博弈論
- SG函式
- SG函式的定義
- SG函式的和
- 定理
- get_GS
- 例題
- Fibonacci again and again
- Good Luck in CET-4 Everybody!
- Stone Game II hoj4388
- 巴什博奕（Bash Game）
- 例題
- HDU 1846 Brave Game
- 威佐夫博弈（Wythoff Game）
- 斐波那契博弈
- 尼姆博奕（Nimm Game）
- 例題
- POJ 2234 Matches Game
- HDU1907 John
- HDU1536 S-Nim
- A Multiplication Game
- Being a Good Boy in Spring Festival
- Rabbit and Grass
- Anti_min問題
- 模板
- 例題
- HDU 2509 Be the Winner
- 對稱博弈
- A Funny Game
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;
}
Good Luck in CET-4 Everybody!
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 18791 Accepted Submission(s): 11771
Problem Description
大學英語四級考試就要來臨了，你是不是在緊張的復習？也許緊張得連短學期的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能有好的狀態，
Input
輸入資料包含多個測驗用例，每個測驗用例占一行，包含一個整數n（1<=n<=1000），
Output
如果Kiki能贏的話，請輸出“Kiki”，否則請輸出“Cici”，每個實體的輸出占一行，
Sample Input
1
3
Sample Output
Kiki
Cici
Author
lcy
#include <stdio.h>
#include <string.h>
#define MAXN 1000 + 10
#define N 200
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;
f[0] =1;
for(int i = 1; i <= 16; i++)
f[i] = f[i-1]*2;
getSG(1005);
while(scanf("%d",&n)!=EOF)
{
if(SG[n]) printf("Kiki\n");
else printf("Cici\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;
}
例題
HDU 1846 Brave Game
Problem Description
十年前讀大學的時候，中國每年都要從國外引進一些電影大片，其中有一部電影就叫《勇敢者的游戲》（英文名稱：Zathura），一直到現在，我依然對于電影中的部分電腦特技印象深刻，
今天，大家選擇上機考試，就是一種勇敢（brave）的選擇；這個短學期，我們講的是博弈（game）專題；所以，大家現在玩的也是“勇敢者的游戲”，這也是我命名這個題目的原因，
當然，除了“勇敢”，我還希望看到“誠信”，無論考試成績如何，希望看到的都是一個真實的結果，我也相信大家一定能做到的~
各位勇敢者要玩的第一個游戲是什么呢？很簡單，它是這樣定義的：
1、 本游戲是一個二人游戲;
2、 有一堆石子一共有n個；
3、 兩人輪流進行;
4、 每走一步可以取走1…m個石子；
5、 最先取光石子的一方為勝；
如果游戲的雙方使用的都是最優策略，請輸出哪個人能贏，
Input
輸入資料首先包含一個正整數C(C<=100)，表示有C組測驗資料，
每組測驗資料占一行，包含兩個整數n和m（1<=n,m<=1000），n和m的含義見題目描述，
Output
如果先走的人能贏，請輸出“first”，否則請輸出“second”，每個實體的輸出占一行，
Sample Input
2
23 2
4 3
Sample Output
first
second
#include <iostream>
using namespace std;
int main()
{
int n,m,t;
cin>>t;
while(t--){
cin>>n>>m;
if(n%(m+1)==0) cout<<"second"<<endl;
else cout<<"first"<<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);
}
}
A Multiplication Game
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8593 Accepted Submission(s): 4819
Problem Description
Stan and Ollie play the game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Stan always starts with p = 1, does his multiplication, then Ollie multiplies the number, then Stan and so on. Before a game starts, they draw an integer 1 < n < 4294967295 and the winner is who first reaches p >= n.
Input
Each line of input contains one integer number n.
Output
For each line of input output one line either
Stan wins.
or
Ollie wins.
assuming that both of them play perfectly.
Sample Input
162
17
34012226
Sample Output
Stan wins.
Ollie wins.
Stan wins.
必敗點(P點) :前一個選手(Previous player)將取勝的位置稱為必敗點，
必勝點(N點) :下一個選手(Next player)將取勝的位置稱為必勝點，
對于這兩個概念的描述，我開始的時候也搞不懂，
其實可以從字面理解，簡單說來，就是當你走到某一點的時候，如果你無論怎么走也不能贏對方，此時你必敗，這個點就叫做必敗點，
演算法實作：
步驟1:將所有終結位置標記為必敗點（P點）；（終結位置指的是不能將游戲進行下去的位置）
步驟2:將所有一步操作能進入必敗點（P點）的位置標記為必勝點（N點）
步驟3:如果從某個點開始的所有一步操作都只能進入必勝點（N點） ，則將該點標記為必敗點（P點） ；
步驟4:如果在步驟3未能找到新的必敗（P點），則演算法終止；否則，回傳到步驟2，
好了，下面通過這道題來理解下吧，
題意：
你和一個人玩游戲，給你一個數字n，每次操作可以從2~9中任選一個數字，并把它與p相乘，（游戲開始時p=1）
兩人輪流操作，當一個人操作完后p>=n，這個人就是勝者，
解題思路：
由于每次都是從p=1開始的，所以只要判斷每個游戲中1為必敗點還是必勝點即可，（以下各式 / 均為取上整）
依照上面所提到的演算法，將終結位置，即[n,無窮]標記為必敗點；
然后將所有一步能到達此必敗段的點標記為必勝點，即[n/9,n-1]為必勝點；
然后將只能到達必勝點的點標記為必敗點，即[n/9/2,n/9-1]為必敗點；
重復上面2個步驟，直至可以確定1是必勝點還是必敗點，
#include <math.h>
#include <stdio.h>
int main()
{
unsigned int n,x;
while(~scanf("%u",&n))
{
for(x=0;n>1;x++)
{
if(x&1)//x&1實作兩個操作交替運行
n = ceil(n*1.0/2);
else
n = ceil(n*1.0/9);
}
puts(x&1?"Stan wins.":"Ollie wins.");
}
return 0;
}
ceil()函式的使用
// 假設最終數為 162，為了防止對方得到大于等于 162的數，則上一步，一方應該讓數盡量不大于 162 /
// 9 = 18，如果大于等于 18，則對方可以乘以 9 即可大于等于 162，再往上一步，一方應該盡量選擇將數
// 相乘后得到大于等于 9 的數，因為這樣，另一方無論選擇那個乘數，終將導致乘積大于等于 18，因為 9 /
// 9 = 1，即誰先乘，誰將獲勝，
// 對于給定的數N，對于 Stan 來說，先達到數 N，則是勝利，回歸到上一步，如果 Stan 先達到 N / 9，
// 則失敗，繼續上一步，若 Stan 先達到 N / 9 / 2，則勝利，使用遞回解決即可，
#include <iostream>
#include <cmath>
using namespace std;
void ones(int number, bool win)
{
if (number <= 9 && win)
{
cout << "Stan wins." << endl;
return;
}
if (number <= 2 && !win)
{
cout << "Ollie wins." << endl;
return;
}
if (win)
ones(ceil(number / 9.0), !win);
else
ones(ceil(number / 2.0), !win);
}
int main(int ac, char *av[])
{
int number;
while (cin >> number)
ones(number, true);
return 0;
}
Being a Good Boy in Spring Festival
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11882 Accepted Submission(s): 7319
Problem Description
一年在外 父母時刻牽掛
春節回家 你能做幾天好孩子嗎
寒假里嘗試做做下面的事情吧
陪媽媽逛一次菜場
悄悄給爸爸買個小禮物
主動地 強烈地 要求洗一次碗
某一天早起 給爸媽用心地做回早餐
如果愿意 你還可以和爸媽說
咱們玩個小游戲吧 ACM課上學的呢～
下面是一個二人小游戲：桌子上有M堆撲克牌；每堆牌的數量分別為Ni(i=1…M)；兩人輪流進行；每走一步可以任意選擇一堆并取走其中的任意張牌；桌子上的撲克全部取光，則游戲結束；最后一次取牌的人為勝者，
現在我們不想研究到底先手為勝還是為負，我只想問大家：
——“先手的人如果想贏，第一步有幾種選擇呢？”
Input
輸入資料包含多個測驗用例，每個測驗用例占2行，首先一行包含一個整數M(1<M<=100)，表示撲克牌的堆數，緊接著一行包含M個整數Ni(1<=Ni<=1000000，i=1…M)，分別表示M堆撲克的數量，M為0則表示輸入資料的結束，
Output
如果先手的人能贏，請輸出他第一步可行的方案數，否則請輸出0，每個實體的輸出占一行，
Sample Input
3
5 7 9
0
Sample Output
1
思路：可選步數為任意步，SG(x) = x;
本題中每一堆都可以選任意個，所以每一堆的SG值都是所剩余的個數，
最后結果是所有堆的SG值異或的結果，令ans = 所有堆的SG值異或的結果
如果ans == 0，則是必敗點，
如果ans != 0，使取后結果為0的策略是必勝策略
具體怎么取呢？
每一堆的數值與ans相異或，所得的結果就是這一堆可以取的數量，
但是，如要這一堆數量沒有這么多，就不可以這么取
#include <iostream>
using namespace std;
int value[101];
int main ()
{
int n,ans,count,i;
while (cin>>n && n)
{
ans=0;
for (i=0;i<n;i++)
{
cin>>value[i];
ans^=value[i];
}
count=0;
for (i=0;i<n;i++)
{
ans^=value[i]; //用到了一個很明顯的結論：a = a ^ b ^ b;
if (value[i]>ans) count++; //當前堆有足夠多的牌，方案數++
ans^=value[i];
}
cout<<count<<endl;
}
return 0;
}
Rabbit and Grass
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1088 Accepted Submission(s): 816
Problem Description
大學時光是浪漫的，女生是浪漫的，圣誕更是浪漫的，但是Rabbit和Grass這兩個大學女生在今年的圣誕節卻表現得一點都不浪漫：不去逛商場，不去逛公園，不去和AC男約會，兩個人竟然貓在寢食下棋……
說是下棋，其實只是一個簡單的小游戲而已，游戲的規則是這樣的：
1、 棋盤包含1*n個方格，方格從左到右分別編號為0，1，2，…，n-1；
2、 m個棋子放在棋盤的方格上，方格可以為空，也可以放多于一個的棋子；
3、 雙方輪流走棋；
4、 每一步可以選擇任意一個棋子向左移動到任意的位置（可以多個棋子位于同一個方格），當然，任何棋子不能超出棋盤邊界；
5、 如果所有的棋子都位于最左邊（即編號為0的位置），則游戲結束，并且規定最后走棋的一方為勝者，
對于本題，你不需要考慮n的大小（我們可以假設在初始狀態，棋子總是位于棋盤的適當位置），下面的示意圖即為一個1*15的棋盤，共有6個棋子，其中，編號8的位置有兩個棋子，
大家知道，雖然偶爾不夠浪漫，但是Rabbit和Grass都是冰雪聰明的女生，如果每次都是Rabbit先走棋，請輸出最后的結果，
Input
輸入資料包含多組測驗用例，每個測驗用例占二行，首先一行包含一個整數m（0<=m<=1000），表示本測驗用例的棋子數目，緊跟著的一行包含m個整數Ki(i=1…m; 0<=Ki<=1000)，分別表示m個棋子初始的位置，m=0則結束輸入，
Output
如果Rabbit能贏的話，請輸出“Rabbit Win!”，否則請輸出“Grass Win!”，每個實體的輸出占一行，
Sample Input
2
3 5
3
3 5 6
0
Sample Output
Rabbit Win!
Grass Win!
Author
lcy
距離轉為NIM，將每一堆直接放在最左邊
#include<iostream>
#include<cstdlib>
#include<stdio.h>
using namespace std;
int main()
{
int n,num;
while(scanf("%d",&n)&&n)
{
int ans=0;
for(int i=0;i<n;i++)
{
scanf("%d",&num);
ans^=num;
}
if(ans) puts("Rabbit Win!");
else puts("Grass Win!");
}
}
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;
}
對稱博弈
A Funny Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 8649 Accepted: 5320
Description
Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 <= n <= 106) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, leaving all other coins untouched. At least one coin must be removed. Players alternate moves with Alice starting. The player that removes the last coin wins. (The last player to move wins. If you can’t move, you lose.)
Figure 1
Note: For n > 3, we use c1, c2, …, cn to denote the coins clockwise and if Alice remove c2, then c1 and c3 are NOT adjacent! (Because there is an empty place between c1 and c3.)
Suppose that both Alice and Bob do their best in the game.
You are to write a program to determine who will finally win the game.
Input
There are several test cases. Each test case has only one line, which contains a positive integer n (1 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input.
Output
For each test case, if Alice win the game,output “Alice”, otherwise output “Bob”.
Sample Input
1
2
3
0
Sample Output
Alice
Alice
Bob
Source
POJ Contest,Author:Mathematica@ZSU
思路：
對于n<=2，先手ALICE必勝，n>3時，無論Alice怎么取，BOB都可以取一定的數目來構造出中心對稱，這樣BOB一定是最后一次取光的，
當n > 3 時，無論A怎么選擇，B可以選一個特殊的位置拿走1個連續的2個，將A取剩的環路剪成兩條相同的鏈路，然后，無論A從那條鏈路中那個位置取幾個，B都可以在另一條鏈路中采用相同的取法，此時，B慢A一步，即最后一個一定是B取到的，B必勝！
#include <stdio.h>
int main()
{
int n;
while(scanf("%d", &n), n){
if(n <= 2)
printf("Alice\n");
else
printf("Bob\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/163363.html
標籤：其他
上一篇：CodeForces - 1422D Returning Home （建圖 + 最短路）
下一篇：C++解決背包問題