ICPC nanchang invitation E card Game




根据以上我们得出SG函数，当SG函数异或和为0时，先手必输，我们记录一下位置，然后就可以愉快的博弈了

**#include<bits/stdc++.h>
using namespace std;
const int maxn = 200000+100;
int a[maxn],b[maxn],sum[maxn],pre[maxn],nxt[maxn];
int main(void){	
  // a[0] = -1;
   int T;cin>>T;
   int kase = 0;
   while(T--){
   	 int n,m;
	 scanf("%d%d",&n,&m);
   	 map<int,int> ma;
   	 int ans = 0,x,y;
	 // pre[1] 
   	 for(int i = 1;i <= n; ++i)
   	    scanf("%d",&a[i]),pre[i] = a[i-1]+1;
     pre[1] = 0;
	 for(int i = 1;i < n; ++i)
	 	nxt[i] = a[i+1]-1;
   	 nxt[n] = m-1;
   	 for(int i = 2;i <= n; ++i){
   		 if(a[i]-a[i-1]-1> ans){
   			ans = a[i]-a[i-1]-1;
   			x = a[i-1]+1;
   			y = a[i]-1;
		} 	
	 }
	 	if(ans < a[1])  ans = a[1],x = 0,y = a[1]-1;
// cout<<a[1]-1<<endl; 
	 	
   	 for(int i = 1;i <= n; ++i){
	   	 	if(__builtin_popcount(a[i])&1)
	   	 		b[i] = a[i]*2;
	   	 	else
	   	 		b[i] = a[i]*2+1;
	   	 	sum[i] = sum[i-1]^b[i];
			int xx,yy,len;
			len = 0;
			if(sum[i] == 0){
				len = nxt[i]+1,xx = 0,yy = nxt[i];
			}
		    else if(ma[sum[i]] == 0)
	   	 	{
	   	 			ma[sum[i]] = i;
			}
	   	 	else {
	   	 		
	   	 			int  tt = pre[ma[sum[i]]+1];
	   	 			len  = nxt[i]-tt+1;
	   	 			xx = tt;
	   	 			yy = nxt[i];
	   	 	}
	   	 	if(len > ans){
	   	 		ans = len;
	   	 		x = xx;
	   	 		y = yy;
			}
	   	} 
	   	if(ans < m-a[n]-1)  ans = m-a[n]-1,x = a[n]+1,y = m-1;
// cout<<sum[n]<<endl;
   		printf("Case %d:\n",++kase);
   	 	if(ans == 0)
   	 		printf("0\n");
   	 	else
   	 		printf("%d\n%d %d\n",y-x+1,x,y);
	
}
	
	
	return 0;
}**