博弈论小结-白红宇

博弈论小结

阅读量：5327 次

发布时间：2019-06-14

本文共 12261 字，大约阅读时间需要 40 分钟。

这几天充分感受了被博弈论支配的恐惧……

首先是参考资料：

学长的一些课件……就不放了

然后

还有这个dalao的模型总结挺好的，种类也不少……

然后……具体模型sg函数sj定理以及各种诡异的游戏请看上面的参考资料……我只是瞎扯一些做题的感想

首先学了下极大极小搜索以及配套的alpha-beta剪枝

虽然……并不是我当时做的的正解……

但是这种思想很好，尤其是剪枝的时候

我们在搜的时候保留之前祖先节点的上界下界，如果不可能更新最优解了直接跳出。

大概贴的代码……那个原题是在栈里面取东西所以代码打成这样了

1 int f[N][N<<1][2]; 2 inline int min(int a,int b){
    return a
      
       b?a:b;} 4 inline int searching(int player,int layer,int limit,int down,int up) 5 { 6     if(layer>n)return 0; 7     if(f[layer][limit][player]!=-1)return f[layer][limit][player]; 8     register int i,lim=min(layer+limit-1,n),v; 9     for(i=layer;i<=lim;++i)10     {11         v=searching(player^1,i+1,(i-layer+1)<<1,down,up);12         if(!player)down=max(down,v);13         else up=min(up,v);14         if(down>up)break;15     }16     return f[layer][limit][player]=(player?up:down);17 }

极大极小

然后我们来说说的正解：博弈DP

博弈DP在转移的时候利用了一个东西：由于两个人都是绝顶聪明的，所以面临同样状态时决策一定会是相同的

然后对于本题的转移方程，由于对手一定会取最有利的局面，因此我们转移的时候不能取max而要取min……

