|
n个石子取2的次幂个，0为terminal position P/N分析和求SG值方法都可以，找规律的话模3余0也能过 主要是为了练习SG的求法 [cpp] view plaincopyprint?
- #include <cstdio>
- #include <cstring>
- //单纯博弈型 也可用P/N分析法
- int x[12],SG[1050];
- bool vis[1050];
-
- void init()
- {
- for (int i=0 ; i<11 ; ++i)
- x=1<<i;
- SG[0]=0;
- for (int i=1 ; i<1002 ; ++i)//get Sprague-Grundy value;
- {
- memset (vis , 0 , sizeof(vis));
- for (int j=0 ; x[j]<=i ; ++j)
- {
- vis[SG[i-x[j]]]=true;
- }
- for (int j=0 ; ; ++j)
- {
- if(!vis[j]){SG=j;break;}
- }
- }
- for (int i=0 ; i<100 ; ++i)
- printf("num=%d sg=%d\n",i,SG);
- }
-
- int main ()
- {
- int n;
- init();
- while (~scanf("%d",&n))
- {
- if(SG[n])puts("Kiki");
- else puts("Cici");
- }
- return 0;
- }
HDU 3980 Paint Chain n元环，每次取连续的m个元素，最先不能取者败。 可以考虑n<m和n>=m两种情况，第一种情况结果显然，第二种将取过1次后剩下的n-m元链进行求SG值，前m-1个状态的SG值明显为0，m为1，之后的状态取走m元素之后，会将剩下的2段分成2份（考虑0的情况），分别求其SG值，从而得到当前的状态的一个后继SG值。
[cpp] view plaincopyprint?
- #include <cstdio>
- #include <cstring>
-
- const int maxn=1005;
- int SG[maxn];
- bool vis[maxn];
-
- bool sg(int n , int m)//get SG value
- {
- memset(SG , 0 , sizeof(SG));
- SG[m]=1;
- for (int i=m+1 ; i<=n ; ++i)
- {
- memset (vis , 0 , sizeof(vis));
- for (int j=0 ; j<i-m ; ++j)
- {
- vis[SG[j]^SG[i-m-j]]=true;
- }
- for (int j=0 ; ; ++j)
- {
- if(!vis[j]){SG=j;break;}
- }
- }
- //for (int i=0 ; i<=n ; ++i)
- //printf("%d %d \n",i,SG);
- return SG[n];
- }
-
- int main ()
- {
- int cas;
- int n,m;
- scanf("%d",&cas);
- for (int I=1 ; I<=cas ; ++I)
- {
- scanf("%d%d",&n,&m);
- if(m>n)printf("Case #%d: abcdxyzk\n",I);
- else if(sg(n-m,m))printf("Case #%d: abcdxyzk\n",I);
- else printf("Case #%d: aekdycoin\n",I);
- }
- return 0;
- }
| 
收藏
淘帖
踩
