CF1567F One-Four Overload（题解）

· · 题解

Link.

Codeforces
Luogu

P.S.

给个证明？

Description.

给定一个 n\times m 的矩阵，每个元素是 X 或 .。
共两种颜色，对每个 . 染上一种颜色，使得所有 X 周围不同颜色出现次数相同。

Solution.

对于一个 X 周围有奇数个 . 的情况，显然直接无解。
一个 X 周围有 0 个 .，显然不用考虑。
一个 X 周围有 2 个 .，一个是黑另一个就是白，直接二分图染色即可。
一个 X 周围有 4 个 .，有点麻烦。

结论是一个 X 周围有 4 个 . 时。
钦定 (x-1,y)\Leftrightarrow(x,y-1) 和 (x+1,y)\Leftrightarrow(x,y+1) 即可。

证明如下：
证明原结论，只需要证明这样构造不存在奇环即可。
用反证法：假设有奇环。
首先，有两种边，第一种是 (x,y)\Leftrightarrow(x\pm1,y\pm1) 的边，称为斜边。
第二种是 (x,y)\Leftrightarrow(x\pm2,y) 或 (x,y)\Leftrightarrow(x,y\pm2) 的边，称为直边。
定义一个坐标的奇偶性为它横坐标的奇偶性。
那斜边会改变一个坐标的奇偶性，而直边不会。
因为成环，所以起点终点坐标和奇偶性相同。
所以肯定有偶数调斜边，那就有奇数条直边。
考虑如果存在了一条直边，那直边两点中间至少存在长度为 3 的连续 X。
然后最旁边的两个 X 周围有 3 个 .，然后会继续往旁边扩展。
同时两刀是不能合并成同一刀的，那样会出现一个格子是奇数。
脑补一下这个长什么样，显然就是把原图切成了网格。
每个网格的边缘可以通过一个空心闭合宽为 1 的截。
产生了两个，但是其实并不会影响，因为走进去不管在那边都还需要走出来。
每条直边是一个连接两个网格的边。
所以从一个网格走回这个网格会跨过偶数个边界。
与环上有奇数条直边矛盾。
所以它肯定是二分图。

Coding.

//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
    x=0;char c=getchar(),f=0;
    for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
    for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int n,m,cl[250005],vv[505][505];char ch[505][505];
struct edge{int to,nxt;}e[500005];int et,head[250005];
inline void adde(int x,int y) {e[++et]=(edge){y,head[x]},head[x]=et;}
#define ID(i,j) ((i-1)*m+(j))
inline void dfs(int x)
{
    for(int i=head[x];i;i=e[i].nxt)
        if(!~cl[e[i].to]) cl[e[i].to]=cl[x]^1,dfs(e[i].to);
        else if(!(cl[x]^cl[e[i].to])) puts("NO"),exit(0);
}
int main()
{
    read(n,m);for(int i=1;i<=n;i++) scanf("%s",ch[i]+1);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(ch[i][j]=='X')
    {
        vector<int>v;int cnt=0;for(int k=0;k<4;k++)
        {
            int nx=i+dx[k],ny=j+dy[k];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            if(ch[nx][ny]=='.') cnt++,v.push_back(ID(nx,ny));
        }
        if(cnt&1) return puts("NO"),0;else vv[i][j]=cnt/2*5;
        for(int i=0;i<(int)v.size();i+=2) adde(v[i],v[i+1]),adde(v[i+1],v[i]);
    }
    memset(cl,-1,sizeof(cl));for(int i=1;i<=n*m;i++) if(!~cl[i]) cl[i]=0,dfs(i);
    puts("YES");for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
        printf("%d%c",ch[i][j]=='X'?vv[i][j]:cl[ID(i,j)]?4:1,j==m?'\n':' ');
    return 0;
}