526互联

Atcoder Grand Contest 059 E - Grid 3-coloring（转化+思维）

发布时间 2023-05-01 23:26:33作者: tzc_wk

首先先是一步很猛的操作——将三染色视作构造一个矩阵使得相邻元素相差 \(1\) 且每个元素 \(\bmod 3\) 的值就等于其颜色。证明是显然的，我们按从上到下从左到右的顺序填数，可以归纳证明，对于一个相邻格子颜色互不相同的矩阵的填数方案，处于斜对角的两个格子上写的数要么差 \(2\)，要么相等，这样待填的这个格子必然存在合法的待选值。

于是问题转化为是否存在合法的填数方案。我们先给边界上的元素确定值，如果边界上都没法做到相邻元素相差 \(1\) 就直接似了。判完这个条件之后思考还有什么必要条件，显然边界上任意两个元素之间的差值不能超过它们的曼哈顿距离，否则的话对于任意一条它们之间的路径，必然存在两个元素相差 \(\ge 2\)。而这一部分的 check 其实只用考虑边界上相对的位置，即 \(a_{1,i}\) 与 \(a_{n,i}\)，以及 \(a_{i,1}\) 与 \(a_{i,n}\)。

这样是否充分了呢？答案是肯定的。考虑构造，\(a_{i,j}=\max\{i-1+a_{1,j},n-i+a_{n,j},j-1+a_{i,1},m-j+a_{i,m}\}\)。容易验证相邻元素相差不超过 \(1\)，并且根据黑白染色，中括号中四项的奇偶性都是相同的，也就是 \(a_{i,j}\) 的奇偶性是随 \(i+j\) 的奇偶性同步变化的。因此不会出现相邻元素相同的情况，符合条件。

评价：agc 全是脑洞题，一步想出来就会做，否则就不会/tuu

#include<bits/stdc++.h>
using namespace std;
int n,len,sum[1000005];char s[1000005];
void solve(){
	scanf("%d%s",&n,s+1);len=strlen(s+1);s[++len]=s[1];sum[1]=(s[1]-'0')%3;
	for(int i=2;i<=len;i++)for(int j:{-1,1})if(((sum[i-1]+j)%3+3)%3==(s[i]-'0')%3)sum[i]=sum[i-1]+j;
	if(sum[1]!=sum[len])return puts("NO"),void();
	for(int i=2;i<n;i++)if(abs(sum[i]-sum[3*n-1-i])>=n)return puts("NO"),void();
	for(int i=2;i<n;i++)if(abs(sum[n-1+i]-sum[4*n-2-i])>=n)return puts("NO"),void();
	puts("YES");
}
int main(){int qu;scanf("%d",&qu);while(qu--)solve();return 0;}