博弈論基礎練習
1.P4101 [HEOI2014]人人盡說江南好
題目描述：
略
題目分析：
由題意可知
N
N
N為初始小石子堆數，且每堆數量為
1
1
1，
在合并時，合并后每堆數量不可超過
M
M
M，獲勝的標志當前所有的堆對方無法繼續操作，
于是可以知道，當可操作堆數為奇數時，我方獲勝，否則對方獲勝，所以若使后繼結果對己方為最優，則選擇每次移動數量最少的堆，
可得
A
N
S
=
(
N
M
o
d
M
)
?
(
M
?
1
)
ANS=(N Mod M)*(M-1)
ANS=(NModM)?(M?1)
A
N
S
+
=
(
(
N
M
o
d
M
)
?
1
)
∣
0
ANS+=((N Mod M )-1)|0
ANS+=((NModM)?1)∣0
CODE：
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
int ans[10010];
int QRead(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main(){
int T=QRead(),a,b;
for(int i=1;i<=T;++i){
a=QRead(),b=QRead();
ans[i]=(b-1)*(a/b);
if(a%b) ans[i]+=a%b-1;
ans[i]%=2;
}
for(int i=1;i<=T;++i){
if(ans[i])printf("0\n");
else printf("1\n");
}
return 0;
}反思與總結:
- 博弈論題目首先需要判斷必勝（或必敗）的條件
2.P5675 [GZOI2017]取石子游戲
題目描述：
略
題目分析：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/267442.html
標籤：其他
上一篇：LDU20級新生排位賽第二場
下一篇：acwing6數的進制轉換