【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;
}

推荐阅读

go
紫荆花之恋：动态树上的小精灵友谊问题

本题来自WC2014，题目编号为BZOJ3435、洛谷P3920和UOJ55。该问题描述了一棵不断生长的带权树及其节点上小精灵之间的友谊关系，要求实时计算每次新增节点后树上所有可能的朋友对数。 ... [详细]

蜡笔小新 2024-12-22 14:36:54
main
使用栈实现字符串中括号匹配的C++程序

本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现，并详细解释了算法的核心思想和具体实现步骤。 ... [详细]

蜡笔小新 2024-12-22 11:44:35
import
字符串中特定字符的移除方法

本文介绍如何从字符串中移除大写、小写、特殊、数字和非数字字符，并提供了多种编程语言的实现示例。 ... [详细]

蜡笔小新 2024-12-22 00:08:06
go
贪心与优先队列：最小化加法代价问题

本题要求在一组数中反复取出两个数相加，并将结果放回数组中，最终求出最小的总加法代价。这是一个经典的哈夫曼编码问题，利用贪心算法可以有效地解决。 ... [详细]

蜡笔小新 2024-12-20 23:20:38
email
Linux环境下进程间通信：深入解析信号机制

本文详细探讨了Linux系统中信号的生命周期，从信号生成到处理函数执行完毕的全过程，并介绍了信号编程中的注意事项和常见应用实例。通过分析信号在进程中的注册、注销及处理过程，帮助读者理解如何高效利用信号进行进程间通信。 ... [详细]

蜡笔小新 2024-12-21 10:29:05
object
主调|大侠_重温C++

主调|大侠_重温C++ ... [详细]

蜡笔小新 2024-12-20 20:43:56
main
Linux环境下C语言实现定时向文件写入当前时间

本文介绍如何在Linux系统中使用C语言编程，实现在每秒钟向指定文件中写入当前时间戳。通过此示例，读者可以了解基本的文件操作、时间处理以及循环控制。 ... [详细]

蜡笔小新 2024-12-21 21:39:27
list
深入解析Spring启动过程

本文详细介绍了Spring框架的启动流程，帮助开发者理解其内部机制。通过具体示例和代码片段，解释了Bean定义、工厂类、读取器以及条件评估等关键概念，使读者能够更全面地掌握Spring的初始化过程。 ... [详细]

蜡笔小新 2024-12-21 17:33:44
main
深入探讨C++中移动赋值后析构函数的调用机制

本文详细解释了为什么在成功执行移动赋值操作后，对象的析构函数会被调用，并提供了代码示例和详细的分析。 ... [详细]

蜡笔小新 2024-12-21 14:09:38
list
由二叉树到贪心算法

二叉树很重要树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。单就面试而言，在 ... [详细]

蜡笔小新 2024-12-21 13:13:13
main
HDU5444：暴力求解策略

本文介绍了如何使用暴力方法解决HDU5444问题。代码通过逐个检查输入数据，确保在所有情况下都能找到正确的解决方案。 ... [详细]

蜡笔小新 2024-12-21 13:05:28
command
并发编程 12—— 任务取消与关闭之 shutdownNow 的局限性

Java并发编程实践目录并发编程01——ThreadLocal并发编程02——ConcurrentHashMap并发编程03——阻塞队列和生产者-消费者模式并发编程04——闭锁Co ... [详细]

蜡笔小新 2024-12-21 12:39:07
main
二叉树的链表实现

本文介绍了一种使用链表结构表示二叉树的方法。通过定义节点结构和相关操作函数，可以方便地创建、插入和遍历二叉树。 ... [详细]

蜡笔小新 2024-12-21 11:37:21
import
深入解析Java多线程与并发库的应用：空中网实习生面试题详解

本文详细探讨了Java多线程与并发库的高级应用，结合空中网在挑选实习生时的面试题目，深入分析了相关技术要点和实现细节。文章通过具体的代码示例展示了如何使用Semaphore和SynchronousQueue来管理线程同步和任务调度。 ... [详细]

蜡笔小新 2024-12-21 09:43:07
go
HDU 2871 内存管理问题（线段树优化）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2871。本题涉及内存管理操作，包括重置、申请、释放和查询内存块。通过使用线段树进行高效管理和维护。 ... [详细]

蜡笔小新 2024-12-20 10:59:14

Toby_魚5902

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

Tags | 热门标签

RankList | 热门文章