Codeforces Round 958 (Div. 2) solutions (A-D)

ACM
5k words

A - Split the Multiset

正着做是从n拆解到1，反着就是从n个1合并到n，那就尽可能每次合并k个，模拟一下就行（虽然感觉正着想反着想没区别）。

1
2
3
4
5
6
7
8
9
10
void solve(void){
    int n,k;
    cin>>n>>k;
    int ans=0;
    while (n>=k){
        ans+=n/k;
        n=(n/k)+(n%k);
    }
    cout<<ans+(n!=1)<<endl;
}

B - Make Majority

首先全1肯定直接YES了，全0也直接NO。然后从样例数据可以看出来，直接把连续的0合并成一个0，最优。然后是从有0有1的段落进一步合并，因为每次我们要把k个0改掉，要付出至少k+1个1，这样1的个数是随着吞并次数的增加越来越少的，因此我们直接进行一次[1,n]的吞并，显然如果这次不能把所有数都吞成1，之后也再也不会有机会的。直接判断即可。

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
int n;
char str[maxn+5];
 
void solve(void){
    scanf("%d",&n);
    scanf("%s",str+1);
    char ch=str[1];
    bool allsame=true;
    for (int i=2;i<=n&&allsame;i++)
        if (str[i]!=ch)
            allsame=false;
    if (allsame){
        ch=='1'?puts("Yes"):puts("No");
        return ;
    }
    vector<P> block;
    for (int i=1;i<=n;i++)
        if (str[i]!=str[i-1])
            block.push_back(P{str[i],1});
        else
            block.back().second++;
    int cnt_zero=0,cnt_one=0;
    for (P p:block)
        if (p.first=='0')
            p.second=1,cnt_zero++;
        else
            cnt_one+=p.second;
    if (cnt_one>cnt_zero){
        puts("Yes");
        return ;
    }
    else
        puts("No");
}

C - Increasing Sequence with Fixed OR

一开始的时候想到i=(i-1)&mask去了，浪费了一点时间（漏条件了，草）。观察样例可以发现最后一个数必定是n，那就从后往前推，倒数第二个要比n小一点，但是和n或运算后要等于n，那就只能从n的二进制位里面删掉一个1来构造了，肯定是删最小的更优。倒数第三个因为倒数第二个已经失去了n的二进制位里的一个1，要求倒二倒三或运算后等于n，这个1要由倒数第三个来补，补上了低位的1后还要保证比倒数第二个小，那就要扣掉前面的1，因此构造就很明显了，假设

n=(1111011110)2n=(1111011110)_2\\

那就会有

ansk=(1111011110)2ansk−1=(1111011100)2ansk−2=(1111011010)2ansk−3=(1111010110)2ansk−4=(1111001110)2ansk−5=(1110011110)2⋮ans1=(0111011110)2ans_k=(1111011110)_2\\ ans_{k-1}=(1111011100)_2\\ ans_{k-2}=(1111011010)_2\\ ans_{k-3}=(1111010110)_2\\ ans_{k-4}=(1111001110)_2\\ ans_{k-5}=(1110011110)_2\\ \vdots\\ ans_1=(0111011110)_2

到这里就结束了，可以证明这就是最长的kk。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;

ll n;
#define lowbit(x) ((x)&(-(x)))
 
void solve(void){
    cin>>n;
    vector<ll> ans;
    ll mask=n;
    ll x=n;
    ans.push_back(n);
    while (x){
        if (n-lowbit(x))
            ans.push_back(n-lowbit(x));
        x^=lowbit(x);
    }
    cout<<ans.size()<<endl;
    for (int i=ans.size()-1;i>=0;i--)
        cout<<ans[i]<<' ';
    cout<<endl;
}

D - The Omnipotent Monster Killer

感觉样例在暗示贪心，但是稍微想一下就感觉贪心不可能。然后往dp想就被硬控一个小时，最后写完发现时间已经结束了TT（还是太彩了）

一个能否掉贪心的样例是：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
1
7
1 1 10000 10000 1 1 1
1 2
1 3
2 4
2 5
4 6
4 7

输出：
20010

