HDU4146 水~

水题~
只需记录下改变的行，列即可。
View Code
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 const int maxn = 1005;
 5 const int maxm = 100005;
 6 int mat[ maxn ][ maxn ];
 7 int row[ maxn ],col[ maxn ];
 8 
 9 int main(){
10     int T;
11     scanf("%d",&T);
12     int ca=1;
13     while( T-- ){
14         int n;
15         scanf("%d",&n);
16         char a[ maxn ];
17         for( int i=1;i<=n;i++ ){
18             scanf("%s",a+1);
19             for( int j=1;j<=n;j++ ){
20                 if( a[j]=='b' ){
21                     mat[i][j]=1;
22                 }
23                 else{
24                     mat[i][j]=-1;
25                 }
26             }
27         }
28         int t;
29         scanf("%d",&t);
30         int x,y;
31         memset( row,0,sizeof( row ));
32         memset( col,0,sizeof( col ));
33         for( int k=0;k<t;k++ ){
34             scanf("%d%d",&x,&y);
35             row[ x ]++;
36             col[ y ]++;
37         }
38         int ans=0;
39         for( int i=1;i<=n;i++ ){
40             for( int j=1;j<=n;j++ ){
41                 if( (row[i]+col[j])%2==1&&mat[i][j]==1 ){
42                     ans++;
43                 }
44                 else
45                     if( (row[i]+col[j])%2==0&&mat[i][j]==-1 ){
46                         ans++;
47                     }
48             }
49         }
50         printf("Case #%d: %d\n",ca++,ans);
51     }
52     return 0;
53 }
由于没有估算数据量 TLE了一次。。
keep moving...