博弈论
四大基础博弈
转跳链接
转跳1
转跳2
HDU 1546(SG函数)
题目要求
首先输入K 表示一个集合的大小 之后输入集合 表示对于这对石子只能去这个集合中的元素的个数
之后输入 一个m 表示接下来对于这个集合要进行m次询问
之后m行 每行输入一个n 表示有n个堆 每堆有n1个石子 问这一行所表示的状态是赢还是输 如果赢输入W否则L
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| const double eps = 1e-6; const LL mod=1e9+7; const LL INF=(LL)1e18; using namespace std; LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);} LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;} bool hashh[maxn]; int sg[maxn],s[150]; int t; void sg_solve(){ mm(sg,0); int j; for(int i=1;i<=maxn;i++){ mm(hashh,0); for(j=0;j<t;j++){ if(i-s[j]>=0) hashh[sg[i-s[j]]]=1; } for(j=0;j<=maxn;j++){ if(!hashh[j]) break; } sg[i]=j; } } int main(){ // freopen("input.txt","r",stdin); // freopen("ouput.txt","w",sdout); ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); while(cin>>t){ if(t==0) break; string ans; for(int i=0;i<t;i++) cin>>s[i]; sg_solve(); int n; cin>>n; for(int i=1;i<=n;i++){ int m; cin>>m; int res=0; for(int j=1;j<=m;j++){ int h; cin>>h; res^=sg[h]; } ans+=res?'W':'L'; } cout<<ans<<endl; } return 0; }
|
思路
SG模版
威佐夫博弈的变形