Tanky WooRSS

HDOJ 1847 Good Luck in CET-4 Everybody!

19 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1847


有人说这是巴什博弈,有人说是SG函数。。。我也迷糊了~~~ 转载至MiYu大牛~~~:http://www.cppblog.com/MiYu/archive/2010/08/09/122845.html

首先我们可以想到在面对3的时候是必败局,谁面对3时无论拿多少都会败 ! <---这是关键 那么就要尽量造成这样的局势给对方,因为任何不是3的倍数的数加1或2都可以变成3的倍数, 同理减去1或2也可以变成3的倍数,也就是说假设目前的个数不是3的倍数,那我肯定能把它 拿成3的倍数,比如现在是11个,那我拿走2个就变成9,这样就造成对方为3的倍数局势,那 么对方拿m个我都可以通过拿1或者2使总共一轮拿的数目成为3的倍数,这样就会有两种情况: 1.刚好拿完. 2.剩下的还有3的倍数个,那继续; 所以这样拿下去必胜
#include 
using namespace std;
int main ()
{
    int N;
    while ( cin >> N )
    {
          puts ( N % 3 != 0 ? "Kiki" : "Cici" ); 
    }
    return 0; 
}