CF1481F 题解

· · 题解

CF1481F 题解

Problem Link

题目大意

给一棵 n 个点的树，给每个点填 0/1，最终要求填 0 的点恰有 x 个，最小化所有 1\to i 形成的 01 串中本质不同字符串的数量，给出构造。

数据范围：n\le 10^5。

思路分析

首先考虑最理想情况，当且仅当每层都填同一个数才能取得最小值，此时答案等于最大深度 D。

然后考虑一般的情况，显然只有一层不是全部同色，显然我们想让某种颜色的节点全在叶子上，此时就能取到 D+1 作为答案，事实上，这是可行的，下给出一种证明：

从第一层开始，维护两种颜色剩下的数量 c_0,c_1，假设当前处理到第 i 层，且该层非叶子节点有 t 个，且 i\sim D 层还剩下 m 个节点，我们能得到 \max(c_0,c_1)\ge\left\lfloor \dfrac m2\right\rfloor\ge t，因此用余量更多的一种去填非叶节点即可。

对于叶节点，依然用同种颜色去填，如果能填完，则没有新建字符串，处理下一层。

如果不能填完，那么剩下部分用另一种颜色去填，此时 i+1\sim D 层全部同色，只有 i 层不是完全同色。

此时我们就构造了一组 D+1 的方案。

然后考虑如何判定答案是否可能为 D，显然把每一层的大小 siz_i 做个背包即可，bitset 优化，时空复杂度 \mathcal O\left(\dfrac {n^2}\omega\right)。

此时空间过大，考虑优化，注意到 siz 相同的层可以一起在 dp 的时候处理，由于 \sum siz_i=n，因此不同的 siz 只有 \mathcal O(\sqrt n) 种，空间复杂度就可以做到 \mathcal O\left(\dfrac{n\sqrt n}{\omega}\right)。

时间复杂度 \mathcal O\left(\dfrac {n^2}\omega\right)

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
bitset <MAXN> dp[505],tmp;
int dep[MAXN],tot,cnt[MAXN];
vector <int> G[MAXN],ver[MAXN],blo[MAXN];
char str[MAXN];
inline void dfs(int u,int fa) {
    ver[dep[u]=dep[fa]+1].push_back(u);
    tot=max(tot,dep[u]);
    for(int v:G[u]) dfs(v,u);
}
signed main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=2,p;i<=n;++i) scanf("%d",&p),G[p].push_back(i);
    dfs(1,0);
    dp[0].set(0);
    vector <int> sz;
    for(int i=1;i<=tot;++i) {
        int k=ver[i].size();
        blo[k].push_back(i);
        sz.push_back(k);
    }
    sort(sz.begin(),sz.end());
    sz.erase(unique(sz.begin(),sz.end()),sz.end());
    int cnt=sz.size();
    sz.insert(sz.begin(),0);
    for(int t=1;t<=cnt;++t) {
        int i=sz[t]; tmp=dp[t-1];
        for(int j=0;j<=(int)blo[i].size();++j) {
            dp[t]|=tmp,tmp<<=i;
        }
    }
    if(dp[cnt][m]) {
        printf("%d\n",tot);
        for(int t=cnt;t>=1;--t) {
            int i=sz[t];
            for(int j=0;j<=(int)blo[i].size();++j) if(dp[t-1][m-i*j]) {
                m-=i*j;
                for(int k=0;k<j;++k) {
                    for(int u:ver[blo[i][k]]) str[u]='a';
                }
                for(int k=j;k<(int)blo[i].size();++k) {
                    for(int u:ver[blo[i][k]]) str[u]='b';
                }
                break;
            }
        }
    } else {
        printf("%d\n",tot+1);
        int ca=m,cb=n-m;
        for(int i=1;i<=tot;++i) {
            sort(ver[i].begin(),ver[i].end(),[&](int x,int y){ return G[x].size()>G[y].size(); });
            bool o=ca>cb;
            for(int j:ver[i]) {
                if(o) str[j]='a',o^=!(--ca);
                else str[j]='b',o^=!(--cb);
            }
        }
    }
    printf("%s\n",str+1);
    return 0;
}