Codeforces Round #142 (Div. 2) C

http://codeforces.com/problemset/problem/229/A

比完以后看了看其他人的代码，其实思路我是想到了，可是就是代码没实现，代码能力太弱了。。

思路就是先预处理一下。把每行的close[i][j]标记出来。close[i][j]表示在第i行的第j个数最少移动几次可以使得map[i][j]变为1。

在这里可以使用队列来得到close[i][j]的值，下面大牛的代码：

 1 #include <cstdio>
 2 #include <queue>
 3 
 4 int ans[10010], min[10010];
 5 
 6 int main(){
 7 
 8     int n, m;
 9     scanf("%d %d\n" ,&n ,&m);
10 
11     char buf[10010];
12     for(int i = 1; i <= n; i++){
13 
14         scanf("%s" ,buf + 1);
15 
16         std::queue<int> que;
17         for(int j = 1; j <= m; j++){
18             if(buf[j] == '1'){
19                 min[j] = 0;
20                 que.push(j);
21             }
22             else min[j] = m;
23         }
24 
25         if(que.empty()){
26             puts("-1");
27             return 0;
28         }
29 
30         while(!que.empty()){//有点bfs的感觉，我开始也是这么写的，可是我竟然越写越繁琐。唉，代码写的少啊。
31 
32             int now = que.front(); que.pop();
33 
34             int lnex = (now == 1)? m: now - 1;
35             int rnex = (now == m)? 1: now + 1;
36 
37             if(min[lnex] > min[now] + 1){
38                 min[lnex] = min[now] + 1;
39                 que.push(lnex);
40             }
41             if(min[rnex] > min[now] + 1){
42                 min[rnex] = min[now] + 1;
43                 que.push(rnex);
44             }
45 
46         }
47         
48         for(int j = 1; j <= m; j++) ans[j] += min[j];
49 
50     }
51 
52     int res = m * n;
53     for(int i = 1; i <= m; i++){
54         if(res > ans[i]) res = ans[i];
55     }
56     printf("%d\n" ,res);
57 
58 }

在尝试了bfs（其实就是队列....）后。我换成了直接写。。然后貌似没写好，竟然tle了。。可是时间复杂度才n*m*2啊。。。最后没时间了。刚刚改了下变成了下面的形式：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 
  6 using namespace std;
  7 #define MAXN 105
  8 #define inf 10020
  9 #define Min(x,y) (x>y?y:x)
 10 int n,m;
 11 int map[MAXN][MAXN*MAXN];
 12 int close[MAXN][MAXN*MAXN];
 13 
 14 
 15 int main()
 16 {
 17     while(scanf("%d%d",&n,&m) != EOF)
 18     {
 19         getchar();
 20         char buf[256];
 21         for(int i=1;i<=n;i++)
 22         {
 23             gets(buf);
 24             for(int j=1;j<=m;j++)
 25             {
 26                 if(buf[j-1]=='1')
 27                     map[i][j]=1;
 28                 else if(buf[j-1]=='0')
 29                     map[i][j]=0;
 30             }
 31         }
 32         for(int i=1;i<=n;i++)
 33             for(int j=1;j<=m;j++)
 34                 close[i][j]=inf;
 35         for(int i=1;i<=n;i++)
 36         {
 37             int step=inf;
 38             for(int j=1;j<=m*2;j++)//看一个同学的代码是<=m，明显不对。。。估计final test的时候会跪..
 39             {
 40                 if(j==m+1)
 41                     j++;
 42                 if(map[i][j%(m+1)]==1)
 43                 {
 44                     step=0;
 45                     close[i][j%(m+1)]=0;
 46                 }
 47                 else
 48                 {
 49                     step++;
 50                     close[i][j%(m+1)]=Min(close[i][j%(m+1)],step);
 51                 }
 52             }
 53             step=inf;
 54             for(int j=m;j>-m;j--)
 55             {
 56                 if(j==0)
 57                     j--;
 58                 if(map[i][(j+m+1)%(m+1)]==1)
 59                 {
 60                     step=0;
 61                     close[i][(j+m+1)%(m+1)]=0;
 62                 }
 63                 else
 64                 {
 65                     step++;
 66                     close[i][(j+m+1)%(m+1)]=Min(close[i][(j+m+1)%(m+1)],step);
 67                 }
 68             }
 69         }
 70         int ans=inf;
 71         for(int j=1;j<=m;j++)
 72         {
 73             int s=0;
 74             for(int i=1;i<=n;i++)
 75                 s+=close[i][j];
 76             if(s<ans)
 77                 ans=s;
 78         }
 79         if(ans==inf)
 80             puts("-1");
 81         else
 82             printf("%d\n",ans);
 83     }
 84     return 0;
 85 }
 86

明天交下看看。。不应该tle 啊。

