SRM423DIVII_Mo Cushile-my darling,myblood_百度空间企业库|免费b2b网站

SRM423DIVII_Mo Cushile-my darling,myblood_百度空间

pts1000好难好经典..
1.{dy}题很简单..
34      int count(int n, vector <int> x, vector <int> y)
35      {
36          int res=0;
37          for(int i=0;i<(int)x.size();i++){
38              int a=x[i];
39              int b=y[i];
40              res+=min(abs(a-1)+abs(b-1),
41                       min(abs(a-1)+abs(b-n),
42                           min(abs(a-n)+abs(b-1),
43                               abs(a-n)+abs(b-n))));
44
45          }
46          return res;
47      }

2.第二题还是看别人才想到的...其实以前在CLRS上就看过这个问题曼哈顿距离的邮局问题。对于1维的话最近点都是在轴上的点..而对于多维的话只需要进行这些轴上的组合即可...[这道题绕圈子绕了好久...]
34      vector <int> count(vector <int> x, vector <int> y)
35      {
36          int n=(int)x.size();
37          vector<int>res(n,-1);
38          for(int i=0;i<n;i++){
39              for(int j=0;j<n;j++){
40                  vector<int>tmp(n,0);
41                  for(int k=0;k<n;k++){
42                      tmp[k]=abs(x[k]-x[i])+abs(y[k]-y[j]);
43                  }
44                  sort(tmp.begin(),tmp.end());
45                  for(int k=1;k<n;k++){
46                      tmp[k]+=tmp[k-1];
47                  }
48                  for(int k=0;k<n;k++){
49                      if(res[k]==-1)
50                          res[k]=tmp[k];
51                      else
52                          res[k]=min(res[k],tmp[k]);
53                  }
54              }
55          }
56          return res;
57      }

