首页 > 代码库 > 组合博弈
组合博弈
博弈，一般就是，sg啊，dfs极大极小搜索啊，dp啊，找规律啊....
HDU 1847 Good Luck in CET-4 Everybody!(SG水题)
预处理一下，不然会RE。
HDU 4559 涂色游戏
这个题，非常棒...看了别人的思路，n个1个格子的sg为n%2，我们利用sg函数处理出2＊i的值，然后把给出的矩形分段。
#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <iostream>using namespace std;int dp[5001];int p[3][5001];int sg(int x){ int i,l,r; int o[5001]; if(dp[x] >= 0) return dp[x]; memset(o,0,sizeof(o)); for(i = 1;i <= x;i ++) { l = i-1;//染1＊1的方格 r = x-i; o[sg(l)^sg(r)^1] = 1; if(i+1 <= x)//枚举在那里染2＊2的方格 { l = i-1; r = x-i-1; o[sg(l)^sg(r)] = 1; } } for(i = 0;;i ++) { if(!o[i]) return dp[x] = i; } return 0;}int main(){ int n,m,x,y,i,t,cas = 1,ans,flag; memset(dp,-1,sizeof(dp)); dp[0] = 0; dp[1] = 0; for(i = 2;i <= 5000;i ++) { sg(i); } scanf("%d",&t); while(t--) { memset(p,0,sizeof(p)); scanf("%d%d",&n,&m); for(i = 0;i < m;i ++) { scanf("%d%d",&x,&y); p[x][y] = 1; } ans = (2*n-m)&1; flag = 0; for(i = 1;i <= n;i ++) { if(!p[1][i]&&!p[2][i]) flag ++; else { ans ^= dp[flag]; flag = 0; } } ans ^= dp[flag]; printf("Case %d: ",cas++); if(ans) printf("Alice\n"); else printf("Bob\n"); } return 0;}
HDU 1760 A New Tetris Game
极大极小dfs
#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <iostream>using namespace std;char str[50][50];int p[50][50];int n,m;int dfs(){ int i,j,flag; flag = 0; for(i = 0;i < n-1;i ++) { for(j = 0;j < m-1;j ++) { if(p[i][j] == 0&&p[i+1][j] == 0&&p[i][j+1] == 0&&p[i+1][j+1] == 0) { p[i][j] = p[i+1][j] = p[i][j+1] = p[i+1][j+1] = 1; if(dfs() == 0) flag = 1; p[i][j] = p[i+1][j] = p[i][j+1] = p[i+1][j+1] = 0; } } } if(flag) return 1; else return 0;}int main(){ int i,j; while(scanf("%d%d",&n,&m)!=EOF) { for(i = 0; i < n; i ++) scanf("%s",str[i]); for(i = 0; i < n; i ++) { for(j = 0; j < m; j ++) { if(str[i][j] == ‘0‘) p[i][j] = 0; else p[i][j] = 1; } } if(dfs()) printf("Yes\n"); else printf("No\n"); } return 0;}
HDU 3951 Coin Game
这题先不考虑有环的情况，长度为n的sg会比较好求，暴力出sg会发现，除了k = 1之外，其他情况的k，dp[i] >= 1,无论第一步怎么选，肯定是要变化为一段的情况。
搜了一下题解，发现大家直接搞出了 策略，后手可以搞出对称的策略，用sg对不对啊，应该也没问题吧...
#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <iostream>using namespace std;int dp[1001];int n;int sg(int x){ int i,j; if(dp[x] >= 0) return dp[x]; int o[1001]; memset(o,0,sizeof(o)); for(i = 1;i <= x;i ++) { for(j = 1;j <= n;j ++) { if(x-j-(i-1) < 0) continue; o[sg(i-1)^sg(x-j-(i-1))] = 1; } } for(i = 0;;i ++) if(!o[i]) return dp[x] = i;}int main(){ int t,k,cas = 1; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); printf("Case %d: ",cas++); if(k == 1) { if(n%2) printf("first\n"); else printf("second\n"); } else { if(n <= k) printf("first\n"); else printf("second\n"); } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。