hdu-5465-二维BIT+nim Clarke and puzzle

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 951 Accepted Submission(s): 349

Problem Description

Clarke is a patient with multiple personality disorder. One day, Clarke split into two personality

Input

The first line contains a integer

Output

For each testcase, for each operation

Sample Input

1 1 2 3 1 2 1 1 1 1 2 2 1 2 1 1 1 1 1 2

Sample Output

Yes No Hint: The first enquiry: $a$ can decrease grid $(1, 2)$'s number by $1$. No matter what $b$ operate next, there is always one grid with number $1$ remaining . So, $a$ wins. The second enquiry: No matter what $a$ operate, there is always one grid with number $1$ remaining. So, $b$ wins.

Source

BestCoder Round #56 (div.2)

　　　　对于操作1而言就是一个裸的nim博弈，答案就是 {c[x1][y1]^......^c[x2][y2]}

　　操作二就是改变了格子中的一个数。

用二维BIT来维护矩阵内的异或和即可。

　　(最近总把下标写错，，把x1,y1写成了i,j检查半天， (误

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ULL unsigned long long 
 4 #define LL long long 
 5 int c[510][510];
 6 int C[510][510];
 7 int N,M;
 8 inline int lowbit(int x){return x&-x;}
 9 void change(int x,int y,int d){
10     for(int i=x;i<=N;i+=lowbit(i))
11         for(int j=y;j<=M;j+=lowbit(j))
12             C[i][j]^=d;
13 }
14 int ask(int x,int y){
15     int r=0;
16     for(int i=x;i;i-=lowbit(i))
17         for(int j=y;j;j-=lowbit(j))
18             r^=C[i][j];
19     return r;
20 }
21 int main(){
22     int t,n,m,i,q,j,k,x1,x2,y1,y2;
23     scanf("%d",&t);
24     while(t--){
25         memset(C,0,sizeof(C));
26         scanf("%d%d%d",&n,&m,&q);
27         N=n,M=m;
28         for(i=1;i<=n;++i){
29             for(j=1;j<=m;++j){
30                 scanf("%d",&c[i][j]);
31                 change(i,j,c[i][j]);
32             }
33         }
34         
35         int opt,d;
36         while(q--){
37             scanf("%d",&opt);
38             if(opt==1){
39                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
40                 int ans=(ask(x2,y2)^ask(x1-1,y1-1)^ask(x1-1,y2)^ask(x2,y1-1));
41                 ans?puts("Yes"):puts("No");
42             }
43             else{
44                 scanf("%d%d%d",&x1,&y1,&d);
45                 change(x1,y1,(d^c[x1][y1]));
46                 c[x1][y1]=d;
47             }
48         }
49     }
50     return 0;
51 }

hdu-5465-二维BIT+nim Clarke and puzzle

相关推荐