题解：P12556 嘟嘟嘟

wukaichen888 · 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;
}