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 DescriptionClarke is a patient with multiple personality disorder. One day, Clarke split into two personality a and b, they are playing a game.
There is a n∗m matrix, each grid of this matrix has a number ci,j.
a wants to beat b every time, so a ask you for a help.
There are q operations, each of them is belonging to one of the following two types:
1. They play the game on a (x1,y1)−(x2,y2) sub matrix. They take turns operating. On any turn, the player can choose a grid which has a positive integer from the sub matrix and decrease it by a positive integer which less than or equal this grid’s number. The player who can’t operate is loser. a always operate first, he wants to know if he can win this game.
2. Change ci,j to b.
InputThe first line contains a integer T(1≤T≤5), the number of test cases.
For each test case:
The first line contains three integers n,m,q(1≤n,m≤500,1≤q≤2∗105)
Then n∗m matrix follow, the i row j column is a integer ci,j(0≤ci,j≤109)
Then q lines follow, the first number is opt.
if opt=1, then 4 integers x1,y1,x1,y2(1≤x1≤x2≤n,1≤y1≤y2≤m) follow, represent operation 1.
if opt=2, then 3 integers i,j,b follow, represent operation 2. OutputFor each testcase, for each operation 1, print Yes if a can win this game, otherwise print No. Sample Input1
1 2 3
1 2
1 1 1 1 2
2 1 2 1
1 1 1 1 2 Sample OutputYes
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.
SourceBestCoder Round #56 (div.2) 对于操作1而言就是一个裸的nim博弈,答案就是 {c[x1][y1]^……^c[x2][y2]} 操作二就是改变了格子中的一个数。 用二维BIT来维护矩阵内的异或和即可。 (最近总把下标写错,,把x1,y1写成了i,j检查半天, (误
#include<bits/stdc++.h>
using namespace std;
#define ULL unsigned long long
#define LL long long
int c[][];
int C[][];
int N,M;
inline int lowbit(int x){return x&-x;}
void change(int x,int y,int d){
for(int i=x;i<=N;i+=lowbit(i))
for(int j=y;j<=M;j+=lowbit(j))
C[i][j]^=d;
}
int ask(int x,int y){
int r=;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
r^=C[i][j];
return r;
}
int main(){
int t,n,m,i,q,j,k,x1,x2,y1,y2;
scanf("%d",&t);
while(t--){
memset(C,,sizeof(C));
scanf("%d%d%d",&n,&m,&q);
N=n,M=m;
for(i=;i<=n;++i){
for(j=;j<=m;++j){
scanf("%d",&c[i][j]);
change(i,j,c[i][j]);
}
} int opt,d;
while(q--){
scanf("%d",&opt);
if(opt==){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans=(ask(x2,y2)^ask(x1-,y1-)^ask(x1-,y2)^ask(x2,y1-));
ans?puts("Yes"):puts("No");
}
else{
scanf("%d%d%d",&x1,&y1,&d);
change(x1,y1,(d^c[x1][y1]));
c[x1][y1]=d;
}
}
}
return ;
}