自动搬运

查看原文

来自洛谷，原作者为

	wukaichen888 复健 OI

搬运于2025-08-24 23:16:27，当前版本为作者最后更新于2025-05-21 15:03:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能有帮助：蒋凌宇抽屉原理构造。

对于 $c=2$，考虑最终有两种互补局面。称代价为初始局面到达最终局面步数，每个格子对其中一个造成代价，总代价和为 $nm$，其中一个必然少于一半，即 $w\le\lfloor\frac{nm}{2}\rfloor$。

对于 $c=3$。考虑按斜线分组，即按照 $i+j$ 分组。

假如按照循环节为 $2$，六种最终局面，分别为 $01$、$02$、$10$、$12$、$20$、$21$ 循环。则每个格子对其中四个造成代价，总代价和为 $4nm$，即 $w\le\lfloor\frac{2nm}{3}\rfloor$。

仍然按照循环节为 $2$，三种最终局面，分别为 $?0$、$?1$、$?2$ 循环，问号处分别不能填 $0$、$1$、$2$。则 $i+j$ 为偶数的格子对其中一个造成代价，$i+j$ 为奇数的格子对其中两个造成代价，即 $w\le\lfloor\frac{nm}{2}\rfloor$。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=505;
ll n,m,c,q;
ll a[N][N];
ll c0,c1,cnt[10];
char s[N];
int main(){
	mt19937 rnd;srand(time(0));rnd.seed(rand());
	scanf("%lld%lld%lld%lld",&n,&m,&c,&q);
	for(ll i=1;i<=n;i++){
		scanf("%s",s+1);
		for(ll j=1;j<=m;j++)
			if(s[j]=='R') a[i][j]=0;
			else if(s[j]=='G') a[i][j]=1;
			else if(s[j]=='B') a[i][j]=2;
	}
	if(c==2){
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++){
				c0+=(a[i][j]!=((i+j)&1ll));
				c1+=(a[i][j]!=((i+j+1ll)&1ll));
			}
		if(c0<=q){for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) a[i][j]=((i+j)&1ll);}
		else if(c1<=q){for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) a[i][j]=((i+j+1ll)&1ll);}
	}
	else{
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				if((i+j)&1ll){
					cnt[0]++,cnt[1]++,cnt[2]++;
					cnt[a[i][j]]--;
				}
				else cnt[a[i][j]]++;
		for(ll p=0;p<3;p++)
			if(cnt[p]<=q){
				for(ll i=1;i<=n;i++)
					for(ll j=1;j<=m;j++)
						if((i+j)&1ll) a[i][j]=p;
						else if(a[i][j]==p) a[i][j]=(a[i][j]+1)%3;
				break;
			}
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++)
			if(a[i][j]==0) printf("R");
			else if(a[i][j]==1) printf("G");
			else printf("B");
		puts("");
	}
	return 0;
}