组合博弈学习笔记
说在前边
- 下面的博弈题目基本就是sg函数，搜必败必胜态，找规律，推策略。。。没有对理论进行深入了解。
HDU1527
搜索时发现，必败态的数对貌似有规律，首先他们的大小两个数的差值是逐个增加的。然后，差分打表，发现差值为1或者2.实在找不到规律了，OEIS了一发，是个黄金分割，学到了。
//**黄金分割**
//**a(n) = floor(n*phi), where phi = (1+sqrt(5))/2
//**1,3,4,6,8,9,11,12,14,16,17,19,21,22,24,25,27,29,30,32,33,35,37
//**特点: 在i附近，貌似有规律地浮动
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
typedef long long ll;
using namespace std;
bool f[1101][1011],vis[1112][1101];
int dfs(int x,int y) {
if(x==0&&y==0) return 0;
if(vis[x][y]) return f[x][y];
vis[x][y]=vis[y][x]=1;
rep(i,1,x) if(!dfs(x-i,y)) return f[x][y]=f[y][x]=1;
rep(i,1,y) if(!dfs(x,y-i)) return f[x][y]=f[y][x]=1;
rep(i,1,min(x,y)) if(!dfs(x-i,y-i)) return f[x][y]=f[y][x]=1;
return f[x][y]=f[y][x]=0;
}
vector<int> v;
int main() {
//**
// rep(i,1,550) rep(j,1,i) {
// if(!dfs(i,j))printf("(%d,%d) = %d
",i,j,dfs(i,j)),v.pb(j);//**第i对数之间差i
// }
// cout << (sqrt(5)+1)/2.0 << endl;
// rep(i,0,(int)v.size()-1) {
// printf("%d, ",v[i]);
// }puts("");
//**
ll a,b;
while(scanf("%lld%lld",&a,&b) != EOF) {
if(a>b) swap(a,b);
ll t = b-a;
ll ta = floor((sqrt(5.0)+1.0)*t/2.0);
if(ta == a) puts("0");
else puts("1");
}
return 0;
}
HDU1760
直接搜索即可，hash去重直接用map，hash二进制压位。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
typedef unsigned long long ull;
const int N = 55;
const int mod = 1000007;
using namespace std;
int n,m;
map<ull,bool> s;
char mp[N][N];
bool ck(int x,int y) {
if(x>=1&&x+1<=n&&y>=1&&y+1<=m) {
if(mp[x][y]=='0'&&mp[x][y+1]=='0'&&mp[x+1][y]=='0'&&mp[x+1][y+1]=='0')
return 1;
return 0;
}
return 0;
}
bool ack() {
rep(i,1,n-1)rep(j,1,m-1)if(ck(i,j))return 1;
return 0;
}
void put(int x,int y) {
mp[x][y] = mp[x+1][y] = mp[x][y+1] = mp[x+1][y+1] = '1';
}
void del(int x,int y) {
mp[x][y] = mp[x+1][y] = mp[x][y+1] = mp[x+1][y+1] = '0';
}
ull HS() { //hash 好好写
ull hs = 0;
rep(i,1,n) rep(j,1,m)if(mp[i][j]=='0')
hs |= (1LL<<((i-1LL)*m+j-1LL));
return hs;
}
int dfs() {
ull hs = HS();
if(s.find(hs)!=s.end()) return s[hs];
if(!ack()) return s[hs]=0;
int ans = 0;
rep(i,1,n-1)rep(j,1,m-1) if(ck(i,j)){
put(i,j);
if(!dfs()) ans |= 1;
del(i,j);
}
return s[hs]=ans;
}
int main() {
while(scanf("%d%d",&n,&m) != EOF) {
rep(i,1,n) scanf(" %s",mp[i]+1);
s.clear();
if(dfs())puts("Yes");
else puts("No");
}
return 0;
}
HDU1847
直接预处理sg函数即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
typedef long long ll;
const int N = 1010;
using namespace std;
int n, sg[N];
bool vis[N];
void init() {
sg[0] = 0;
rep(s,1,1000) {
memset(vis,0,sizeof(vis));
rep(i,0,10)if((s>=(1<<i)))
vis[sg[s - (1<<i)]] = 1;
rep(i,0,1000) if(!vis[i]) {
sg[s] = i;break;
}
}
}
int main() {
init();
while(scanf("%d",&n)!=EOF) {
if(sg[n] == 0) puts("Cici");
else puts("Kiki");
}
return 0;
}
HDU2516
记忆化搜索必败态，必胜态，发现满足斐波那契数列。之前的dp写法我自己都没看懂。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
typedef long long ll;
using namespace std;
//***
int dfs(int n,int x) {
if(n==0)return 0;
rep(i,1,min(2*x,n)) if(!dfs(n-i,i)) return 1;
return 0;
}
int cal(int n) {
rep(i,1,n-1) if(!dfs(n-i,i)) return 1;
return 0;
}
void _init(int n) {
rep(i,2,n) if(!cal(i)) printf("%d ",i);puts("");
}
//***
vector<ll> v;
void init() {
ll f0 = 1, f1 = 1, f2 = 2;
while(f2<(1LL<<32LL)) {
v.pb(f2);
f0 = f1; f1 = f2; f2 = f1 + f0;
}
// for(auto x: v)printf("%lld ",x);puts("");
}
int main() {
//**
//_init(50);
//**
init();
ll n;
while(scanf("%lld",&n),n) {
if(*lower_bound(v.begin(),v.end(),n)==n)puts("Second win");
else puts("First win");
}
return 0;
}
HDU3951
直接暴力求一根链情况下的sg函数，然后发现长度大于1必胜。环的情况就很容易了。还有一种思路是对称的取硬币可以证明后手必胜。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
typedef long long ll;
const int N = 1e3 + 7;
using namespace std;
int sg[N],vis[N];
void init(int K) {
sg[0] = 0;
rep(s,1,100) {
memset(vis,0,sizeof(vis));
rep(k,1,K) rep(i,1,s) {
if(s-(i+k-1)>=0) {
vis[sg[i-1]^sg[s-(i+k-1)]]=s;
}
}
rep(i,0,100) if(vis[i]!=s){
sg[s]=i;break;
}
}
rep(s,1,100)printf("%d ",sg[s]);puts("");
}
int main() {
//**
//rep(i,1,10)init(i);
//对于一根链
//当k=1时，奇数必胜
//当k大于1时，大于0就必胜
//**
int T,C=0;
scanf("%d",&T);
while(T--) {ll n; int K;
scanf("%lld%d",&n,&K);
printf("Case %d: ",++C);
if(K==1) {
if((n-1)%2==1)puts("second");
else puts("first");
}
else {
if(n<=K) puts("first");
else puts("second");
}
}
return 0;
}
HDU4559
将格子拆为 2×i 的格子与 1×1 的格子的组合，把他们分别处理sg值然后异或起来。对于 1×1 的格子，sg值就是1，对于2*i的格子，可以直接求sg值，具体写法见代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
typedef long long ll;
const int N = 4750;
using namespace std;
int T,C=0,n,m,sg[N],vis[N],num[N];
void init() {
sg[0] = sg[1] = 0;
rep(s,2,4747) {
rep(i,1,s) {
int l = i-1, r = s-i;
vis[sg[l]^1^sg[r]]=s; // 1*1
if(i+1<=s) {
l=i-1; r=s-(i+1);
vis[sg[l]^sg[r]]=s; // 2*2
}
}
rep(i,0,4747) if(vis[i]!=s){
sg[s] = i; break;
}
}
}
int solve() {
int t0, t1, ans;
t0=t1=ans=0;
rep(i,1,n) {
if(num[i] == 1) t1^=1;
if(num[i] == 0) ++t0;
else {
ans^=sg[t0];
t0 = 0;
}
}
(ans^=sg[t0])^=t1;
return ans;
}
int main() {
init();
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
rep(i,0,n) num[i]=vis[i]=0;
rep(i,1,m) {int x,y;
scanf("%d%d",&x,&y);
++num[y];
}
printf("Case %d: ",++C);
if(solve()) puts("Alice");
else puts("Bob");
}
return 0;
}
HDU4642
每次反转一个位置右下角一定会翻转一次，如果Alice将它反转为0，则Bob一定会将它反转为1，则最后一定是Alice赢。反之同理。所以直接判最后一位是0还是1即可
#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
typedef long long ll;
using namespace std;
int n,m;
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);int x;
rep(i,1,n)rep(j,1,m) scanf("%d",&x);
if(x==1) puts("Alice");
else puts("Bob");
}
return 0;
}
HDU5963
与上一题思路基本一致，子节点的修改都会对根节点上的对应边进行反转，所以直接判那条边是否为1即可，多条边，直接判断奇偶。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define MP make_pair
#define PII pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
map<PII,int> M;
int n,m,d[44444];
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
rep(i,1,n) d[i]=0; M.clear();
rep(i,1,n-1) {int x,y,z;
scanf("%d%d%d",&x,&y,&z);
d[x]+=z;d[y]+=z;
if(x > y) swap(x,y);
M[MP(x,y)] = z;
}
rep(i,1,m) {int opt,x,y,z;
scanf("%d",&opt);
if(opt) {
scanf("%d%d%d",&x,&y,&z);
if(x>y)swap(x,y);
int t = M[MP(x,y)];
d[x]+=z; d[y]+=z;
d[x]-=t; d[y]-=t;
M[MP(x,y)] = z;
}
else {
int x;
scanf("%d",&x);
if(d[x]%2)puts("Girls win!");
else puts("Boys win!");
}
}
}
return 0;
}