HDOJ 1847 Good Luck in CET-4 Everybody!

题目地址:
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的倍数个,那继续; 所以这样拿下去必胜

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main ()
{
    int N;
    while ( cin >> N )
    {
          puts ( N % 3 != 0 ? "Kiki" : "Cici" ); 
    }
    return 0; 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1847 Good Luck in CET-4 Everybody!》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注