[TS-A1488][2013中国国家集训队第二次作业]魔法波[高斯消元]

暴力直接解异或方程组，O(n^6)无法接受，那么我们考虑把格子分块，横着和竖着分别分为互不影响的块，这样因为障碍物最多不超过200个，那么块的个数最多为2*(800+200)=2000个，最后用bitset优化即可。

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 int n,cnt,Pos[2100],Right[2100],Left[2100];
  6 int Crs[1100][1100],Dwn[1100][1100],MID;
  7 char    str[1100][1100];
  8 
  9 bitset<2100>eq[2100];
 10 
 11 void    Gauss()
 12 {
 13     int i,j;
 14     for(i=1;i<=cnt;++i)
 15     {
 16         j=i;
 17         while(!eq[j][i] && j<=cnt)j++;
 18         if(j==cnt+1)continue;
 19         if(j!=i)swap(eq[j],eq[i]);
 20         for(j=1;j<=cnt;++j)
 21             if(j!=i && eq[j][i])eq[j]^=eq[i];
 22     }
 23     return ;
 24 }
 25 
 26 int main()
 27 {
 28     int i,j,temp;
 29 
 30     scanf("%d",&n);
 31 
 32     for(i=1;i<=n;++i)
 33         scanf("%s",str[i]+1);
 34 
 35     for(i=1;i<=n;++i)
 36         str[0][i]=str[i][0]=str[i][n+1]=str[n+1][i]='X';
 37 
 38     cnt=1;
 39 
 40     for(j=1;j<=n;++j) for(i=1;i<=n+1;++i)
 41     {
 42         if(str[i][j]!='X')Crs[i][j]=cnt;
 43         if(str[i-1][j]=='X' && str[i][j]!='X')Left[cnt]=i,Pos[cnt]=j;
 44         if(str[i+1][j]=='X' && str[i][j]!='X')Right[cnt]=i,cnt++;
 45     }
 46 
 47     MID=cnt-1;
 48     
 49     for(i=1;i<=n;++i) for(j=1;j<=n+1;++j)
 50     {
 51         if(str[i][j]!='X')Dwn[i][j]=cnt;
 52         if(str[i][j-1]=='X' && str[i][j]!='X')Left[cnt]=j,Pos[cnt]=i;
 53         if(str[i][j+1]=='X' && str[i][j]!='X')Right[cnt]=j,cnt++;
 54     }
 55 
 56     cnt--;
 57 
 58     for(i=1;i<=MID;++i)
 59     {
 60         temp=0;
 61         eq[i].set(i);
 62 
 63         for(j=Left[i];j<=Right[i];++j)
 64         {
 65             eq[i][Crs[j][Pos[i]]]=eq[i][Crs[j][Pos[i]]]^1;
 66             eq[i][Dwn[j][Pos[i]]]=eq[i][Dwn[j][Pos[i]]]^1;
 67             temp^=(str[j][Pos[i]]=='X'?0:str[j][Pos[i]]-48);
 68             temp^=1;
 69         }
 70 
 71         eq[i][cnt+1]=temp;
 72 #ifdef  Debug
 73         cerr << eq[i] << endl;
 74 #endif
 75     }
 76 
 77     for(i=MID+1;i<=cnt;++i)
 78     {
 79         temp=0;
 80         eq[i].set(i);
 81 
 82         for(j=Left[i];j<=Right[i];++j)
 83         {
 84             eq[i][Crs[Pos[i]][j]]=eq[i][Crs[Pos[i]][j]]^1;
 85             eq[i][Dwn[Pos[i]][j]]=eq[i][Dwn[Pos[i]][j]]^1;
 86             temp^=(str[Pos[i]][j]=='X'?0:str[Pos[i]][j]-48);
 87             temp^=1;
 88         }
 89 
 90         eq[i][cnt+1]=temp;
 91 #ifdef  Debug
 92         cerr << eq[i] << endl;
 93 #endif
 94     }
 95 
 96     Gauss();
 97 
 98 #ifdef  Debug
 99     cerr << endl;
100     for(i=1;i<=cnt;++i)
101         cerr << eq[i] << endl;
102     cerr << endl;
103 #endif
104 
105     for(i=1;i<=n;++i)
106     {
107         for(j=1;j<=n;++j)
108         {
109             printf("%d",str[i][j]=='X'?0:(1^eq[Crs[i][j]][cnt+1]^eq[Dwn[i][j]][cnt+1]
110                         ^(str[i][j]-48)));
111         }
112         printf("
");
113     }
114 
115     return 0;
116 }