【BZOJ2437】【NOI2011】兔兔与蛋蛋（博弈论，二分图匹配）

作者：Toby_魚5902 | 来源：互联网 | 2023-10-13 10:30

【BZOJ2437】【NOI2011】兔兔与蛋蛋（博弈论，二分图匹配）题面BZOJ题解考虑一下暴力吧。对于每个状态，无非就是要考虑它是否是必胜状态这个直接用\(dfs\)爆搜即可。

【BZOJ2437】【NOI2011】兔兔与蛋蛋（博弈论，二分图匹配）

题面

BZOJ

题解

考虑一下暴力吧。
对于每个状态，无非就是要考虑它是否是必胜状态
这个直接用\(dfs\)爆搜即可。
这样子对于每一次操作，考虑兔兔操作后的状态是否是必胜状态
如果这个状态是必胜状态，并且蛋蛋操作完后的状态是（兔兔的）必败状态
那么这就是一个“犯错误”的操作。
这样暴力可以拿到\(75pts\)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define RG register
#define MAX 45
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,m,X,Y;
char ch[MAX];
int g[MAX][MAX],zt[MAX];
int d[4][2]={1,0,-1,0,0,1,0,-1};
int ans[MAX*MAX],top,Q;
bool dfs(int x,int y,int z)
{
    for(int i=0;i<4;++i)
    {
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx<1||xx>n||yy<1||yy>m||g[xx][yy]!=z)continue;
        swap(g[x][y],g[xx][yy]);
        if(!dfs(xx,yy,z^1)){swap(g[x][y],g[xx][yy]);return true;}
        swap(g[x][y],g[xx][yy]);
    }
    return false;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ch+1);
        for(int j=1;j<=m;++j)
            if(ch[j]=='X')g[i][j]=1;
            else if(ch[j]=='O')g[i][j]=0;
            else if(ch[j]=='.')g[i][j]=2;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(g[i][j]==2){X=i;Y=j;break;}
    Q=read();
    for(int i=1,x,y;i<=Q;++i)
    {
        x=read(),y=read();
        zt[i]=dfs(X,Y,0);
        swap(g[x][y],g[X][Y]);
        X=x;Y=y;
        if(zt[i]&&dfs(X,Y,1))ans[++top]=i;
        x=read();y=read();
        swap(g[x][y],g[X][Y]);
        X=x;Y=y;
    }
    printf("%d\n",top);
    for(int i=1;i<=top;++i)printf("%d\n",ans[i]);
    return 0;
}

观察一下基本的事实。
考虑走的方案是否可能出现一个环。
无论环有多大，似乎都是一样的，所以我们就考虑在\(2\times 2\)的方格中移动
初始时空格在\((1,1)\)，它和\((1,2)\)交换位置，此时，\((1,1)\)为白
然后\((1,2)\)和\((2,2)\)交换位置，\((1,2)\)为黑
\((2,2)\)和\((2,1)\)交换位置，\((2,2)\)为白
此时如果\((2,1)\)能与\((1,1)\)交换位置，那么\((1,1)\)需要是黑色
但是\((1,1)\)是白色，所以显然不能成环。
对于一个更大的环，无非是长\(+1\)或者宽\(+1\)拓展出来的，每次多走两步，对于黑白没有影响。

既然不能成环，意味着每个点只会被经过一次。
那么，我们可以重新开一下这个过程，可以理解为从空格开始，
走一条路径，路径上黑白相间。
黑白相间？有点像二分图的感觉。每条增广路不就是黑白相间吗？
因为先手的是白格子，所以可以把空格开成黑格子
这样子就是要从这个黑格子这里找一条增广路出去。
再考虑一下胜利的情况，如果先手胜利，那么从黑格子连向了一个白格子
然后找不到增广路了，此时白格子胜。
继续把这个情况向上拓展，我们可以得到。

如果当前点一定在二分图的最大匹配中，那么先手必胜。因为先手始终可以沿着最大匹配的匹配边走，而最大匹配中交错路的数量为奇数条，也就是进行奇数次操作，意味着后手最后无法操作，此时先手必胜。

那么，每次进行判定当前点是否在二分图的最大匹配中，是否一定被选中即可判定先手是否必胜，依次可以计算答案。

