博弈问题之其它博弈合集

找规律博弈：

这类题目出得也很多，而且出得很巧妙，相比固定模式的博弈解决方法，这类题目更加需要开创性思维和强大的逻辑能力。虽然最后可能代码很简单，但其中的思考过程却十分精彩。而且人都有一种在未知情况下的本能就是找出事物的规律，所以这也是人本能的一种体现~

例题：

POJ1740 A New Stone Game

这是楼教主的男人八题之一，非常好的找规律博弈，既不是很简单的一眼题，想法也很巧妙，我的男人八题专题系列有写到这个题目：传送阵

动态博弈：

动态博弈(dynamic game)是指参与人的行动有先后顺序，而且行动在后者可以观察到行动在先者的选择，并据此作出相应的选择。动态博弈的困难在于，在前一刻最优的决策在下一刻可能不再为最优，因此在求解上发生很大的困难。动态博弈行动有先后顺序，不同的参与人在不同时点行动，先行动者的选择影响后行动者的选择空间，后行动者可以观察到先行动者做了什么选择，因此，为了做最优的行动选择，每个参与人都必须这样思考问题：如果我如此选择，对方将如何应对？如果我是他，我将会如何行动？给定他的应对，什么是我的最优选择？如下棋。

其实就是DP+博弈，这类题目将博弈问题的性质糅合在了DP中，其实主要还是DP，状态转移方程是关键。

例题：

POJ1678 I Love this Game!

题意是给你n个数字和a,b(a<b)，第一个人拿[a,b]中的数字，然后第二个人拿比这个数字大且相差在[a,b]之间的数字，直到那不了，问最优情况下第一个人拿的点数之和与第二个人的差。这就是一个DP过程，只要后面的人每次都取最大数即可。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<set>#include<vector>#include<stack>#include <queue>#include<map>#define mem(a,b) memset(a,b,sizeof(a))#define FOR(a,b,i) for(i=a;i<=b;++i)#define For(a,b,i) for(i=a;i<b;++i)using namespace std;inline void RD(int &ret){    char c;    do    {        c=getchar();    }    while(c<'0'||c>'9');    ret=c-'0';    while((c=getchar())>='0'&&c<='9')    {        ret=ret*10+(c-'0');    }}inline void OT(int a){    if(a>=10)    {        OT(a/10);    }    putchar(a%10+'0');}int d[1001][1001];int nim_mul(int x,int y);//两个函数互相调用（nim积模板）int nim_pow(int x,int y){    if(d[x][y]!=-1)    {        return d[x][y];    }    if(x==0)    {        return d[x][y]=1<<y;    }    if(y==0)    {        return d[x][y]=1<<x;    }    int x1=x,y1=y,s=1,w=1,z;    while(x1||y1)    {        z=1<<w;        if((x1%2==1||y1%2==1)&&!(x1%2==1&&y1%2==1))        {            s*=z;        }        w*=2;        x1/=2;        y1/=2;    }    w=1;    x1=x;    y1=y;    while(x1||y1)    {        z=1<<w;        if(x1%2==1&&y1%2==1)        {            s=nim_mul(s,z*3/2);        }        w*=2;        x1/=2;        y1/=2;    }    return d[x][y]=s;}int nim_mul(int x,int y){    int i,j,s=0,p=0,q;    for(p=0,i=x;i;i/=2,p++)    {        if(i%2==1)        {            for(q=0,j=y;j;j/=2,q++)            {                if(j%2==1)                {                    s^=nim_pow(p,q);                }            }        }    }    return s;}int main(){    int n,a,b,c,s;    mem(d,-1);    while(scanf("%d",&n)!=EOF)    {        s=0;        while(n--)        {            scanf("%d%d%d",&a,&b,&c);            s^=nim_mul(nim_mul(a,b),c);        }        if(s==0)        {            printf("Yes\n");        }        else        {            printf("No\n");        }    }    return 0;}

还有什么不平等博弈，极大极小搜索博弈表示还没搞明白，甚至还不懂，所以以后会了再发吧~

这里给出cxlove大神的博弈总结：无线膜拜~ORZ