传播网站建设,重庆城乡建设信息网官网,Wordpress 当天文章更新数,手机端开发网站模板下载组合博弈学习笔记 说在前边 下面的博弈题目基本就是sg函数#xff0c;搜必败必胜态#xff0c;找规律#xff0c;推策略。。。没有对理论进行深入了解。HDU1527 搜索时发现#xff0c;必败态的数对貌似有规律#xff0c;首先他们的大小两个数的差值是逐个增加的。然后搜必败必胜态找规律推策略。。。没有对理论进行深入了解。HDU1527 搜索时发现必败态的数对貌似有规律首先他们的大小两个数的差值是逐个增加的。然后差分打表发现差值为1或者2.实在找不到规律了OEIS了一发是个黄金分割学到了。 //**黄金分割**
//**a(n) floor(n*phi), where phi (1sqrt(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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--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(x0y0) 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;
}
vectorint v;
int main() {
//**
// rep(i,1,550) rep(j,1,i) {
// if(!dfs(i,j))printf((%d,%d) %d\n,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(ab) 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去重直接用maphash二进制压位。 #include cstdio
#include algorithm
#include cstring
#include map
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
typedef unsigned long long ull;
const int N 55;
const int mod 1000007;
using namespace std;
int n,m;
mapull,bool s;
char mp[N][N];
bool ck(int x,int y) {if(x1x1ny1y1m) {if(mp[x][y]0mp[x][y1]0mp[x1][y]0mp[x1][y1]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[x1][y] mp[x][y1] mp[x1][y1] 1;
}
void del(int x,int y) {mp[x][y] mp[x1][y] mp[x][y1] mp[x1][y1] 0;
}
ull HS() { //hash 好好写ull hs 0;rep(i,1,n) rep(j,1,m)if(mp[i][j]0)hs | (1LL((i-1LL)*mj-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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--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(1i)))vis[sg[s - (1i)]] 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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
using namespace std;//***
int dfs(int n,int x) {if(n0)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();
}
//***vectorll v;
void init() {ll f0 1, f1 1, f2 2;while(f2(1LL32LL)) {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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--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-(ik-1)0) {vis[sg[i-1]^sg[s-(ik-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);//对于一根链//当k1时奇数必胜//当k大于1时大于0就必胜//**int T,C0;scanf(%d,T);while(T--) {ll n; int K;scanf(%lld%d,n,K);printf(Case %d: ,C);if(K1) {if((n-1)%21)puts(second);else puts(first);}else {if(nK) 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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 4750;
using namespace std;
int T,C0,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*1if(i1s) {li-1; rs-(i1);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;t0t1ans0;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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--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(x1) 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 ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define MP make_pair
#define PII pairint,int
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
mapPII,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(xy)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;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9404862.html
