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

推荐阅读

tree
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
io
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
io
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
tree
洛谷 P4116 树上操作：颜色变换与路径查询

本题涉及一棵由N个节点组成的树（共有N-1条边），初始时所有节点均为白色。题目要求处理两种操作：一是改变某个节点的颜色（从白变黑或从黑变白）；二是查询从根节点到指定节点路径上的第一个黑色节点，若无则输出-1。 ... [详细]

蜡笔小新 2024-12-26 10:22:20
io
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
import
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
io
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16
go
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
import
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
io
C++: 实现基于类的四面体体积计算

本文介绍如何使用C++编程语言，通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式，并提供了两种不同的实现方式。 ... [详细]

蜡笔小新 2024-12-27 14:31:39
io
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
import
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
import
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
tree
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
io
C语言链表动态创建：头插法与尾插法详解

本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法，包括具体的实现代码和运行示例。通过这些内容，读者可以更好地理解和掌握链表的基本操作。 ... [详细]

蜡笔小新 2024-12-26 13:59:07

Toby_魚5902

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

Tags | 热门标签

RankList | 热门文章