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

推荐阅读

string
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
char
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
char
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
char
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
string
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
char
伊振华作品 | 沈阳市智慧城市运行管理中心的设计与建设

本文介绍了设计师伊振华受邀参与沈阳市智慧城市运行管理中心项目的整体设计，并以数字赋能和创新驱动高质量发展的理念，建设了集成、智慧、高效的一体化城市综合管理平台，促进了城市的数字化转型。该中心被称为当代城市的智能心脏，为沈阳市的智慧城市建设做出了重要贡献。 ... [详细]

蜡笔小新 2023-12-14 16:35:39
uri
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
char
c语言\n不换行,c语言printf不换行

$c语言\n不换行,c语言printf不换行$

本文目录一览：1、C语言不换行输入2、c语言的 ... [详细]

蜡笔小新 2023-12-14 11:05:35
char
Linux环境变量函数getenv、putenv、setenv和unsetenv详解

本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数，可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值，并打印出来。 ... [详细]

蜡笔小新 2023-12-13 12:01:03
char
PE总结9PE文件结构之解析导出表

本文介绍了PE文件结构中的导出表的解析方法，包括获取区段头表、遍历查找所在的区段等步骤。通过该方法可以准确地解析PE文件中的导出表信息。 ... [详细]

蜡笔小新 2023-12-13 11:47:24
string
hdu 5439（找规律）的数列求和问题

本文讨论了一个数列求和问题，该数列按照一定规律生成。通过观察数列的规律，我们可以得出求解该问题的算法。具体算法为计算前n项i*f[i]的和，其中f[i]表示数列中有i个数字。根据参考的思路，我们可以将算法的时间复杂度控制在O(n)，即计算到5e5即可满足1e9的要求。 ... [详细]

蜡笔小新 2023-12-12 14:05:58
char
STL迭代器的种类及其功能介绍

本文介绍了标准模板库(STL)定义的五种迭代器的种类和功能。通过图表展示了这几种迭代器之间的关系，并详细描述了各个迭代器的功能和使用方法。其中，输入迭代器用于从容器中读取元素，输出迭代器用于向容器中写入元素，正向迭代器是输入迭代器和输出迭代器的组合。本文的目的是帮助读者更好地理解STL迭代器的使用方法和特点。 ... [详细]

蜡笔小新 2023-12-10 15:17:25
string
go利用(*interface{})(nil)传递参数类型的原理及应用

本文介绍了在go语言中利用(*interface{})(nil)传递参数类型的原理及应用。通过分析Martini框架中的injector类型的声明，解释了values映射表的作用以及parent Injector的含义。同时，讨论了该技术在实际开发中的应用场景。 ... [详细]

蜡笔小新 2023-12-10 11:37:12
string
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
char
Python正则表达式学习记录及常用方法

本文记录了学习Python正则表达式的过程，介绍了re模块的常用方法re.search，并解释了rawstring的作用。正则表达式是一种方便检查字符串匹配模式的工具，通过本文的学习可以掌握Python中使用正则表达式的基本方法。 ... [详细]

蜡笔小新 2023-12-13 16:37:19

Toby_魚5902

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

Tags | 热门标签

RankList | 热门文章