今天讲了博弈论的相关知识，感觉很注重思维和模型积累的是SG函数，应该是需要多做题才可以熟练掌握。
聚聚帮忙列出了几种应该掌握的博弈模型：
- 巴什博弈
- 威佐夫博弈
- 斐波那契博弈
- 尼姆博弈
- 阶梯博弈
- Nim博弈的第二种形式
- 树上博弈
下来总结今日学习的题目：
A - Playing With Stones
题意：n堆stones，一次最多只能取走一半stones，stone为1时失败，先手是否胜利。
Thinking:
- 打表法找出SG函数的规律。
- 用亦或表示P-N状态。
- 利用多组Nim博弈的结论进行判断。
#include <cstdio>
#include <cstring>
#define LL long long
const int maxn = 1e3+10;
/*
int SG[maxn], S[maxn];
void getSG(int n){
memset(SG, 0, sizeof(SG));
//sg[0]=0; sg[1]=0;
for(int i=2; i<=n; i++){
memset(S, 0, sizeof(S));
for(int j=1; j*2<=i; j++){
S[SG[i-j]] = 1;
}
for(int j=0; ;j++){
if(!S[j]){
SG[i] = j;
break;
}
}
}
}
int main(){
getSG(100);
for(int i=1; i<=50; i++){
if(i%10==0) printf("\n");
printf("%d ",SG[i]);
}
return 0;
}
*/
LL getsg(LL n){
return n%2 ? getsg(n/2) : n/2;
}
int main(){
int T,N;
scanf("%d",&T);
for(int t=0; t<T; t++){
scanf("%d",&N);
LL ans = 0;
for(int i=0; i<N; i++){
LL tmp;
scanf("%lld",&tmp);
ans ^= getsg(tmp);
}
if(ans){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
B - 悼念512汶川大地震遇难同胞——选拔志愿者
C - Public Sale
Thinking:
很明显的巴什博弈。
策略：一堆n个石子，最多取m个，最少1个，A先手。 n%(m+1)==0 :B胜； 否则A开始取n-n/(m+1)*(m+1)个石子，之后石子和始终为(m+1),即A胜。
#include <cstdio>
int main(){
int C;
scanf("%d",&C);
for(int c=0; c<C; c++){
int n,m;
scanf("%d%d",&n, &m);
if(n%(m+1) == 0){
printf("Rabbit\n");
}else{
printf("Grass\n");
}
}
return 0;
}
#include <cstdio>
int main(){
int n,m;
while( scanf("%d%d",&m,&n) != EOF){
if(m%(n+1) == 0){
printf("none\n");
}else if(m <= n){
for(int i=m; i<=n; i++){
printf("%d%s",i,i==n?"\n":" ");
}
}else{
printf("%d\n",m-(m/(n+1))*(n+1));
}
}
return 0;
}
D - No Gambling
认真读题就好了
题意：
给定两个N*N由红点和蓝点构成的完全对称的图，两个人轮流连边，每次只能对相邻同颜色两点连一条边且不能穿过对方所连的线，先手对蓝点连边，从左到右获胜，后手对红点连边，从上到下获胜，问谁胜谁负。
#include <cstdio>
int main(){
int n;
while(scanf("%d",&n) && (n+1)){
printf("I bet on Oregon Maple~\n");
}
return 0;
}
E - Good Luck in CET-4 Everybody!
Thinking:
开始产生错误思路：看到2的幂，想到利用数的二进制和位运算来判断，但发现当n=21=1+4+16时答案错误。
正解：sg打表找规律。关于规律为3的倍数先手胜利的思考：这是保证最后的1由先手来取，先手操作时始终保持留给对手的是3的倍数即可。
/*
int f[11];
bool sg[1005];
void init(){
f[0]=1;
for(int i=1; i<=10; i++) f[i] = f[i-1]*2;
for(int i=1; i<=1000; i++){
for(int j=0; f[j]<=i; j++){
if(!sg[i-f[j]]){
sg[i]=true;
break;
}
}
}
}
*/
#include <cstdio>
int main(){
int n;
while(scanf("%d",&n) != EOF){
if(n%3==0){
printf("Cici\n");
}else{
printf("Kiki\n");
}
}
return 0;
}
F - Coin Game
题意： 将给定的n个硬币排成一圈，两人轮流取硬币，每次只能取连续的1到k个硬币，问先手胜还是负。
如果能够把游戏分成对称的两部分，那么先手在某一部分里做了某个操作，后手就可以在另一部分里做和它同样的操作。最后肯定是先手先结束他自己的那一部分，后手再结束另一部分，那么后手就胜利了。
#include <cstdio>
int main(){
int T;
scanf("%d",&T);
for(int t=1; t<=T; t++){
int n,k;
scanf("%d%d",&n, &k);
if(k==1 && (n%2==1)){
printf("Case %d: first\n",t);
}else if(n <= k){
printf("Case %d: first\n",t);
}else{
printf("Case %d: second\n",t);
}
}
return 0;
}
G - 取石子游戏
斐波那契博弈。
/*
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int sg[maxn][maxn];
int dfs(int x, int y){
if(sg[x][y] != -1) return sg[x][y];
set<int> s;
s.clear();
for(int i=1; i<=y; i++){
if(x-i >= 0){
s.insert(sg[x-i][2*i]);
}
}//属于这个集合的非负整数
for(int i=0; ;i++){
if(s.count(i) == 0){
sg[x][y] = i;
break;
}
}//不属于这个集合的最小非负整数 //这里用set()//A题用的是类似与hash的方法
return sg[x][y];
}
int main()
{
memset(sg, -1, sizeof(sg));
for(int i=1; i<=1000; i++){
sg[0][i] = 0;
sg[1][i] = 1;
}
for(int i=2; i<=100; i++){
for(int j=1; j<=100; j++){
sg[i][j] = dfs(i, j);
}
}
for(int i=1; i<=30; i++){
for(int j=1; j<=30; j++){
printf("%2d ",sg[i][j]);
}
cout << endl;
}
bool flag = true;
for(int i=1; i<=100; i++){
for(int j=1; j<i; j++){
if(sg[i][j]!=0){
flag=false; break;
}
}
if(flag){
cout << i << endl;
flag = true;
}else{
flag = true;
}
}
return 0;
}
*/
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 50;
LL f[maxn];
void fib(){
f[1]=1; f[2]=2;
for(int i=3; i<maxn; i++){
f[i] = f[i-1] + f[i-2];
}
}
int main(){
fib();
LL n;
while(scanf("%lld",&n) != EOF && (n!=0)){
if(lower_bound(f, f+50, n)-f>=50 || f[lower_bound(f, f+50, n)-f]!=n){
printf("First win\n");
}else{
printf("Second win\n");
}
}
return 0;
}
H - Nim or not Nim?
题意：Alice和Bob轮流取石子，每一次可以从任意一堆中拿走任意个石子，也可将一堆石子分为两个小堆。求必胜策略。
SG函数打表找规律。
#include <cstdio>
#include <cstring>
/*
const int N = 1e6+5;
int vis[N], sg[N];
void getSG(){
memset(sg, 0, sizeof(sg));
sg[0] = 0;
sg[1] = 1;
for(int i=1; i<100; i++){
memset(vis, 0, sizeof(vis));
for(int j=1; j<=i; j++){
vis[sg[i-j]] = 1;
}//移走任意个石子
for(int j=1; j<i; j++){
vis[sg[j]^sg[i-j]] = 1;
} //将石子分为两堆
for(int j=0; ; j++){
if(!vis[j]){
sg[i] = j;
break;
}
}
printf("%d %d\n", i, sg[i]);
}
}
*/
int getsg(int n){
if(n%4==3) return n+1;
else if(n%4==0) return n-1;
else return n;
}
int main(){
int T;
scanf("%d", &T);
for(int t=0; t<T; t++){
int N,ans = 0;
scanf("%d", &N);
for(int i=0; i<N; i++){
int tmp;
scanf("%d", &tmp);
ans ^= getsg(tmp);
}
if(ans == 0){
printf("Bob\n");
}else{
printf("Alice\n");
}
}
return 0;
}
K - Being a Good Boy in Spring Festival
题意：有m堆牌，两个人先后取某堆中的任意（不少于一）张牌，最后取完者胜；问先手取胜第一次取牌有多少种取法。
Thinking:
利用亦或的性质，可以看成是自反性吧，然后逆着思考 必胜的情况下 首次操作 可以对哪些堆，可以保证亦或和为0；并且要符合实际，即 所取数量<=已有数量（此题小于也可以过，=应该更严谨吧）
#include <cstdio>
int a[105];
int main(){
int m;
while( scanf("%d",&m)!=EOF && m ){
int ans = 0;
for(int i=0; i<m; i++){
scanf("%d",&a[i]);
ans ^= a[i];
}
if(ans == 0){
printf("0\n");
}else{
int num=0;
for(int j=0; j<m; j++){
if((ans^a[j]) <= a[j]){
num++;
}
}
printf("%d\n",num);
}
}
return 0;
}
L - 取(m堆)石子游戏
Nim博弈，与K相似。
#include <cstdio>
const int maxm = 200005;
int a[maxm];
int main(){
int m;
while( scanf("%d",&m)!=EOF && m ){
int ans=0;
for(int i=0; i<m; i++){
scanf("%d", &a[i]);
ans ^= a[i];
}
if(ans == 0){
printf("No\n");
}else{
printf("Yes\n");
for(int i=0; i<m; i++){
int tmp = ans^a[i];
if(tmp <= a[i]){
printf("%d %d\n", a[i], tmp);
}
}
}
}
return 0;
}
M - 取石子游戏
Thinking:
很直接的威佐夫博弈，由此题可知积累模型的重要性，否则，这个题打表肉眼恐怕很难找到规律。
#include <cstdio>
#include <cmath>
int main(){
int a,b;
while(scanf("%d%d", &a, &b)!=EOF){
if(a > b){
int t=a; a=b; b=t;
}
int i = b-a;
b = (int)((sqrt(5.0)+1.0)/2.0*i);
if(a==b) printf("0\n");
else printf("1\n");
}
return 0;
}