博弈论
2019-09-28 本文已影响0人
云中翻月
博弈DP
POJ 1082: Calendar Game
从最终状态向前dp即可。
注意如下两点：
1 需要保证前后的状态均合法，例如f[i,j,k+1]=>f[i,j,k]则需要保证(i,j,k+1)和(i,j,k)这两个日期都合法。
2 因为日期是增加，所以要从后往前推，即循环逆序。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
从最终状态向前dp即可。
注意如下两点：
1 需要保证前后的状态均合法，例如f[i,j,k+1]=>f[i,j,k]则需要保证(i,j,k+1)和(i,j,k)这两个日期都合法。
2 因为日期是增加，所以要从后往前推，即循环逆序。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxy=2000+5;
const int maxm=12+5;
const int maxd=31+5;
const int month[][13]={0,31,28,31,30,31,30,31,31,30,31,30,31,
0,31,29,31,30,31,30,31,31,30,31,30,31};
const int INF=0x3f3f3f3f;
int T,y,m,d,f[maxy][maxm][maxd]={0};
int leap(int year){
if(year%400==0||(year%4==0&&year%100!=0)) return 1;
return 0;
}
void pre(){
f[2001][11][4]=0;
for(int i=2001;i>=1900;i--){
int flag=leap(i),nxt_flag=leap(i+1);
for(int j=12;j>=1;j--){
if(i==2001&&j==12) continue;
for(int k=month[flag][j];k>=1;k--){
if(i==2001&&j>=11&&k>4) continue;
//加一个月
if(j+1<=12&&k<=month[flag][j+1]&&(i<2001||(i==2001&&j+1<11)||(i==2001&&j+1==11&&k<=4)))
f[i][j][k]|=!f[i][j+1][k];
if(j==12&&k<=month[nxt_flag][1]&&(i+1<=2001))
f[i][j][k]|=!f[i+1][1][k];
//加一天
if(k+1<=month[flag][j]&&(i<2001||(i==2001&&j<11)||(i==2001&&j==11&&k+1<=4)))
f[i][j][k]|=!f[i][j][k+1];
if(k==month[flag][j]&&j+1<=12&&(i<2001||(i==2001&&j+1<=11)))
f[i][j][k]|=!f[i][j+1][1];
if(k==month[flag][j]&&j==12&&(i+1<=2001))
f[i][j][k]|=!f[i+1][1][1];
}
}
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("Calendar Game.in","r",stdin);
pre();
cin>>T;
while(T--){
cin>>y>>m>>d;
if(f[y][m][d]) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 2068: Nim
题解链接 http://www.mamicode.com/info-detail-2131299.html
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
题解链接 http://www.mamicode.com/info-detail-2131299.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10+5;
const int maxs=(1<<13)+5;
const int INF=0x3f3f3f3f;
int d[maxn<<1][maxs],n,s,a[maxn<<1];
void init(){
memset(d,-1,sizeof(d));
}
int dfs(int x,int y){ //轮到第i个人，还剩j个石子的胜负情况
if(d[x][y]!=-1) return d[x][y];
if(y==0) return d[x][y]=1;
for(int i=1;i<=a[x]&&i<=y;i++){
if(!dfs(x%(2*n)+1,y-i)) return d[x][y]=1; //后继状态有一个必败 该状态必胜
}
return d[x][y]=0; //后继状态都必胜 该状态必败
}
int main() {
ios::sync_with_stdio(false);
//freopen("Nim.in","r",stdin);
while(cin>>n){
if(!n) break;
cin>>s;
for(int i=1;i<=2*n;i++) cin>>a[i];
init();
cout<<dfs(1,s)<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3688: Cheat in the Game
题解链接 http://www.hankcs.com/program/algorithm/poj-3688-cheat-in-the-game.html
注意每轮结束，石头数都会复原，因此博弈dp时每个卡片每轮中只能使用一次，即对应01背包的情况。
因为总共有四种状态（必败 必胜 非必败 非必胜）所以直接按照传统的转移会出现问题。
代码如下
/*
题解链接 http://www.hankcs.com/program/algorithm/poj-3688-cheat-in-the-game.html
注意每轮结束，石头数都会复原，因此博弈dp时每个卡片每轮中只能使用一次，即对应01背包的情况。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxm=100000+5;
const int INF=0x3f3f3f3f;
int n,m,d[maxm][2],ans,a[maxn];
void dp(){
d[0][0]=1;
for(int i=1;i<=n;i++) for(int j=m;j>=a[i];j--) { //01背包 保证每个数字只能使用一次
if(d[j-a[i]][0]==1) d[j][1]=1;
if(d[j-a[i]][1]==1) d[j][0]=1;
}
}
void init(){
ans=0;
memset(d,0,sizeof(d));
}
int main() {
// ios::sync_with_stdio(false);
//freopen("Cheat in the Game.in","r",stdin);
while(cin>>n>>m){
if(!n&&!m) break;
init();
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
// sort(a+1,a+n+1);
dp();
for(int i=1;i<=m;i++) if(d[i][1]&&(!d[i][0])){
// D(i);
ans++;
}
cout<<ans<<endl;
}
return 0;
}
POJ 1740: A New Stone Game
题解链接 https://www.cnblogs.com/s1124yy/p/5702694.html
代码如下
/*
题解链接 https://www.cnblogs.com/s1124yy/p/5702694.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10+5;
const int maxm=100+5;
const int INF=0x3f3f3f3f;
int n,a[maxm];
int main() {
ios::sync_with_stdio(false);
//freopen("A New Stone Game.in","r",stdin);
while(cin>>n){
if(!n) break;
int flag=0;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
if(n&1) flag=1;
else{
for(int i=1;i<=n;i+=2) if(a[i+1]!=a[i]) flag=1;
}
cout<<flag<<endl;
}
return 0;
}
Nim和Grundy数
POJ 2975: Nim
设所有元素异或和为XOR，a[i]是原先的值，XOR^a[i]是为了让抑或值为0，必须将a[i]变成的值。
如果a[i]>=(XOR^a[i])，则可以通过改变a[i]来使得局面达到一个必败状态。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
设所有元素异或和为XOR，a[i]是原先的值，XOR^a[i]是为了让抑或值为0，必须将a[i]变成的值。
如果a[i]>=(XOR^a[i])，则可以通过改变a[i]来使得局面达到一个必败状态。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1000+5;
const int INF=0x3f3f3f3f;
int n,a[maxn],XOR,ans;
void init(){
XOR=ans=0;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Nim.in","r",stdin);
while(cin>>n){
if(!n) break;
init();
for(int i=1;i<=n;i++) cin>>a[i],XOR^=a[i];
if(XOR!=0){
for(int i=1;i<=n;i++) if(a[i]>=(XOR^a[i])) ans++;
//a[i]是原先的值 XOR^a[i]是为了让抑或值为0 必须将a[i]变成的值
}
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ 3537: Crosses and Crosses
题解链接 https://www.cnblogs.com/neighthorn/p/6441252.html
注意vis要声明为局部变量，因为它只在这一层中有效。
代码如下
/*
题解链接 https://www.cnblogs.com/neighthorn/p/6441252.html
注意vis要声明为局部变量，因为它只在这一层中有效。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2000+5;
const int INF=0x3f3f3f3f;
int sg[maxn],n;
void init(){
memset(sg,-1,sizeof(sg));
sg[0]=0;
}
int dfs(int x){
if(sg[x]!=-1) return sg[x];
bool vis[maxn]; //注意vis要声明为局部变量 因为它只在这一层中有效
memset(vis,0,sizeof(vis));
for(int i=1;i<=x;i++) vis[dfs(max(0,i-3))^dfs(max(x-i-2,0))]=1;
for(int i=0;;i++) if(!vis[i]) return sg[x]=i;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Crosses and Crosses.in","r",stdin);
cin>>n;
init();
dfs(n)==0?cout<<"2":cout<<"1";
// for(int i=1;i<=n;i++) D(sg[i]);
return 0;
}
POJ 2315: Football Game
题解链接 http://www.hankcs.com/program/algorithm/poj-2315-football-game.html
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
题解链接 http://www.hankcs.com/program/algorithm/poj-2315-football-game.html
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=30+5;
const int logL=27+5; //log2(100000000)=27
const int INF=0x3f3f3f3f;
const double pi=acos(-1.0);
int n,m,l,r,XOR[logL],s[maxn];
void init(){
memset(XOR,0,sizeof(XOR));
}
int dis(int s){
return ((int)(s/(pi*r*2))+1);
}
bool solve(){
int k=dis(l); //最大的石子堆数
for(int i=1;i<=n;i++){
int num=dis(s[i])%k; //额外的石子不管 降低时间复杂度
int cnt=0;
while(num){
XOR[++cnt]+=num&1;
num>>=1;
}
}
for(int i=1;i<=logL-5;i++) if(XOR[i]%(m+1)) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Football Game.in","r",stdin);
while(cin>>n>>m>>l>>r){
init();
for(int i=1;i<=n;i++) cin>>s[i];
solve()?cout<<"Alice"<<endl:cout<<"Bob"<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
