首页 > 代码库 > poj_2234

poj_2234

2024-07-13 18:14:46   223人阅读

做AdHoc的題目放了一道博弈論，當時一看就知道是Nim遊戲。之前聽老師說過，也遇到過類似的題目，只是都沒有去看和寫過。

遊戲的大致規則就是給兩個玩家在n堆石子中輪流拿走石子，每個玩家每次只能從一堆中至少拿一個（當然不能超過那堆的個數），

輪到玩家沒石子可拿那個玩家就輸（就是拿走最後剩餘石子的玩家贏）。

問，先拿石子的玩家在兩個玩家都是最優策略的情況下能否贏。

做法，設每堆石子的個數分別為a1,a2,a3,a4.....an-1,an。

設ans=a1 XOR a2 XOR a3 XOR a4 ...XOR an-1 XOR an，若ans=1,則先拿的人必贏，否則先拿的必輸

這是Nim遊戲最基本的情況，還有不少引申和變型，比如Sprague-Grundy function今天就沒全懂，特別是G值得算法

下面是題目：

 

Matches Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 8446 Accepted: 4880

Description

Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not.

Input

The input consists of several lines, and in each line there is a test case. At the beginning of a line, there is an integer M (1 <= M <=20), which is the number of piles. Then comes M positive integers, which are not larger than 10000000. These M integers represent the number of matches in each pile.

Output

For each test case, output "Yes" in a single line, if the player who play first will win, otherwise output "No".

Sample Input

2 45 453 3 6 9

Sample Output

NoYes

Source

POJ Monthly,readchild

 

下面是AC代碼：

#include<cstdio>#include<cstdlib>#include<cstring>int main(){   int n,i,j;   freopen("in.txt","r",stdin);   freopen("out.txt","w",stdout);   while(scanf("%d",&n)==1)   {      int ans=0;      for(i=0;i<n;i++)         {            int u;            scanf("%d",&u);            ans^=u;         }         if(ans) printf("Yes\n");            else printf("No\n");   }   return 0;}


 

 

poj_2234


联系
我们