先定義mex(minimal excludant)運算，這是施加於一個集合的運算，表最小的不屬於這個集合的非負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
遊戲的和的SG函數值等於他包含的各個子游戲SG函數值的互斥或和
遊戲的某個局面必勝，當且僅當該局面對應節點的SG函數值大於0
遊戲的某個局面必敗，當且僅當該局面對應節點的SG函數值等於0
//f[N]:可改變當前狀態的方式，N為方式的種類，f[N]要在getSG之前先預處理
//SG[]:0~n的SG函數值
//S[]:為x後繼狀態的集合
int f[N],SG[MAXN],S[MAXN];
void getSG(int n){
int i,j;
memset(SG,0,sizeof(SG));
//因為SG[0]始終等於0，所以i從1開始
for(i = 1; i <= n; i++){
//每一次都要將上一狀態 的 後繼集合 重置
memset(S,0,sizeof(S));
for(j = 0; f[j] <= i && j <= N; j++)
S[SG[i-f[j]]] = 1; //將後繼狀態的SG函數值進行標記
for(j = 0;; j++) if(!S[j]){ //查詢當前後繼狀態SG值中最小的非零值
SG[i] = j;
break;
}
}
}
Problem Description任何一個大學生對菲波那契數列(Fibonacci numbers)應該都不會陌生，它是這樣定義的：
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2)(n>=3);
所以，1,2,3,5,8,13……就是菲波那契數列。
在HDOJ上有不少相關的題目，比如1005 Fibonacci again就是曾經的浙江省賽題。
今天，又一個關於Fibonacci的題目出現了，它是一個小遊戲，定義如下：
1、 這是一個二人遊戲;
2、 一共有3堆石子，數量分別是m, n, p個；
3、 兩人輪流走;
4、 每走一步可以選擇任意一堆石子，然後取走f個；
5、 f只能是菲波那契數列中的元素（即每次只能取1，2，3，5，8…等數量）；
6、 最先取光所有石子的人為勝者；
假設雙方都使用最優策略，請判斷先手的人會贏還是後手的人會贏。
Input
輸入資料包含多個測試用例，每個測試用例佔一行，包含3個整數m,n,p（1<=m,n,p<=1000）。
m=n=p=0則表示輸入結束。
Output
如果先手的人能贏，請輸出「Fibo」，否則請輸出「Nacci」，每個範例的輸出佔一行。
Sample Input
1 1 1
1 4 1
0 0 0
Sample Output
Fibo
Nacci
標程
#include <stdio.h>
#include <string.h>
#define MAXN 1000 + 10
#define N 20
int f[N],SG[MAXN],S[MAXN];
void getSG(int n){
int i,j;
memset(SG,0,sizeof(SG));
for(i = 1; i <= n; i++){
memset(S,0,sizeof(S));
for(j = 0; f[j] <= i && j <= N; j++)
S[SG[i-f[j]]] = 1;
for(j = 0;;j++) if(!S[j]){
SG[i] = j;
break;
}
}
}
int main()
{
int n,m,k;
f[0] = f[1] = 1;
for(int i = 2; i <= 16; i++)
f[i] = f[i-1] + f[i-2];
getSG(1000);
while(scanf("%d%d%d",&m,&n,&k),m||n||k)
{
if(SG[n]^SG[m]^SG[k]) printf("Fibo\n");//問題的和=子問題SG函數互斥或和
else printf("Nacci\n");
}
return 0;
}
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 785 Accepted Submission(s): 464
Problem Description
Stone Game II comes. It needs two players to play this game. There are some piles of stones on the desk at the beginning. Two players move the stones in turn. At each step of the game the player should do the following operations.
First, choose a pile of stones. (We assume that the number of stones in this pile is n)
Second, take some stones from this pile. Assume the number of stones left in this pile is k. The player must ensure that 0 < k < n and (k XOR n) < n, otherwise he loses.
At last, add a new pile of size (k XOR n). Now the player can add a pile of size ((2*k) XOR n) instead of (k XOR n) (However, there is only one opportunity for each player in each game).
The first player who can’t do these operations loses. Suppose two players will do their best in the game, you are asked to write a program to determine who will win the game.
Input
The first line contains the number T of test cases (T<=150). The first line of each test cases contains an integer number n (n<=50), denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game.
You can assume that all the number of stones in each pile will not exceed 100,000.
Output
For each test case, print the case number and the answer. if the first player will win the game print 「Yes」(quotes for clarity) in a single line, otherwise print 「No」(quotes for clarity).
Sample Input
3
2
1 2
3
1 2 3
4
1 2 3 3
Sample Output
Case 1: No
Case 2: Yes
Case 3: No
題目大意：
給出n堆物品，每堆物品都有若干件，現在A和B進行遊戲，每人每輪操作一次，按照如下規則：
解題思路
把每堆原來a個物品分成兩堆，k和k^ a，證明得，這樣分堆，不會影響二進位制中1的總數的奇偶性，（後面會給出證明）
為什麼要考慮二進位制呢？注意題目中的條件，x^ k<x，所以當x的二進位制表示中只有一個1時就不能再分了。所以終止條件也有了。對於操作，因為是乘二，所以並不影響奇偶性結果。
設一堆數目中二進位制表示1的個數是m，則所有要操作的步驟就是所有的（m-1）加起來。討論這個總數的奇偶性就行了。
如何統計二進位制中1的個數？可以對2不斷取模進行，也可以使用n&(n-1)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
using namespace std;
int m;
int main(){
int T;
scanf("%d",&T);
for(int j=1;j<=T;j++){
scanf("%d",&m);
int n=0,x;
for(int i=1;i<=m;i++){
scanf("%d",&x);
while(x){
n+=(x&1);
x/=2;
}
}
n+=m;
printf("Case %d: ",j);
if(n&1){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int getsg(int n)
{
int count=0;
while(n)
{
n&=(n-1);
count++;
}
return count;
}
int main()
{
int T,n;
cin>>T;
int index=0;
while(T--)
{
cin>>n;
int ans=0,temp;
for(int i=1;i<=n;++i)
{
cin>>temp;
ans+=(getsg(temp)-1);
}
printf("Case %d: ",++index);
if(ans&1) puts("Yes");
else puts("No");
}
return 0;
}
只有一堆n個物品，兩個人輪流從這堆物品中取物，規定每次至少取一個，最多取m個。最後取光者得勝。
顯然，如果n=m+1，那麼由於一次最多隻能取m個，所以，無論先取者拿走多少個，
後取者都能夠一次拿走剩餘的物品，後者取勝。因此我們發現瞭如何取勝的法則：如果
n=（m+1）r+s，（r為任意自然數，s≤m),那麼先取者要拿走s個物品，如果後取者拿走
k（≤m)個，那麼先取者再拿走m+1-k個，結果剩下（m+1）（r-1）個，以後保持這樣的
取法，那麼先取者肯定獲勝。
總之，要保持給對手留下（m+1）的倍數，就能最後獲勝。
這個遊戲還可以有一種變相的玩法：兩個人輪流報數，每次至少報一個，最多報十
個，誰能報到100者勝。
#include <iostream>
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m)
if(n%(m+1)==0) cout<<"後手必勝"<<endl;
else cout<<"先手必勝"<<endl;
return 0;
}
有兩堆各若干的物品，兩人輪流從其中一堆取至少一件物品，至多不限，或從兩堆中同時取相同件物品，規定最後取完者勝利。
直接說結論了，若兩堆物品的初始值為（x，y），且x<y，則令z=y-x；
記w=（int）[（（sqrt（5）+1）/2）*z ]；
若w=x，則先手必敗，否則先手必勝。
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n1,n2,temp;
while(cin>>n1>>n2)
{
if(n1>n2) swap(n1,n2);
temp=floor((n2-n1)*(1+sqrt(5.0))/2.0);
if(temp==n1) cout<<"後手必勝"<<endl;
else cout<<"先手必勝"<<endl;
}
return 0;
}
有一堆物品，兩人輪流取物品，先手最少取一個，至多無上限，但不能把物品取完，之後每次取的物品數不能超過上一次取的物品數的二倍且至少為一件，取走最後一件物品的人獲勝。
結論是：先手勝當且僅當n不是斐波那契數（n為物品總數）
#include<iostream>
#include<cmath>
using namespace std;
int f[100];
void Init()//斐波那契數列
{
f[0]=f[1]=1;
for(int i=2;i<=100;i++)
{
f[i]=f[i-1]+f[i-2];
}
}
int main()
{
int n;
cin>>n;
Init();
bool flag=false;
for(int i=0;f[i];i++)
{
if(f[i]==n)
{
flag=true;
break;
}
}
if(flag)
cout<<"後手必勝"<<endl;
else
cout<<"先手必勝"<<endl;
}
有任意堆物品，每堆物品的個數是任意的，雙方輪流從中取物品，每一次只能從一堆物品中取部分或全部物品，最少取一件，取到最後一件物品的人獲勝。
結論就是：把每堆物品數全部互斥或起來，如果得到的值為0，那麼先手必敗，否則先手必勝。
程式碼如下：
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int main()
{
int n,ans,temp;
while(cin>>n)
{
temp=0;
for(int i=0;i<n;i++)
{
cin>>ans;
temp^=ans;
}
if(temp==0) cout<<"後手必勝"<<endl;
else cout<<"先手必勝"<<endl;
}
return 0;
}
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 45
3 3 6 9
Sample Output
No
Yes
當前為必敗局面 ，當且僅當pile[1]^ pile[2] ^ …pile[n]=0
#include <iostream>
using namespace std;
int main()
{
int M;
while(cin>>M,M)
{
int pile[20];
for(int i=0; i<M; ++i)
{
cin>>pile[i];
}
int result = 0;
for(int i=0; i<M; ++i)
{
result ^= pile[i];
}
if(result)
cout<<"Yes"<<endl;
else
cout<<"No" <<endl;
}
return 0;
}
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2577 Accepted Submission(s): 1400
Problem Description
Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.
Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.
Input
The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.
Constraints:
1 <= T <= 474,
1 <= N <= 47,
1 <= Ai <= 4747
Output
Output T lines each of them containing information about game winner. Print 「John」 if John will win the game or 「Brother」 in other case.
Sample Input
2
3
3 5 1
1
1
Sample Output
John
Brother
這道題有些不一樣，如果John吃的是某個盒子最後一顆，那就判定John為敗。
所以，這道題分為兩種情況討論：
①若所有堆的數量都為1。則根據奇偶來判斷誰勝。
②其他情況，將所有資料互斥或起來，判斷是否為奇異態。
#include <iostream>
#include <algorithm>
using namespace std;
int arr[48];
int main()
{
int t,n,i,temp;
cin>>t;
while( t-- )
{
cin>>n;
for(i=0;i<n;++i)
cin>>arr[i];
sort(arr,arr+n);
// 如果全是1，按照奇偶判斷誰獲勝
if( arr[n-1]==1 )
{
if( n&1 ) cout<<"Brother"<<endl;
else cout<<"John"<<endl;
continue;
}
// 互斥或加起來
temp=0;
for(i=0;i<n;++i)
temp^=arr[i];
if( temp==0 ) cout<<"Brother"<<endl;
else cout<<"John"<<endl;
}
return 0;
}
Understandibly it is no fun to play a game when both players know how to play perfectly (ignorance is bliss). Fourtunately, Arthur and Caroll soon came up with a similar game, S-Nim, that seemed to solve this problem. Each player is now only allowed to remove a number of beads in some predefined set S, e.g. if we have S =(2, 5) each player is only allowed to remove 2 or 5 beads. Now it is not always possible to make the xor-sum 0 and, thus, the strategy above is useless. Or is it?
your job is to write a program that determines if a position of S-Nim is a losing or a winning position. A position is a winning position if there is at least one move to a losing position. A position is a losing position if there are no moves to a losing position. This means, as expected, that a position with no legal moves is a losing position.
Input
Input consists of a number of test cases. For each test case: The first line contains a number k (0 < k ≤ 100 describing the size of S, followed by k numbers si (0 < si ≤ 10000) describing S. The second line contains a number m (0 < m ≤ 100) describing the number of positions to evaluate. The next m lines each contain a number l (0 < l ≤ 100) describing the number of heaps and l numbers hi (0 ≤ hi ≤ 10000) describing the number of beads in the heaps. The last test case is followed by a 0 on a line of its own.
Output
For each position: If the described position is a winning position print a ‘W’.If the described position is a losing position print an ‘L’. Print a newline after each test case.
Sample Input
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
Sample Output
LWW
WWL
題目大意：
就是首先給你一個數s,輸入s個數的集合，接下來的操作只能取與這集合相對應的石子，接下來一行輸入一個數m,表示
m次操作，然後輸入一個n,表示有n堆石子，如果先手勝出輸出L,否則輸出W,當然得一連串輸出這m個字母。
思路:運用sg函數和xor處理
#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
using namespace std;
const int maxn=10010;
int sg[maxn],oper[maxn],temp[maxn],k[maxn];
int s;
void getsg()
{
memset(sg,0,sizeof(sg));
for(int i=0;i<10010;i++){
memset(temp,0,sizeof(temp));
for(int j=0;j<s&&oper[j]<=i;j++){
temp[sg[i-oper[j]]]=1;//如果到達的前一點均為必勝，那麼這個點為必敗
} //否則為必勝
for(int j=0;j<=s;j++){//深入瞭解你會發現sg會使一個週期
if(temp[j]==0){//如果都出現了，那麼不會進行賦值了，為必敗
sg[i]=j;//如果有第一個必敗點，那麼記錄下來，這個點變為必勝點
break;
}
}
}
}
int main()
{
char p[1005];
int m,a,b,c;
string str;
while(scanf("%d",&s),s){
for(int i=0;i<s;i++) scanf("%d",&oper[i]);
getsg();
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d",&a);
scanf("%d",&c);
c=sg[c];//互斥或操作就是將每堆石子進行互斥或，
for(int j=1;j<a;j++){
scanf("%d",&b);
c=c^sg[b];
}
if(c==0) p[i]='L';如果互斥或值為零
else p[i]='W';
}
printf("%s\n",p);
}
}
這種題與以往的博弈題的勝負條件不同，誰先走完最後一步誰輸，但他也是一類Nim遊戲，即為anti-nim遊戲。
首先給出結論：先手勝當且僅當 ①所有堆石子數都為1且遊戲的SG值為0（即有偶數個孤單堆-每堆只有1個石子數）；②存在某堆石子數大於1且遊戲的SG值不為0.
證明：
若所有堆都為1且SG值為0，則共有偶數堆石子，故先手勝。
i)只有一堆石子數大於1時，我們總可以對該石子操作，使操作後堆數為奇數且所有堆的石子數均為1；
ii)有超過一堆的石子數1時，先手將SG值變為0即可，且總還存在某堆石子數大於1
1
2
3
4
因為先手勝。
此題用到的概念：
【定義1】：若一堆中僅有一個石子，則被稱為孤單堆。若大於1個，則稱為充裕堆。
【定義2】：T態中，若充裕堆的堆數大於等於2，則稱為完全利他態，用T2表示；若充裕堆的堆數等於0，則稱為部分利他態。用T0表示。
孤單堆的根數互斥或智慧影響二進位制的最後以為，但充裕堆會影響高位（非最後一位）。一個充裕堆，高位必有一位不為0，則所有根數互斥或不為0。故不會是T態。
【定理1】：S0態，即僅有奇數個孤單堆，必敗。T0態必勝。
證明：S0態，其實就是每次只能取一根。每次第奇數根都由自己取，第偶數根都由對方取，所以最後一根必由自己取。所以必敗。同理：T0態必勝。
【定理2】：S1態，只要方法正確，必勝。
證明：若此時孤單堆堆數為奇數，把充裕堆取完；否則，取成一根。這樣，就變成奇數個孤單堆，由對方取。由定理1，對方必輸，己必勝。
【定理3】：S2態不可轉一次變為T0態。
證明：充裕堆數不可能一次由2變為0。
【定理4】：S2態可一次轉變為T2態。
證明：因為對於任何一個S態，總能從一堆中取出若干個使之成為T態。又因為S1態，只要方法正確，必勝。S2態不可轉一次變為T0態，所以轉變的T態為T2態。
【定理5】：T2態，只能轉變為S2態或S1態。
證明：因為T態，取任何一堆的若干根都將成為S態。由於充裕堆不可能一次由2變為0，所以此時的S態不可能為S0態。得證。
【定理6】：S2態，只要方法正確，必勝。
證明：方法如下：
S2態，就把它變為T2態。（定理4）；
對方只能T2轉變為S2態或S1態（定理5）。
若轉變為S2，則轉向①。
若轉變為S1，這時己必勝（定理1）。
1
2
3
4
5
6
【定理7】：T2態必輸。
證明：同定理6.
綜上所述：必輸態有：T2、S0；必勝態有：S2、S1、T0。
#include<iostream>
using namespace std;
int main()
{
int i,n,m;
while(cin >> n)
{
int flag = 0; //判斷是否是孤單堆
int s = 0;
for(i = 0;i < n;i++)
{
cin >> m;
s ^= m;
if(m > 1)
flag = 1;
}
if(flag == 0)
if(n % 2)
cout << "No\n";
else
cout << "Yes\n";
else
if(s == 0)
cout << "No" <<endl;
else
cout << "Yes" <<endl;
}
return 0;
}
Problem Description
Let’s consider m apples divided into n groups. Each group contains no more than 100 apples, arranged in a line. You can take any number of consecutive apples at one time.
For example 「@@@」 can be turned into 「@@」 or 「@」 or 「@ @」(two piles). two people get apples one after another and the one who takes the last is
the loser. Fra wants to know in which situations he can win by playing strategies (that is, no matter what action the rival takes, fra will win).
Input
You will be given several cases. Each test case begins with a single number n (1 <= n <= 100), followed by a line with n numbers, the number of apples in each pile. There is a blank line between cases.
Output
If a winning strategies can be found, print a single line with 「Yes」, otherwise print 「No」.
Sample Input
2
2 2
1
3
Sample Output
No
Yes
題目大意：有n堆蘋果，每堆有mi個。兩人輪流取，每次可以從一堆蘋果中取任意連續個蘋果（取完後一堆可能變成了2堆），最後取光者為輸。Fra先下，問是否可以獲勝。
#include<iostream>
using namespace std;
int main()
{
int i,n,m;
while(cin >> n)
{
int flag = 0; //判斷是否是孤單堆
int s = 0;
for(i = 0;i < n;i++)
{
cin >> m;
s ^= m;
if(m > 1)
flag = 1;
}
if(flag == 0)
if(n % 2)
cout << "No\n";
else
cout << "Yes\n";
else
if(s == 0)
cout << "No" <<endl;
else
cout << "Yes" <<endl;
}
return 0;
}