bzoj 1228: [SDOI2009]E&D
@#$%^&*()
/************************************************************** Problem: 1228 User: lxy8584099 Language: C++ Result: Accepted Time:196 ms Memory:820 kb ****************************************************************/ /* 实际上SG值满足规律: x为奇数,y为奇数:SG=0 x为偶数,y为偶数:SG=SG(x/2 , y/2)+1 x为奇数,y为偶数:SG=SG((x+1)/2 , y/2)+1 x为偶数,y为奇数:SG=SG(x/2 , (y+1)/2)+1 强行超答案。。 */ #include<cstdio> using namespace std; int n,T; long long a,b; int SG(long long a,long long b) { if((a&1)&&(b&1)) return 0; else if(!(a&1)&&!(b&1)) return SG(a/2,b/2)+1; else if(a&1) return SG((a+1)/2,b/2)+1; else return SG(a/2,(b+1)/2)+1; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n);n>>=1; int ans=0; for(int i=1;i<=n;i++) { scanf("%lld%lld",&a,&b); ans^=SG(a,b); } if(ans!=0) printf("YES\n"); else printf("NO\n"); } return 0; }