看一下代码：

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define N 2010 5 inline int min(int a,int b){
    return a
        
         b?a:b;} 7 int f[N][N],n,val[N]; 8 int main() 9 {10     // freopen("Ark.in","r",stdin);11     register int i,j;scanf("%d",&n);12     for(i=1;i<=n;++i)scanf("%d",&val[i]);13     for(i=n;i;--i)val[i]+=val[i+1];14     for(i=1;i<=n;++i)15         for(j=1;j<=n;++j)16         {17             f[i][j]=f[i][j-1];18             if(i-2*j+1>=0)f[i][j]=max(f[i][j],val[n-i+1]-f[i-2*j+1][2*j-1]);19             if(i-2*j>=0)f[i][j]=max(f[i][j],val[n-i+1]-f[i-2*j][2*j]);20         }21     printf("%d\n",f[n][1]);22 }

bzoj2017

接着……

这题以及后面的某些题大概是对每个下标的元素计算sg函数值，然后异或

这可能是一种解题技巧……

对于本题，对于下标i，我们考虑所有在i操作之后影响到的状态的mex值，

即我们找出所有操作之后受影响的元素，把他们异或起来作为状态，然后再取mex

因为sg函数计算就是对到达的状态取mex嘛……

代码：

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define N 25 5 int n,sg[N]; 6 inline int read() 7 { 8     int x=0;register char c=getchar(); 9     while(c<'0'||c>'9')c=getchar();10     while(c>='0'&&c<='9')x=10*x+(c^48),c=getchar();11     return x;12 }13 bool vis[40];14 inline int get(int id)15 {16     register int i,j;17     memset(vis,0,sizeof(vis));18     for(i=id+1;i

bzoj1188

然后再来一道也是sg和下标有关的……

我们认为……这样的翻硬币类似物游戏中每个白点是独立的

也就是说我们把每个下标的sg值都异或起来然后判断即可

至于怎么算……这道题我们使用除法分块来做

由于后面n/2长度的sg值相等，那么他们前面一段的sg值也相等，这样推到前面去，在同一个除法分块块里面的下标sg值都相等

所以我们就可以用根本跑不满的$O(n)$来打这道题了！

代码：

1 #include 
      
        2 #include 
       
                                                                                                                                                                                                 3 #include 
        
          4 #include 
         
           5 using namespace std; 6 #define N 66000 7 bool vis[1010]; 8 int len,hd[N],tot,cnt,l[N],r[N],sg[N],f[N]; 9 inline void init(int n)10 {11     register int i,j,cur,val,last;12     for(i=1;i<=n;i=last+1)13         hd[++tot]=last=n/(n/i);14     r[0]=n,cnt=0;15     for(i=tot;i;--i)16     {17         val=0,cur=cnt;18         for(last=j=2;j<=n/hd[i];j=last+1)19         {20             while(cur&&j*hd[i]>r[cur])--cur;21             last=r[cur]/hd[i];22             vis[val^f[cur]]=1;23             if((last-j+1)&1)val^=f[cur];24             vis[val]=1;25         }26         for(j=1;vis[j];++j);27         sg[i]=f[++cnt]=j;28         if(cnt>1&&f[cnt]==f[cnt-1])l[--cnt]=hd[i-1]+1;29         else l[cnt]=hd[i-1]+1,r[cnt]=hd[i];30         memset(vis,0,sizeof(vis));31     }32 }33 inline int gsg(int pos)34     {
    return sg[upper_bound(hd+1,hd+tot+1,pos)-hd-1];}35 int main()36 {37     // freopen("Ark.in","r",stdin);38     register int i,j,t,n,a,ans;39     scanf("%d%d",&len,&t);40     init(len);41     while(t--)42     {43         scanf("%d",&n),ans=0;44         for(i=1;i<=n;++i)45             scanf("%d",&a),ans^=gsg(len/(len/a));46         puts(ans?"Yes":"No");47     }48 }

bzoj4035

然后……下面这道题和sg函数并没有什么关系……

然后呢……我们发现照题意这样操作，一次操作的后继状态就太！多！了！

于是我们考虑手玩小样例可能这也是解题技巧吧2333

总之结论是”原石子可以被分成完全相同的2堆“的时候先手必败

至于具体的证明……

我们采取什么操作，我们对手就利用和我们取的那个石子堆对称的那堆进行操作就行了，完全模仿即可。

然后如果不完全相同，我们可以用最大的那堆去把其他的补齐，使得他们能成为完全相同的2组，然后把最大的扔到跟最小的相等

这时候我们对手就必败了……

然后代码也很简单啦……

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 char B[1<<15],*S=B,*T=B; 6 #define getc (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++) 7 inline int read() 8 { 9     int x=0;register char c=getc;10     while(c<'0'||c>'9')c=getc;11     while(c>='0'&&c<='9')x=10*x+(c^48),c=getc;12     return x;13 }14 int a[100010];15 int main()16 {17     // freopen("Ark.in","r",stdin); 18     register int n,i,j;19     for(n=read(),i=1;i<=n;++i)a[i]=read();20     for(sort(a+1,a+n+1),i=1;i<=n;++i)21         if(a[i]!=a[i+1]){puts("first player");return 0;}22     puts("second player");return 0;23 }

bzoj1982

然后做了个……似乎很有理有据的证明，大家想看可以去上面的参考资料找。

不过这题好毒啊，竟然要打ETT

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 using namespace std;  7 char B[1<<15],*S=B,*T=B;  8 #define getc (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)  9 inline int read() 10 { 11     int x=0;register char c=getc; 12     while(c<'0'||c>'9')c=getc; 13     while(c>='0'&&c<='9')x=10*x+(c^48),c=getc; 14     return x; 15 } 16 #define N 100010 17 int n,lim,e,adj[N],fa[N],deep[N],val[N]; 18 struct edge{
    int zhong,next;}s[N]; 19 inline void add(int qi,int zhong) 20     {s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;} 21 struct node 22 { 23     node *ch[2],*f; 24     int val,val0,val1,deep; 25     node(){val0=val1=0;} 26     inline void update() 27     { 28         val0=ch[0]->val0^ch[1]->val0; 29         val1=ch[0]->val1^ch[1]->val1; 30         if(deep&1)val0^=val;else val1^=val; 31     } 32 }*null,*root,mem[N<<1],*l[N],*r[N],*sta[N<<1],*tp; 33 inline void init() 34 { 35     null=new node(); 36     null->ch[0]=null->ch[1]=null->f=null; 37     null->val=null->val0=null->val1=0; 38 } 39 int top,tot; 40 inline bool isroot(node *o){
    return o->f==tp;} 41 inline int son(node *o){
    return o->f->ch[1]==o;} 42 inline node* newnode(int val,node *f,int dp) 43 { 44     node *o=mem+(tot++); 45     o->ch[0]=o->ch[1]=null,o->f=f; 46     o->deep=dp,o->val=val; 47     if(dp&1)o->val0=val;else o->val1=val; 48     return o; 49 } 50 inline void dfs(int rt) 51 { 52     deep[rt]=deep[fa[rt]]+1; 53     l[rt]=newnode(val[rt],null,deep[rt]);sta[++top]=l[rt]; 54     for(int i=adj[rt];i;i=s[i].next)dfs(s[i].zhong); 55     r[rt]=newnode(0,null,deep[rt]);sta[++top]=r[rt]; 56 } 57 inline void rotate(node *o) 58 { 59     node *fa=o->f,*grand=fa->f; 60     int k=son(o),kk=son(fa); 61     fa->ch[k]=o->ch[k^1]; 62     if(o->ch[k^1]!=null)o->ch[k^1]->f=fa; 63     o->ch[k^1]=fa,fa->f=o,o->f=grand; 64     if(grand!=null)grand->ch[kk]=o; 65     fa->update(),o->update(); 66 } 67 inline void splay(node *o,node *towards) 68 { 69     for(tp=towards;!isroot(o);rotate(o)) 70         if(!isroot(o->f))rotate(son(o)==son(o->f)?o->f:o); 71 } 72 inline node* getpre(node *o) 73 { 74     splay(o,null),o=o->ch[0]; 75     while(o->ch[1]!=null)o=o->ch[1]; 76     return o; 77 } 78 inline node* getback(node *o) 79 { 80     splay(o,null),o=o->ch[1]; 81     while(o->ch[0]!=null)o=o->ch[0]; 82     return o; 83 } 84 inline node* get_range(node* a,node* b) 85 { 86     node *o=getpre(a),*oo=getback(b); 87     splay(o,null),splay(oo,o);return oo->ch[0]; 88 } 89 inline node* build(int l,int r) 90 { 91     if(l>r)return null; 92     register int mi=l+r>>1; 93     sta[mi]->ch[0]=build(l,mi-1),sta[mi]->ch[1]=build(mi+1,r); 94     if(sta[mi]->ch[0]!=null)sta[mi]->ch[0]->f=sta[mi]; 95     if(sta[mi]->ch[1]!=null)sta[mi]->ch[1]->f=sta[mi]; 96     sta[mi]->update();return sta[mi]; 97 } 98 inline int query(int id) 99 {100     int ret;101     node *o=get_range(l[id],r[id]);102     if(deep[id]&1)ret=o->val1!=0;103     else ret=o->val0!=0;104     puts(ret?"MeiZ":"GTY");105     return ret;106 }107 inline void update(int id,int v)108 {109     splay(l[id],null);110     l[id]->val=val[id]=v;111     l[id]->update();112 }113 inline void insert(int f,int id)114 {115     node *o=getpre(r[f]);116     splay(r[f],null),splay(o,r[f]);117     l[id]=newnode(val[id],null,deep[id]);118     r[id]=newnode(0,null,deep[id]);119     l[id]->ch[1]=r[id],r[id]->f=l[id],l[id]->update();120     o->ch[1]=l[id];l[id]->f=o;o->update();121 }122 int main()123 {124     // freopen("Ark.in","r",stdin);125     register int i,a,b,c,m,cnt=0,opt;126     n=read(),lim=read();127     for(i=1;i<=n;++i)val[i]=read()%(lim+1);128     for(i=1;i

bzoj3729

然后是……参考资料里面有

在会了那个结论之后还是比较裸的，dp一发求个方案数再转概率就行了

有这样一句话比较好“在博弈论中凡是等价的状态都是可以相互替换的”，正因如此我们可以把之前那一堆树枝替换成一条“竹子”

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define N 110 5 #define db double 6 #define K 128 7 int n; 8 db f[N][K<<1],g[N][K<<1]; 9 bool vis[N][K<<1];10 inline void init()11 {12     register int i,j,u,v,cnt=1;13     vis[1][0]=1;g[1][0]=1;db tmp;14     for(i=2;i<=100;++i)15     {16         for(u=0;u

bzoj2688

以及，当然上面的资料里面也是有的

这也很好的解释了为什么普通的min游戏是异或：

异或之后每一位的值是原本1的个数x%(1+1)之后的值

也就是说异或啦，有偶数个1是0，奇数个1是1

上面那个方法总结的博客里介绍了证明……

似乎我这样扔资料不太负责任啊2333

我们可以和之前那道参考一下……

然后我们就发现这俩题都是那样棋子转nim的模型，不过这题是nimk而已

打就好了……拿组合数Dp一下方案数

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define N 10010 5 #define N1 10000 6 #define K 110 7 #define mod 1000000007 8 #define LL long long 9 int bin[25],n,k,d;10 LL f[17][N],fac[N],inv[N];11 inline LL C(int a,int b){
    return a

bzoj2281

然后最后来一道二分图博弈……

关于二分图博弈，一个特点就是我们每个点只能走一次

经常和棋盘黑白染色转二分图搞在一起

必胜和必败常常与二分图的交错轨和匹配边联系在一起：

nim游戏中我们对于2堆一样的石子会模仿对手的操作，然后对于二分图类博弈我们从对手的点出发走匹配边

也是在模仿对手啦……只有对方能走，我们就能走他那个点出去的匹配边，所以是资瓷的

然后经常要考虑是最大匹配的”必须点“还是”非必须点“

前者可以通过从最大匹配的非匹配点dfs得到，后者可以删掉这个点，看看自己的匹配点还能不能找到匹配

然后当时我搞的时候看了，写的很不错……

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 #define N 45 5 #define G 1610 6 #define K 1010 7 int n,m,opt[K<<1],k,ans[K],top; 8 int stcol,id[N][N],v[N][N],col[N][N],cnt; 9 char str[N];10 int e,adj[G],match[G];11 struct edge{
    int zhong,next;}s[G<<2];12 inline void add(int qi,int zhong)13     {s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}14 int vis[G],T;15 bool del[G];16 inline bool find(int rt)17 {18     if(del[rt])return false;19     register int i,u,x;20     for(i=adj[rt];i;i=s[i].next)21         if(vis[u=s[i].zhong]!=T)22         {23             vis[u]=T;24             if(del[u])continue;25             if(!match[u]||find(match[u]))26                 {match[rt]=u,match[u]=rt;return true;}27         }28     return false;29 }30 inline bool judge(int rt)31 {32     del[rt]=1;33     if(!match[rt])return 0;34     int tofind=match[rt];35     ++T,match[rt]=match[tofind]=0;36     return find(tofind)==0;37 }38 int main()39 {40     // freopen("Ark.in","r",stdin);41     register int i,j,a,b;42     scanf("%d%d",&n,&m);43     for(i=1;i<=n;++i)44         for(j=1;j<=m;++j)col[i][j]=((i+j)&1);45     for(i=1;i<=n;++i)46         for(scanf("%s",str+1),j=1;j<=m;++j)47         {48             if(str[j]=='.')a=i,b=j,stcol=col[i][j];49             v[i][j]=(str[j]!='O');50         }51     for(i=1;i<=n;++i)52         for(j=1;j<=m;++j)53             if((v[i][j]&&col[i][j]==stcol)||(v[i][j]==0&&col[i][j]!=stcol))54                 id[i][j]=++cnt;55     for(i=1;i<=n;++i)56         for(j=1;j<=m;++j)57             if(id[i][j])58             {59                 if(id[i-1][j])add(id[i][j],id[i-1][j]);60                 if(id[i+1][j])add(id[i][j],id[i+1][j]);61                 if(id[i][j-1])add(id[i][j],id[i][j-1]);62                 if(id[i][j+1])add(id[i][j],id[i][j+1]);63             }64     for(i=1;i<=cnt;++i)65         if(!match[i])++T,find(i);66     scanf("%d",&k);k<<=1;67     for(i=1;i<=k;++i)68         opt[i]=judge(id[a][b]),scanf("%d%d",&a,&b);69     for(i=1;i<=k;i+=2)70         if(opt[i]&&opt[i+1])ans[++top]=((i+1)>>1);71     printf("%d\n",top);72     for(i=1;i<=top;++i)printf("%d\n",ans[i]);73 }74 //二分图类的博弈论？75 //一个格子只能被访问一次

bzoj2437

大概我现在学的东西就这些……博弈论真的是很有趣的知识，一开始很怕这个……

但是现在发现这种博弈的思想很有意思，双方都要取最优策略，

然后要灵活的考虑sg函数的意义，模型的转换，技巧的使用，当然还有背结论

希望大家学的开心……

啊累死了我要回去睡觉

转载于:https://www.cnblogs.com/LadyLex/p/8311027.html

你可能感兴趣的文章