接上，终于知道为什么tle了。tle的可能有很多种啊，不一定是算法的问题。问题出在 char buf[256]上.....竟然脑残的把m<=10000给忘了...泪奔啊，还有一个问题就是我的inf定义的太小。（开始是防止超出int才定义这么小的，但是明显这也是错的。。。因为有可能是n*m==1000000啊。。）

改正后ac了。。太水了。

这份也ac了：还是题目做的太少了啊。比赛的时候也没能冷静下来好好想清楚。下次一定得注意！

View Code

 1 #include <iostream>
 2  #include <cstdio>
 3  #include <cstring>
 4  #include <algorithm>
 5  
 6  using namespace std;
 7  #define MAXN 105
 8  #define inf 1000020
 9  #define Min(x,y) (x>y?y:x)
10  int n,m;
11  int map[MAXN][MAXN*MAXN];
12  int close[MAXN][MAXN*MAXN];
13  char buf[10010];
14  
15  int main()
16  {
17      while(scanf("%d%d",&n,&m) != EOF)
18      {
19          getchar();
20          for(int i=1;i<=n;i++)
21          {
22              gets(buf);
23              for(int j=1;j<=m;j++)
24              {
25                  if(buf[j-1]=='1')
26                      map[i][j]=1;
27                  else if(buf[j-1]=='0')
28                      map[i][j]=0;
29              }
30          }
31          for(int i=1;i<=n;i++)
32              for(int j=1;j<=m;j++)
33                  close[i][j]=inf;
34          for(int i=1;i<=n;i++)
35          {
36              int step=inf;
37              for(int j=1;j<=m*2;j++)//看一个同学的代码是<=m，明显不对。。。估计final test的时候会跪..
38              {
39                  if(j==m+1)
40                      j++;
41                  if(map[i][j%(m+1)]==1)
42                  {
43                      step=0;
44                      close[i][j%(m+1)]=0;
45                  }
46                  else
47                  {
48                      step++;
49                      close[i][j%(m+1)]=Min(close[i][j%(m+1)],step);
50                  }
51              }
52              step=inf;
53              for(int j=m;j>-m;j--)
54              {
55                  if(j==0)
56                      j--;
57                  if(map[i][(j+m+1)%(m+1)]==1)
58                  {
59                      step=0;
60                      close[i][(j+m+1)%(m+1)]=0;
61                  }
62                  else
63                  {
64                      step++;
65                      close[i][(j+m+1)%(m+1)]=Min(close[i][(j+m+1)%(m+1)],step);
66                  }
67              }
68          }
69          int ans=inf;
70          for(int j=1;j<=m;j++)
71          {
72              int s=0;
73              for(int i=1;i<=n;i++)
74              {
75                   s+=close[i][j];
76                  if(s>ans)
77                      break;
78              }
79              if(s<ans)
80                  ans=s;
81          }
82          if(ans==inf)
83              puts("-1");
84          else
85              printf("%d\n",ans);
86      }
87      return 0;
88  }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 #define MAXN 105
 8 #define inf 1000020
 9 #define Min(x,y) (x>y?y:x)
10 int n,m;
11 char map[MAXN][MAXN*MAXN];
12 int close[MAXN][MAXN*MAXN];
13 
14 
15 int main()
16 {
17     while(scanf("%d%d",&n,&m) != EOF)
18     {
19         getchar();
20         for(int i=1;i<=n;i++)
21         {
22             gets(map[i]+1);
23         }
24         for(int i=1;i<=n;i++)
25             for(int j=1;j<=m;j++)
26                 close[i][j]=inf;
27         for(int i=1;i<=n;i++)
28         {
29             queue<int>q;
30             int cur,lnext,rnext;
31             while(!q.empty())
32                 q.pop();
33             for(int j=1;j<=m;j++)
34                 if(map[i][j]=='1')
35                 {    
36                     close[i][j]=0;
37                     q.push(j);
38                 }
39             while(!q.empty())
40             {
41                 cur=q.front();
42                 q.pop();
43                 lnext=(cur==1)?m:cur-1;
44                 rnext=(cur==m)?1:cur+1;
45                 if(close[i][lnext]>close[i][cur]+1)
46                 {
47                     close[i][lnext]=close[i][cur]+1;
48                     q.push(lnext);
49                 }
50                 if(close[i][rnext]>close[i][cur]+1)
51                 {
52                     close[i][rnext]=close[i][cur]+1;
53                     q.push(rnext);
54                 }
55             }
56         }
57     /*    for(int i=1;i<=n;i++)
58         {
59             for(int j=1;j<=m;j++)
60                 cout<<close[i][j]<<" ";
61             cout<<endl;
62         }
63 */
64         int ans=inf;
65         for(int j=1;j<=m;j++)
66         {
67             int s=0;
68             for(int i=1;i<=n;i++)
69             {
70                 s+=close[i][j];
71                 if(s>ans)
72                     break;
73             }
74             if(s<ans)
75                 ans=s;
76         }
77         if(ans==inf)
78             puts("-1");
79         else
80             printf("%d\n",ans);
81     }
82     return 0;
83 }