题解:#include<cstdio>
#include<cstdlib>
int sg(int i,int j){
unsigned long long tmp=2;
for(int re=0;;re++,tmp*=2)
if((i-1)%tmp<tmp/2 && (j-1)%tmp<tmp/2)return re;
}
int n;
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j,a,b,tmp;
int nn = scan();
while(nn--){
n = scan()/2;
tmp=0;
for(i=1;i<=n;i++){
a = scan();b = scan();
tmp ^= sg(a,b);
}
if(tmp)printf("YES\n");
else printf("NO\n");
}
return 0;
}
得到sg(i,j)=k的必要条件:0出现条件i,j均%2=11出现条件i%4=1,2j%4=1,22出现条件i,j%8=1,2,3,4……
(j-1)%2k+1 < 2k
但是需要注意这里是必要不充分条件,因为每个数字并不是网格状,而是三角形。
为什么呢,因为对于3,它某个合适的位置可能同时也对2合适,那么这个值就是2而不是3
也就是说最sg(i,j)会等于最小的合适的k
i,j≤109,所以直接暴力从小到大枚举,每次时间是logn
评论