至于如何计算当前点是否一定在二分图的最大匹配中？
把当前点给\(ban\)掉，在增广的时候强行不选，然后对其匹配点进行增广，
如果能够找到新的增广路，意为这当前点可以被替代，
否则当前点一定在最大匹配中。
~~这题好神仙啊~~

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define RG register
#define MAX 45
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int n,m,X,Y;
char ch[MAX];
int g[MAX][MAX],zt[MAX*MAX];
int d[4][2]={1,0,-1,0,0,1,0,-1};
int ans[MAX*MAX],top,Q;
int bh[MAX][MAX],tot;
struct Line{int v,next;}e[MAX*MAX<<3];
int h[MAX*MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int match[MAX*MAX],tim,vis[MAX*MAX];
bool ban[MAX*MAX];
bool dfs(int u)
{
    if(ban[u])return false;
    for(int i=h[u];i;i=e[i].next)
        if(vis[e[i].v]!=tim&&!ban[e[i].v])
        {
            vis[e[i].v]=tim;
            if(!match[e[i].v]||dfs(match[e[i].v]))
            {
                match[e[i].v]=u;match[u]=e[i].v;
                return true;
            }
        }
    return false;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ch+1);
        for(int j=1;j<=m;++j)
            if(ch[j]=='X')g[i][j]=1;
            else if(ch[j]=='O')g[i][j]=0;
            else if(ch[j]=='.')g[i][j]=1,X=i,Y=j;
    }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            bh[i][j]=++tot;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(g[i][j])
                for(int k=0;k<4;++k)
                {
                    int x=i+d[k][0],y=j+d[k][1];
                    if(x<1||x>n||y<1||y>m||g[x][y])continue;
                    Add(bh[i][j],bh[x][y]);
                    Add(bh[x][y],bh[i][j]);
                }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(g[i][j])++tim,dfs(bh[i][j]);
    Q=read();
    for(int i=1,id;i<=Q+Q;++i)
    {
        id=bh[X][Y];ban[id]=true;
        if(match[id])
        {
            int nw=match[id];match[nw]=match[id]=0;
            ++tim;zt[i]=!dfs(nw);
        }
        X=read();Y=read();
    }
    for(int i=1;i<=Q;++i)
        if(zt[i+i-1]&zt[i+i])ans[++top]=i;
    printf("%d\n",top);
    for(int i=1;i<=top;++i)printf("%d\n",ans[i]);
    return 0;
}

推荐阅读

io
HDU2757 海洋洋流（BFS+优先队列）

题目描述：计算从起点到终点的最小能量消耗。如果下一个单元格的风向与当前单元格相同，则消耗为0，否则为1。共有8个可能的方向。 ... [详细]

蜡笔小新 2024-11-18 16:02:40
io
SDOI2008 Cave Exploration - 动态树结构应用

题目编号：2049 [SDOI2008]Cave Exploration。题目描述了一种动态图操作场景，涉及三种基本操作：断开两个节点间的连接（destroy(a,b)）、建立两个节点间的连接（connect(a,b)）以及查询两节点是否连通（query(a,b)）。所有操作均确保图中无环存在。 ... [详细]

蜡笔小新 2024-11-18 20:11:35
get
c语言二元插值,二维线性插值c语言

c语言二元插值,二维线性插值c语言 ... [详细]

蜡笔小新 2024-11-20 12:20:16
get
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
get
递归实现表达式求和

本文通过C++语言实现了一个递归算法，用于解析并计算数学表达式的值。该算法能够处理加法、减法、乘法和除法操作。 ... [详细]

蜡笔小新 2024-11-21 15:38:13
io
线段树详解与实现

本文详细介绍了线段树的基本概念及其在编程竞赛中的应用，并提供了一个具体的线段树实现代码示例。 ... [详细]

蜡笔小新 2024-11-19 21:26:45
get
编译原理中的语法分析方法探讨

本文探讨了在编译原理课程中遇到的复杂文法问题，特别是当使用SLR(1)文法时遇到的多重规约与移进冲突。文章讨论了可能的解决策略，包括递归下降解析、运算符优先级解析等，并提供了相关示例。 ... [详细]

蜡笔小新 2024-11-19 14:44:19
io
HNOI2003 激光炸弹问题（二维前缀和的应用）难度：中等

HNOI2003 激光炸弹问题是一个经典的二维前缀和应用题目。本文将详细介绍如何使用二维前缀和解决该问题。 ... [详细]

蜡笔小新 2024-11-19 05:18:58
io
二维码的实现与应用

本文介绍了二维码的基本概念、分类及其优缺点，并详细描述了如何使用Java编程语言结合第三方库（如ZXing和qrcode.jar）来实现二维码的生成与解析。 ... [详细]

蜡笔小新 2024-11-21 17:10:15
get
Singleton单例模式和DoubleChecked Locking双重检查锁定模式

问题描述现在，不管开发一个多大的系统（至少我现在的部门是这样的），都会带一个日志功能；在实际开发过程中 ... [详细]

蜡笔小新 2024-11-21 15:14:45
get
循环双链表中指定位置的元素插入方法

本文详细介绍了如何在循环双链表的指定位置插入新元素的方法，包括必要的步骤和代码示例。 ... [详细]

蜡笔小新 2024-11-20 06:48:26
io
PTA 71 jmuds 顺序表区间元素删除 (C语言)

本文提供了一个使用C语言实现的顺序表区间元素删除功能的完整代码示例。该程序首先初始化一个顺序表，然后根据用户输入的数据进行插入操作，最后根据指定的区间范围删除相应的元素，并输出最终的顺序表。 ... [详细]

蜡笔小新 2024-11-19 13:34:15
io
POJ2263: Heavy Cargo 最大载重问题

POJ2263是一个经典的图论问题，涉及寻找从起点到终点的最大载重路径。本文将详细介绍该问题的背景、解题思路及代码实现。 ... [详细]

蜡笔小新 2024-11-19 11:02:03
io
JZOJ4866: 禅意与园林美学探讨 - 树状数组应用

本题涉及一个长度为n的序列{ai}，代表一系列树木的美学价值。任务是处理m个查询，每个查询提供三个参数l、r和P，目标是在所有满足l < l' ... [详细]

蜡笔小新 2024-11-19 10:00:06
install
RTThread线程间通信

线程中通信在裸机编程中，经常会使用全局变量进行功能间的通信，如某些功能可能由于一些操作而改变全局变量的值，另一个功能对此全局变量进行读取& ... [详细]

蜡笔小新 2024-11-18 14:56:11

Toby_魚5902

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章