题解：CF1567F One-Four Overload

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

提示

以下为笔者的思考过程，可以跳过直接看最后的构造部分。

容易想到先确定非标记点，限制每个标记点周围和为

5

的倍数，这等价于在此邻域中对于每个

1

存在不同且唯一的

4

与其对应。注意到每个标记点四相邻标记点数为偶数，否则显然无解，于是标记点构成若干个欧拉回路，即若干可自交的多边形。

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

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

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

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

1

或

4

，正确性显然。

CPP

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

题解：CF1567F One-Four Overload

文章操作

相关推荐

评论

题解：CF1567F One-Four Overload