CF2057G Secret Message 题解

· · 题解

这个题目限制给的 \dfrac 15 很奇怪。

考虑如下 trick：如果我们不考虑这个限制的情况下构造出了 5 种合法方案，并且这些方案的 |S| 之和恰为 s+p，根据抽屉原理，其中必然存在至少一个方案满足 |S|\le\dfrac15(s+p)。

这也太牛了！那我们怎么找到这五个方案呢？

考虑一种十字形的密铺：

\def\sq{\rule{10px}{10px}} \def\sq{\rule{10px}{10px}} \red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\red\sq\\[-3px] \red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\\[-3px] \red\sq\blue\sq\red\sq\red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\\[-3px] \blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\red\sq\blue\sq\\[-3px] \red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\\[-3px] \blue\sq\red\sq\red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\\[-3px] \blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\red\sq\blue\sq\red\sq\\[-3px] \blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\\[-3px] \red\sq\red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\\[-3px]

发现，如果我们选择了所有十字形中心，那么剩余未被影响到的格子就会在边上，我们在另外选择这些点即可。

注意到这些十字形中心的坐标 (i,j) 满足 (i+2j)\bmod5 同余，所以我们按照这种方式五染色，就能得到 5 种合法方案了！

#include<bits/stdc++.h>
#define N 2000005
#define id(X,Y) ((X-1)*m+(Y))
#define ll long long
#define mod 
using namespace std;

int n,m,a[N],col[N],vis[N];

void sol()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int id=id(i,j);
            col[id]=(i+j*2)%5;
            char c;
            cin>>c;
            a[id]=c=='#';
            vis[id]=0;
        }
    }
    int lim=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int id=id(i,j);
            if(!a[id]) continue;
            lim++;
            lim+=i==n||!a[id(i+1,j)];
            lim+=j==m||!a[id(i,j+1)];
            lim+=i==1||!a[id(i-1,j)];
            lim+=j==1||!a[id(i,j-1)];
        }
    }
    lim/=5;
    for(int c=0;c<5;c++)
    {
        vector<int>vec;
        fill(vis+1,vis+n*m+1,0);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int id=id(i,j);
                if(!a[id]||col[id]!=c) continue;
                vis[id]=1;
                vec.push_back(id);
                if(i<n) vis[id(i+1,j)]=1;
                if(j<m) vis[id(i,j+1)]=1;
                if(i>1) vis[id(i-1,j)]=1;
                if(j>1) vis[id(i,j-1)]=1;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int id=id(i,j);
                if(!a[id]||vis[id]) continue;
                vec.push_back(id);
            }
        }
        if(vec.size()>lim) continue;
        fill(vis+1,vis+n*m+1,0);
        for(auto k:vec) vis[k]=1;
        break;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int id=id(i,j);
            cout<<(vis[id]?'S':a[id]?'#':'.');
        }
        cout<<'\n';
    }
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}