Solution

这道题和 2024 年数学高联 T3 的技巧几乎一模一样，为啥我没做出来？

考虑给出 5 组构造方案，他们 |S| 的和为 s+p，这样就必存在一种方案的 |S| \le \dfrac{1}{5} (s+p)。

如果能将所有点染上五种颜色，使得任何一个点的邻域和自己恰好为这五种颜色，那么对于每种颜色 i，取 S 为所有颜色为 i 的 # 格子，以及不被上述任何一个格子覆盖或相邻的 # 格。后者只会出现在边界上，且边界外对应的格子恰好是颜色 i。

显然这五种颜色的 |S| 之和为 s+p。

怎么五染色？考虑在模意义下构造：令 col_{i,j} = (i+2j) \bmod 5，容易验证符合要求。

直接 vector 套 vector 存储一些东西会 MLE，建议映射成线性序列。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=6e6+10,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int T,n,m,mp[MAXN];
inline int gid(const int i,const int j) {return i*(m+2)+j;}
vector<pair<int,int>> gpos(int col) {
    vector<pair<int,int>> ans;
    ffor(i,1,n) ffor(j,1,m) if(mp[gid(i,j)]==1) {
        if((i+2*j)%5==col) ans.push_back({i,j});
        else ffor(d,0,3) {
            int ii=i+dx[d],jj=j+dy[d];
            if((ii+2*jj)%5==col&&mp[gid(ii,jj)]==0) ans.push_back({i,j});
        }
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--) {
        cin>>n>>m;
        ffor(i,0,(n+2)*(m+2)) mp[i]=0;
        ffor(i,1,n) {
            string S;
            cin>>S,S="&"+S;
            ffor(j,1,m) if(S[j]=='#') mp[gid(i,j)]=1;
        }
        vector<pair<int,int>> ans=gpos(0);
        ffor(i,1,4) {
            vector<pair<int,int>> nw=gpos(i);
            if(nw.size()<ans.size()) ans=nw;
        }
        for(auto id:ans) mp[gid(id.first,id.second)]=2;
        ffor(i,1,n) {
            ffor(j,1,m) if(mp[gid(i,j)]==1) cout<<'#';
            else if(mp[gid(i,j)]) cout<<'S';
            else cout<<'.';
            cout<<'\n'; 
        }
    }
    return 0;
}