博弈論
- SG函式
- SG函式的定義
- SG函式的和
- 定理
- get_GS
- 例題
- Fibonacci again and again
- Stone Game II hoj4388
- 巴什博奕（Bash Game）
- 威佐夫博弈（Wythoff Game）
- 斐波那契博弈
- 尼姆博奕（Nimm Game）
- 例題
- POJ 2234 Matches Game
- HDU1907 John
- HDU1536 S-Nim
- Anti_min問題
- 模板
- 例題
- HDU 2509 Be the Winner
SG函式
SG函式的定義
先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表最小的不屬于這個集合的非負整數，例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0，
SG函式的和
游戲的和的SG函式值等于他包含的各個子游戲SG函式值的異或和
定理
游戲的某個局面必勝，當且僅當該局面對應節點的SG函式值大于0
游戲的某個局面必敗，當且僅當該局面對應節點的SG函式值等于0
get_GS
//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;
}
}
}
例題
Fibonacci again and again
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;
}
Stone Game II hoj4388
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進行游戲，每人每輪操作一次，按照如下規則：
- 任意選擇一個堆，假設該堆有x個物品，從中選擇k個，要保證0<k<x且0<(x^ k)<x，
- 再增加一個大小為x^ k的堆（也就相當于將一個x個物品的堆變成一個k個物品的堆和一個x^ k個物品的堆），另外有一個技能，可以將這個大小為x^ k的堆變成(2*k)^x的堆，但是這個技能每個人只有一次機會可以使用，
- 現在問兩人輪流操作，都采取最優策略，最后不能操作的人輸，問誰會贏，
解題思路
把每堆原來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;
}
巴什博奕（Bash Game）
只有一堆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;
}
威佐夫博弈（Wythoff Game）
有兩堆各若干的物品，兩人輪流從其中一堆取至少一件物品，至多不限，或從兩堆中同時取相同件物品，規定最后取完者勝利，
直接說結論了，若兩堆物品的初始值為（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;
}
尼姆博奕（Nimm Game）
有任意堆物品，每堆物品的個數是任意的，雙方輪流從中取物品，每一次只能從一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人獲勝，
結論就是：把每堆物品數全部異或起來，如果得到的值為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;
}
例題
POJ 2234 Matches Game
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;
}
HDU1907 John
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;
}
HDU1536 S-Nim
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);
}
}
Anti_min問題
這種題與以往的博弈題的勝負條件不同，誰先走完最后一步誰輸，但他也是一類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;
}
例題
HDU 2509 Be the Winner
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/162782.html
標籤：java
上一篇：CodeForces - 1422D Returning Home （建圖 + 最短路）
下一篇：一道題解釋樹形dp【此后無良辰】