假设怪物u在k回合被杀掉，它给全局生命减量提供的贡献是a[u]*k。对于相邻顶点，他们最终贡献给全局答案的k回合是不同的。

可以猜一下这个最终回合数不会太大，因为太大提供不了更优，并且如果黑白染色后，这个结果已经是比较优的，也就是说我们每次多一个回合，至少能让存活的a值和减少一半。一个合理的猜测是这个最终回合数应该是log⁡n\log n级别的（实际上是k≥⌊log⁡2n⌋+1k\geq \lfloor \log_2n\rfloor +1）。

那直接dp了。设dp[u][k]表示假设在k轮击杀u怪物，u的子树内的伤害总和最小值。在不考虑条件的情况下，dp递推是这样的

dp[u][k]=k×a[u]+∑min⁡t∈[1,max⁡](dp[v][t])dp[u][k]=k\times a[u]+\sum \min_{t\in[1,\max]} (dp[v][t])

但是必须考虑条件。假设v是u的任意一个儿子，因为u不可以和v在同一个轮次被击杀，所以是

dp[u][k]=k×a[u]+∑min⁡t∈[1,max⁡],t≠k(dp[v][t])dp[u][k]=k\times a[u]+\sum \min_{t\in[1,\max] ,t\neq k} (dp[v][t])

因此一个朴素的写法是

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
int n;
ll a[maxn+5];

vector<int> G[maxn+5];

int max_cnt;
ll dp[maxn+5][25]; 

void dfs(int u,int fa){
    for (int k=1;k<=max_cnt;k++)
        dp[u][k]=k*a[u];
    for (int v: G[u])
        if (v!=fa){
            dfs(v,u);
            for (int k=1;k<=max_cnt;k++){
                ll delta=inf;
                for (int j=1;j<=max_cnt;j++)
                    if (k!=j)
                        delta=min(delta,dp[v][j]);
                dp[u][k]+=delta;
            }
        }
}

void solve(void){
    cin>>n;
    max_cnt=(int)log2(n)+1;
    memset(dp,127,sizeof(dp));
    for (int i=1;i<=n;i++)
        G[i].clear();
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    ll ans=inf;
    for (int k=1;k<=max_cnt;k++)
        ans=min(ans,dp[1][k]);
    cout<<ans<<endl;
}

这个写法会TLE。仔细分析一下复杂度应该是O(nlog⁡2n)O(n\log^2n)，可能常数小大T了。仔细看看可以优化这段

1
2
3
4
5
6
7
for (int k=1;k<=max_cnt;k++){
              ll delta=inf;
              for (int j=1;j<=max_cnt;j++)
                  if (k!=j)
                      delta=min(delta,dp[v][j]);
              dp[u][k]+=delta;
          }

其中的min⁡dp[v][j]\min dp[v][j]，实际上可以直接贡献给max_cnt-1的dp[u][k]，剩下一个和轮次重复的，我们取次小值即可。

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
int n;
ll a[maxn+5];

vector<int> G[maxn+5];

int max_cnt;
ll dp[maxn+5][25]; 

void dfs(int u,int fa){
    for (int k=1;k<=max_cnt;k++)
        dp[u][k]=k*a[u];
    for (int v: G[u])
        if (v!=fa){
            dfs(v,u);
            ll minn=inf,min2=inf;
            int pos;
            for (int k=1;k<=max_cnt;k++)
                if (dp[v][k]<minn)
                    min2=minn,minn=dp[v][k],pos=k;
                else if (dp[v][k]<min2)
                    min2=dp[v][k];
            for (int k=1;k<=max_cnt;k++)
                dp[u][k]+=(k!=pos)?minn:min2;
        }
}

void solve(void){
    cin>>n;
    max_cnt=(int)log2(n)+1;
    for (int i=1;i<=n;i++)
        for (int k=1;k<=max_cnt;k++)
            dp[i][k]=inf;
    for (int i=1;i<=n;i++)
        G[i].clear();
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1,u,v;i<n;i++){
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    ll ans=inf;
    for (int k=1;k<=max_cnt;k++)
        ans=min(ans,dp[1][k]);
    cout<<ans<<endl;
}