题解：CF1567F One-Four Overload

· · 题解

提供一种比较好写的直接构造的方法。

::::warning[提示] 以下为笔者的思考过程，可以跳过直接看最后的构造部分。 ::::

容易想到先确定非标记点，限制每个标记点周围和为 5 的倍数，这等价于在此邻域中对于每个 1 存在不同且唯一的 4 与其对应。注意到每个标记点四相邻标记点数为偶数，否则显然无解，于是标记点构成若干个欧拉回路，即若干可自交的多边形。

发现多边形内外可以分开考虑，且内部问题形式类似。请注意这里的内外是广义的，因为多边形有自交，可以通过光线投射算法判断其内外，即某一方向到边界前经过边数的奇偶性，注意边界情况。

由于对于多边形内部只有角块，所以只要考虑拐角格不同的限制，显然只要按行奇偶性赋值即可。特别的，多边形为空仍成立。

对于多边形内外间，只有边块的限制，只要给内部全部取反即可。

总结一下，对于每个位置的赋值，只要求出其行编号奇偶性和是否在多边形内部的异或和，对应赋 1 或 4，正确性显然。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[505][505],ans[505][505];
char c[505][505];
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>c[i];
    for(int i=1;i<n-1;i++){
        int cur=0,lst=0;
        for(int j=m-1;j>=0;j--){
            if(j&&j<m-1&&c[i][j]=='X'&&((c[i-1][j]=='.')+(c[i+1][j]=='.')+(c[i][j-1]=='.')+(c[i][j+1]=='.'))&1) return cout<<"NO\n",0;
            if(c[i][j]=='X'&&c[i-1][j]=='X'&&c[i+1][j]=='X'){
                cur^=1;
                continue;
            }
            if(c[i][j]=='X'&&c[i-1][j]=='X'){
                if(lst) cur^=(lst==1),lst=0;
                else lst=-1;
                continue;
            }
            if(c[i][j]=='X'&&c[i+1][j]=='X'){
                if(lst) cur^=(lst==-1),lst=0;
                else lst=1;
                continue;
            }
            if(c[i][j]!='X') ans[i][j]=cur;
        }
    }
    cout<<"YES\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(c[i][j]!='X') cout<<((ans[i][j]^(i&1)?1:4))<<' ';
            else cout<<((c[i-1][j]=='.')+(c[i+1][j]=='.')+(c[i][j-1]=='.')+(c[i][j+1]=='.')>>1)*5<<' ';
        }
        cout<<'\n';
    }
    return 0;
}