HNOI2014题解及数据

HNOI2014题解及数据，包括标程及试题

solution:

明显的组合游戏，暴力N^2求出所有的状态的SG值，复杂度就是O（N^2）可以70分然而我们发现在可以分开枚举：最小的数字小于等于sqrt(N)，分割的数目小于sqrt(N)所以可以做到O(Nsqrt(N))可以过掉本题，不过很多细节需要处理确实比较恶心code:#include#include#include#include#defineMAXN100010intf,n,m,T,a,g,ans,now;usingnamespacestd;intsg[MAXN],vis[MAXN];intinit(){scanf("%d%d",&T,&f);for(inti=0;ifor(inti=f;i<=MAXN-10;i++){intq=(int)ceil(sqrt(i));for(intj=1;jinta=j,b=j+1;intx=i/a,y=i-x*a;x-=y;now=sg[(x&1)*a]^sg[(y&1)*b];vis[now]=i;if(a%2&&x=b){vis[now^sg[b]]=i;}if(a%2==0&&b*(y+a)<=i){vis[now^sg[a]]=i;}}for(intm=2;m<=q;m++){inta=i/m,b=a+1;inty=i-a*m,x=m-y;vis[sg[(x&1)*a]^sg[(y&1)*b]]=i;}for(intj=0;j<=MAXN-10;j++){if(vis[j]!=i){sg[i]=j;break;}}}return0;}intmain(){init();while(T--){scanf("%d",&n);ans=0;intx;for(inti=1;i<=n;i++){scanf("%d",&x);ans=ans^sg[x];}printf("%d%c",ans?1:0,T?'':'\n');}return0;}

Tags:试题.