Posted on 2010-08-09 21:09
MiYu 閱讀(450)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM ( 組合 ) 、
ACM ( 博弈 )
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1849
題目描述:
Problem Description
大學(xué)時(shí)光是浪漫的，女生是浪漫的，圣誕更是浪漫的，但是Rabbit和Grass這兩個(gè)大學(xué)女生在今年的圣誕節(jié)卻表現(xiàn)得一點(diǎn)都不浪漫：不去逛商場(chǎng)，不去逛公園，不去和AC男約會(huì)，兩個(gè)人竟然貓?jiān)趯嬍诚缕?#8230;…
說(shuō)是下棋，其實(shí)只是一個(gè)簡(jiǎn)單的小游戲而已，游戲的規(guī)則是這樣的：
1、 棋盤包含1*n個(gè)方格，方格從左到右分別編號(hào)為0，1，2，…，n-1；
2、 m個(gè)棋子放在棋盤的方格上，方格可以為空，也可以放多于一個(gè)的棋子；
3、 雙方輪流走棋；
4、 每一步可以選擇任意一個(gè)棋子向左移動(dòng)到任意的位置（可以多個(gè)棋子位于同一個(gè)方格），當(dāng)然，任何棋子不能超出棋盤邊界；
5、 如果所有的棋子都位于最左邊（即編號(hào)為0的位置），則游戲結(jié)束，并且規(guī)定最后走棋的一方為勝者。
對(duì)于本題，你不需要考慮n的大小（我們可以假設(shè)在初始狀態(tài)，棋子總是位于棋盤的適當(dāng)位置）。下面的示意圖即為一個(gè)1*15的棋盤，共有6個(gè)棋子，其中，編號(hào)8的位置有兩個(gè)棋子。
大家知道，雖然偶爾不夠浪漫，但是Rabbit和Grass都是冰雪聰明的女生，如果每次都是Rabbit先走棋，請(qǐng)輸出最后的結(jié)果。
Input
輸入數(shù)據(jù)包含多組測(cè)試用例，每個(gè)測(cè)試用例占二行，首先一行包含一個(gè)整數(shù)m（0<=m<=1000），表示本測(cè)試用例的棋子數(shù)目，緊跟著的一行包含m個(gè)整數(shù)Ki(i=1…m; 0<=Ki<=1000)，分別表示m個(gè)棋子初始的位置，m=0則結(jié)束輸入。
Output
如果Rabbit能贏的話，請(qǐng)輸出“Rabbit Win!”，否則請(qǐng)輸出“Grass Win!”，每個(gè)實(shí)例的輸出占一行。
Sample Input
2
3 5
3
3 5 6
0
Sample Output
Rabbit Win!
Grass Win!
題目分析 :
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
標(biāo)準(zhǔn) 的 nim 博弈 問(wèn)題, 不要想復(fù)雜了 . 因?yàn)橹荒芡笠? 所以可以將 初始的每個(gè)棋子的位置看成一個(gè)堆, 比如說(shuō), 1個(gè)棋子在 n-1格, 那么就代表這個(gè)堆有 n-1個(gè)數(shù)
左移1格,就是取走一個(gè), 所以有 m 棋子就代表有m個(gè)堆, 全部到0就是取完了............ 更具體的 nim 博弈介紹請(qǐng)點(diǎn)擊 << 博弈入門 >>
代碼如下:
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
#include <iostream>
int heap[1001];
int main ()
{
int T;
while ( scanf ( "%d",&T ), T )
{
int res = 0 , nCount = 0;
for ( int i = 0; i != T; ++ i )
{
scanf ( "%d",heap + i );
res ^= heap[i];
}
puts ( res == 0 ? "Grass Win!" : "Rabbit Win!" );
}
return 0;
}