ZOJ2686 Cycle Game （博弈，找规律，搜索）
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
题目：有N个点，形成一个环，相邻点之间有权值。从0号点开始，可以选择往两边移动，前提是权值为正。
移动之后，将权值减少一个任意的正数。最后无法移动者败。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1686
一开始就觉得没啥好办法，直接搜索，20个点，权值为30.
果断会T，极端数据根本过不了
其实一开始便发现了一个规律。两个方向，如果某个方向连续的非0个数为奇数的话，先手必胜。
先手的策略是，将权值降为0，后手不能返回了，只能朝一个方向去，如果后手继续将权值降为0，那么先手依旧是继续，因为个数为奇数，先手必胜。如果后手不把权值降为0，那么先手返回一步，将权值降为0，出现两边都为0，必胜。
加上这个优化之后，便从5S的T到30ms。
#include<iostream>#include<cstdio>#include<ctime>#include<cstring>#include<algorithm>#include<cstdlib>#include<vector>#define C 240#define TIME 10#define inf 1<<25#define LL long longusing namespace std;int n,a[30];int slove(int m){ //顺时针找非0个数，如果是奇数，直接返回必胜 int cnt=0; for(int i=m;cnt<n;i=(i+1)%n) if(a[i]==0) break; else cnt++; if(cnt&1) return 1; //逆时针找非0个数，如果是奇数，直接返回必胜 cnt=0; for(int i=(m-1+n)%n;cnt<n;i=(i-1+n)%n) if(a[i]==0) break; else cnt++; if(cnt&1) return 1; for(int i=-1;i<=1;i+=2){ int k; if(i==1) k=m; else k=(m-1+n)%n; for(int j=1;j<=a[k];j++){ a[k]-=j; if(!slove((m+i+n)%n)){ a[k]+=j; return 1; } a[k]+=j; } } return 0;}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); puts(slove(0)?"YES":"NO"); } return 0;}