首页 > 代码库 > hdu 1847 Good Luck in CET-4 Everybody!

hdu 1847 Good Luck in CET-4 Everybody!

2024-07-17 05:56:00   220人阅读

法一：

首先我们可以想到在面对3的时候是必败局，谁面对3时无论拿多少都会败 ! <---这是关键

那么就要尽量造成这样的局势给对方，因为任何不是3的倍数的数加1或2都可以变成3的倍数，
同理减去1或2也可以变成3的倍数，也就是说假设目前的个数不是3的倍数，那我肯定能把它

拿成3的倍数，比如现在是11个，那我拿走2个就变成9，这样就造成对方为3的倍数局势，那

么对方拿m个我都可以通过拿1或者2使总共一轮拿的数目成为3的倍数
#include<stdio.h>
int main()
{
    int n;
    while(~scanf("%d",&n)) 
    {
       if(n%3==0)
          printf("Cici\n");
       else
         printf("Kiki\n"); 
    }
    return 0;
}

法二：

sg函数：

照着模板敲得说实话，没明白sg函数到底怎么回事，为什么可以这样用

sg[n]=0,后者赢；

路过的谁懂，希望解释一下


代码如下：
#include<stdio.h>
#include<string.h>
#define Maxn 1100  
  
int sg[Maxn],ba[Maxn],cnt,n,temp[Maxn];  
  
void init()  
{  
    int i,j;
    ba[0]=1;  
    for( i=1;i<=9;i++) //打出1000内的2次幂数  
        ba[i]=ba[i-1]*2;  
    cnt=9;  
    memset(sg,-1,sizeof(sg));  
    sg[0]=0;  
  
    for(i=1;i<=1000;i++) //求出所有状态的sg值  
    {  
        memset(temp,-1,sizeof(temp));  
        for( j=0;j<=cnt&&ba[j]<=i;j++)  
            temp[sg[i-ba[j]]]=0;  
        for( j=0;;j++)  
            if(temp[j]==-1) //第一个没出现的数  
            {  
                sg[i]=j;  
                break;  
            }  
    }  
}  
int main()  
{  
   init();  
   while(~scanf("%d",&n))  
   {  
       if(sg[n]) //先赢  
            printf("Kiki\n");  
       else  
            printf("Cici\n");  
   }  
   return 0;  
}





联系
我们