3.pts1000好难....是一个很经典的博弈问题，解决算法也是非常的经典.个人认为对于下面题目分析的链接和misof/Petr/ezander[两种不同的算法]给出的源码要好好看看..关于题目分析可以看下面的链接
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm423
使用迭代计算方法[misof]
http://www.topcoder.com/stat?c=problem_solution&rm=299103&rd=13514&pm=9977&cr=8357090
32 const int UNKNOWN=1<<31-1;
33 int result[2][20][20][20][20];
34 int old_result[2][20][20][20][20];
38      bool inrange(int r,int c,int n)
39      {
40          if(r<0 || r>=n)return false;
41          if(c<0 || c>=n)return false;
42          return true;
43      }
44      string winner(int n, int rowWhite, int colWhite, int rowBlack, int colBlack)
45      {
46          int dir[8][2]={{-1,0},
47                         {0,-1},
48                         {0,1},
49                         {1,0},
50                         {-2,0},
51                         {0,-2},
52                         {0,2},
53                         {2,0}};
54          for(int rw=0;rw<n;rw++){
55              for(int cw=0;cw<n;cw++){
56                  for(int rb=0;rb<n;rb++){
57                      for(int cb=0;cb<n;cb++){
58                          result[0][rw][cw][rb][cb]=result[1][rw][cw][rb][cb]=UNKNOWN;
59                      }
60                  }
61              }
62          }
63          for(int r=0;r<n;r++){
64              for(int c=0;c<n;c++){
65                  result[0][r][c][r][c]=result[1][r][c][r][c]=0;
66              }
67          }
68          memcpy(old_result,result,sizeof(result));
69          int current_move=0;
70          bool update=true;
71          while(1){
72              current_move++;
73              update=false;
74              for(int who=0;who<=1;who++){
75                  for(int rw=0;rw<n;rw++){
76                      for(int cw=0;cw<n;cw++){
77                          for(int rb=0;rb<n;rb++){
78                              for(int cb=0;cb<n;cb++){
79                                  //win situation ..
80                                  if(result[who][rw][cw][rb][cb]==UNKNOWN){
81                                      for(int i=0;i<((who==0)?4:8);i++){
82                                          int nr1=rw,nc1=cw,nr2=rb,nc2=cb;
83                                          (who==0?nr1:nr2)+=dir[i][0];
84                                          (who==0?nc1:nc2)+=dir[i][1];
85                                          if(!inrange(nr1,nc1,n) || !inrange(nr2,nc2,n))continue;
86                                          if(old_result[1-who][nr1][nc1][nr2][nc2]!=UNKNOWN &&
87                                             old_result[1-who][nr1][nc1][nr2][nc2]<=0){
88                                              //another lose...
89                                              result[who][rw][cw][rb][cb]=current_move;
90                                              update=true;
91                                              break;
92                                          }
93                                      }
94                                  }
95                                  //lose situation...
96                                  if(result[who][rw][cw][rb][cb]==UNKNOWN){
97                                      bool know_all=true;
98                                      for(int i=0;i<((who==0)?4:8);i++){
99                                          int nr1=rw,nc1=cw,nr2=rb,nc2=cb;
100                                          (who==0?nr1:nr2)+=dir[i][0];
101                                          (who==0?nc1:nc2)+=dir[i][1];
102                                          if(!inrange(nr1,nc1,n) || !inrange(nr2,nc2,n))continue;
103                                          if(old_result[1-who][nr1][nc1][nr2][nc2]==UNKNOWN){
104                                              know_all=false;
105                                              break;
106                                          }
107                                      }
108                                      if(know_all){
109                                          result[who][rw][cw][rb][cb]=-current_move;
110                                          update=true;
111                                      }
112                                  }
113                              }
114                          }
115                      }
116                  }
117              }
118              if(!update)break;
119              memcpy(old_result,result,sizeof(result));
120          }
121          char buf[1024];
122          int res=result[0][rowWhite-1][colWhite-1][rowBlack-1][colBlack-1];
123          char *win;
124          if(res>=0){
125              win="WHITE";
126          }else{
127              win="BLACK";
128              res=-res;
129          }
130          snprintf(buf,sizeof(buf),"%s %d",win,res);
131          return buf;
132      }
使用类BFS计算方法[Petr]
http://www.topcoder.com/stat?c=problem_solution&rm=299099&rd=13514&pm=9977&cr=10574855
并且参考这个帖子[ezander，方法非常巧妙...]
http://forums.topcoder.com/?module=Thread&threadID=626748&start=0
31 struct info_t
32 {
33      bool win;
34      int step;
35      int remain;
36 };
37 struct status_t
38 {
39      int who;
40      int rw,cw,rb,cb;
41      status_t(int _who,int _rw,int _cw,int _rb,int _cb):
42          who(_who),rw(_rw),cw(_cw),rb(_rb),cb(_cb)
43      {
44      }
45 };
46 info_t result[2][20][20][20][20];
50      bool inrange(int r,int c,int n)
51      {
52          if(r<0 || r>=n)return false;
53          if(c<0 || c>=n)return false;
54          return true;
55      }
56      string winner(int n, int rowWhite, int colWhite, int rowBlack, int colBlack)
57      {
58          static int dir[8][2]={{-1,0},
59                                {0,-1},
60                                {0,1},
61                                {1,0},
62                                {-2,0},
63                                {0,-2},
64                                {0,2},
65                                {2,0}};
66          for(int rw=0;rw<n;rw++){
67              for(int cw=0;cw<n;cw++){
68                  for(int rb=0;rb<n;rb++){
69                      for(int cb=0;cb<n;cb++){
70                          result[0][rw][cw][rb][cb]=(info_t){win:false,step:0,remain:min(1,rw)+min(1,n-1-rw)+min(1,cw)+min(1,n-1-cw)};
71                          result[1][rw][cw][rb][cb]=(info_t){win:false,step:0,remain:min(2,rb)+min(2,n-1-rb)+min(2,cb)+min(2,n-1-cb)};
72                      }
73                  }
74              }
75          }
76          queue<status_t>Q;
77          for(int r=0;r<n;r++){
78              for(int c=0;c<n;c++){
79                  Q.push(status_t(0,r,c,r,c));
80                  Q.push(status_t(1,r,c,r,c));
81              }
82          }
83          while(!Q.empty()){
84              status_t s=Q.front();
85              Q.pop();
86              int who=s.who,rw=s.rw,cw=s.cw,rb=s.rb,cb=s.cb;
87              info_t &target=result[who][rw][cw][rb][cb];
88              for(int i=0;i<((who==0)?8:4);i++){
89                  int nr1=rw,nc1=cw,nr2=rb,nc2=cb;
90                  ((who==0)?nr2:nr1)+=dir[i][0];
91                  ((who==0)?nc2:nc1)+=dir[i][1];
92                  if(!inrange(nr1,nc1,n) || !inrange(nr2,nc2,n))continue;
93                  info_t &info=result[1-who][nr1][nc1][nr2][nc2];
94                  if(info.remain==0)continue;
95                  info.win=!target.win;
96                  info.step=target.step+1;
97                  info.remain--;
98                  if(info.win){
99                      info.remain=0;
100                  }
101                  if(info.remain==0){
102                      Q.push(status_t(1-who,nr1,nc1,nr2,nc2));
103                  }
104              }
105          }
106          char buf[1024];
107          info_t &res=result[0][rowWhite-1][colWhite-1][rowBlack-1][colBlack-1];
108          snprintf(buf,sizeof(buf),"%s %d",res.win?"WHITE":"BLACK",res.step);
109          return buf;
110      }

郑重声明：资讯【SRM423DIVII_Mo Cushile-my darling,myblood_百度空间】由发布，版权归原作者及其所在单位，其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实，请读者仅作参考，并请自行核实相关内容。若本文有侵犯到您的版权，请你提供相关证明及申请并与我们联系（qiyeku # qq.com）或【在线投诉】，我们审核后将会尽快处理。

—— 相关资讯 ——