Posts CF1481Div2
Post
Cancel

CF1481Div2

E

给一个数组,每次操作可以把一个数字移到最右边,问最少操作多少次能让数组中一样的数字都在一起,如2211333。

注意到操作顺序是任意的,我们只要决定哪些数字要移到最右边就行了。那么问题就变成了,最多留下多少个数字,他们是符合要求的。

那么我们从左到右dp,如果当前位置是某种数字的最右边,那么我们考虑将所有这种数字留下,$dp[i]=dp[l[a[i]]-1]+cnt[a[i]]$这是$[1,i]$的答案,加上右边,我们取右边出现次数最多的数,把他们留下。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=5e5+10;
int n,a[N],mxr[N],l[N],r[N],cnt[N],dp[N];
inline void wk(){
    n=read();
    rep(i,1,n) a[i]=read();
    rpe(i,n,1){
        ++cnt[a[i]];
        mxr[i]=mxr[i+1];
        chmax(mxr[i],cnt[a[i]]);
        l[a[i]]=i;
        chmax(r[a[i]],i);
    }
    int ans=0;
    rep(i,1,n){
        dp[i]=dp[i-1];
        if(r[a[i]]==i){
            chmax(dp[i],dp[l[a[i]]-1]+cnt[a[i]]);
            chmax(ans,dp[i]+mxr[i+1]);
        }
    }
    printf("%d\n",n-ans);
}

F

给一棵树,根为1,要求给结点分配$x$个字母a,$n-x$个字母b,使得从根到每个点形成的所有字符串,本质不同的串的个数最少。

一个显然的策略就是,让同一层的节点都是一个字母,如果若干层加起来的结点数刚好是$x$,那就可以。

接着我们可以发现,倒数第二层每个节点至少会提供一个叶子节点,那么叶子节点的个数一定大于等于倒数第二层,那么我们一层一层地尝试填充,倒数第二层一定可以填成全$a$或者全$b$,只可能在叶子层多产生一种串,也就是答案最多只会多1。

因为所有层结点加起来是n,那么本质不同的结点数是$O(\sqrt{n})$的,类似于分拆数。

我们只要做一个多重背包就能判断能否凑出$x$。之后随便构造一下方案即可。

Code(没写构造方案):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int N=1e5+10;
int n,k,fa[N],val[N],cnt[N],dep[N],fre[N],vis[N];
int dp[505][N],fr[505][N];
vector<int> G[N];
inline void wk(){
    n=read();k=read();
    rep(i,2,n){
        G[fa[i]=read()].emplace_back(i);
    }
    int mxdep=0;
    function<void(int)> dfs=[&](int x){
                               ++cnt[dep[x]];
                               chmax(mxdep,dep[x]);
                               for(auto v:G[x]){
                                   dep[v]=dep[x]+1;
                                   dfs(v);
                               }
                           };
    dfs(1);
    int nm=0;
    rep(i,0,n){
        if(cnt[i]){
            if(vis[cnt[i]]){
                
            }else{
                vis[cnt[i]]=++nm;
            }
            int t=vis[cnt[i]];
            val[t]=cnt[i];
            ++fre[t];
        }
    }
    dp[0][0]=1;
    rep(i,1,nm){
        int v=val[i],cnt=fre[i];
        vector<int> ok(v,-1);
        rep(j,0,n){
            if(dp[i-1][j]) ok[j%v]=j;
            if(ok[j%v]==-1||((j-ok[j%v])/v)>cnt) dp[i][j]=0;
            else dp[i][j]=1,fr[i][j]=ok[j%v];
        }
    }
    if(dp[nm][k]){
        printf("%d\n",mxdep+1);
        //build
    }else{
        printf("%d\n",mxdep+2);
        //build
    }
}
This post is licensed under CC BY 4.0 by the author.
Contents

一月总结

CF1479Div1

Loading comments from Disqus ...