題干：

大學英語四級考試就要來臨了，你是不是在緊張的復習？也許緊張得連短學期的ACM都沒工夫練習了，反正我知道的Kiki和Cici都是如此。當然，作為在考場浸潤了十幾載的當代大學生，Kiki和Cici更懂得考前的放松，所謂“張弛有道”就是這個意思。這不，Kiki和Cici在每天晚上休息之前都要玩一會兒撲克牌以放松神經。?
“升級”？“雙扣”？“紅五”？還是“斗地主”？?
當然都不是！那多俗啊~?
作為計算機學院的學生，Kiki和Cici打牌的時候可沒忘記專業，她們打牌的規則是這樣的：?
1、??總共n張牌;?
2、??雙方輪流抓牌；?
3、??每人每次抓牌的個數只能是2的冪次（即：1，2，4，8，16…）?
4、??抓完牌，勝負結果也出來了：最后抓完牌的人為勝者；?
假設Kiki和Cici都是足夠聰明（其實不用假設，哪有不聰明的學生~），并且每次都是Kiki先抓牌，請問誰能贏呢？?
當然，打牌無論誰贏都問題不大，重要的是馬上到來的CET-4能有好的狀態。?

Good luck in CET-4 everybody!?

Input

輸入數據包含多個測試用例，每個測試用例占一行，包含一個整數n（1<=n<=1000）。

Output

如果Kiki能贏的話，請輸出“Kiki”，否則請輸出“Cici”，每個實例的輸出占一行。?

Sample Input

1 3

Sample Output

Kiki Cici

解題報告：

? ? 這題顯然是可以話PN圖的，得出結論if(n%3 == 0) ....

? ? 在這里用另外一種方法去做。sg函數不僅可以解決Nim博弈，反正只要是可以畫出一個DAG圖來的，就都可以用sg函數去考慮吧？這里打表要注意一下，我是從f[1]開始打表的，所以getsg函數中需要for(int j=1; f[j]<=i;j++)這樣。如果main函數存f數組的時候是從下標0開始的，那就需要這里的j也從0開始。還有一個要注意的就是，f打表的時候不能(1<<i)<=1000，而應該多打表一些，因為getsg中有f[j]<=i啊，如果你只打表到1000，而不到1024的話，那這個題就涼涼了。

AC代碼：?

#include<bits/stdc++.h>using namespace std; int sg[1005]; bool vis[1005]; int f[22]; void getsg(int n) {memset(sg,0,sizeof sg);for(int i = 1; i<=n; i++) {memset(vis,0,sizeof vis);for(int j = 1; f[j] <= i; j++) {vis[sg[i-f[j]]]=1;}for(int j = 0; j<=i; j++) {if(vis[j]==0) {sg[i]=j;break;}}} } int main() {int n;for(int i = 0; (1<<i)<=2048; i++) {f[i+1] = (1<<i);}getsg(1000);while(~scanf("%d",&n)) {if(sg[n] == 0) puts("Cici");else puts("Kiki");}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 1847】Good Luck in CET-4 Everybody! （巴什博奕，PN图或sg函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。