Solution CF1949D | OI, Funny or Scary?
BreakPlus
·
·
题解
Each transition video can be either funny or scary. What about OI?
省流：如果想直接看构造方案，见代码后。
题目要求我们限制最长连续 0/1 路径长度。我们可以先把图的边分成两部分，权为 0 或边权为 1 的边单独拿出来考虑。
不难发现，这个拿出来的图边数很多，但是最长路径却受到限制。首先，当 n 足够大，它至少是个联通图。
我们可能会联想到菊花图，即使有 n-1 条边，但是受到菊花中心的限制，其最长路径长度竟然只有 2。这对接下来的思考可能有所启发。
考虑将图的点分成两半。我们试图在这两个点集之间进行“拦截”使得一条全 0/1 路径不能两边蹦跶。
比如点集内部边权设为 0，连接两个点集的设为 1。
如果两个集合大小都是 \dfrac{n}{2}，我们确实成功限制了 0，但是无法限制 1。
发现题目给的条件是 \dfrac{3n}{4} 而不是 \dfrac{1}{2}。也就是，对 0 的限制过严，对 1 没有限制。
隐隐之中，是否感觉到有平衡 0 与 1，二者兼得的想法？
若把其中一个集合大小设为 \dfrac{3n}{4}，且内部边权全是 0，然后这个点集与另一个点集之间的连边全是 1。
这样对 0 的限制放宽了，变成 \dfrac{3n}{4}，但仍然符合要求。
而对于 1，我们收获了意外之喜。连续 1 路径一旦进入大点集，就必须立刻返回小点集，而小点集的大小只有 \dfrac{n}{4}，也就是我们成功限制了 1，且最多长度为 2 \times \dfrac{n}{4} = \dfrac{n}{2} < \dfrac{3n}{4}。
也就是说，在没有考虑给定的 \dfrac{n}{2} 条边时，我们超额完成了任务。当然，弱化版问题下可以取大点集大小为 \dfrac{2n}{3}，但是直觉告诉我们对解决接下来的问题没有好处。
如何处理给定的边呢？
在之前的解法的基础上完成。我们先不管给定的边，直接按照上面的方法连。但要保证，给定的边所连成的连通块应被分配到相同的点集（读者可以思考一下如何证明一定可以取出一个大小很接近 \dfrac{3n}{4} 的点集）。
这样点集之间的边仍然保留性质，但大点集内部被破坏了。
注意到 \dfrac{n}{2} 条边中，0/1 中必然有一个边权只出现少于 \dfrac{n}{4} 条，令这个边权为 v。不妨令大点集内部其它边的边权为 1-v，集合之间的连边为 v。
这样 1-v 的性质显然没有被破坏。这个边权只能在点集内部溜达。
---
通过对性质的充分挖掘，我们完成了构造。
```cpp
ll n; char s[30][30];
ll fa[30], col[30];
ll find(ll x){ if(x != fa[x]) fa[x] = find(fa[x]); return fa[x]; }
void Merge(ll x,ll y){ fa[find(x)] = find(y); }
vector<ll>v[35]; ll cnt = 0;
vector<ll>v1, v2;
void solve(){
n=read(); cnt = 0;
for(ll i=1;i<=n;i++) fa[i]=i;
for(ll i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(ll j=1;j<=n;j++){
if(s[i][j]=='F' || s[i][j]=='S') Merge(i, j);
}
}
for(ll i=1;i<=n;i++) v[find(i)].pb(i);
sort(v+1, v+n+1, [](vector<ll> a, vector<ll> b){return a.size() > b.size();});
ll w1 = n - n/4;
for(ll i=1; i<=n; i++){
if(!v[i].size()) continue;
if(w1 >= v[i].size()){
w1 -= v[i].size();
}else for(auto x: v[i]) col[x]=1;
}
ll c0 = 0, c1 = 0;
for(ll i=1;i<=n;i++){
for(ll j=i+1;j<=n;j++){
if(!col[i] && !col[j]){
if(s[i][j]=='F') c0++;
else if(s[i][j]=='S') c1++;
}
}
}
if(c0 < c1){
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
if(s[i][j]!='?') continue;
if(!col[i] && !col[j]){
s[i][j]='S';
}else s[i][j]='F';
}
}
}else{
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
if(s[i][j]!='?') continue;
if(!col[i] && !col[j]){
s[i][j]='F';
}else s[i][j]='S';
}
}
}
for(ll i=1;i<=n;i++){
printf("%s\n",s[i]+1);
}
}
```
一句话题解：取出给定的边中出现最少的那种边权，搞一个点集大小约为 $\dfrac{3n}{4}$，使得其内部非给定边的边权都与之相反，该点集中的点与非该点集中的点连边边权必须与之相同即可。