首页 > 代码库 > 组合博弈

组合博弈

2024-07-08 21:14:22   230人阅读

博弈，一般就是，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;}
View Code

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;}
View Code

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;}
View Code

 

 


联系
我们