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

A - Split the Multiset #

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

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

B - Make Majority #

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

1
int n;
2
char str[maxn+5];
3

4
void solve(void){
5
    scanf("%d",&n);
6
    scanf("%s",str+1);
7
    char ch=str[1];
8
    bool allsame=true;
9
    for (int i=2;i<=n&&allsame;i++)
10
        if (str[i]!=ch)
11
            allsame=false;
12
    if (allsame){
13
        ch=='1'?puts("Yes"):puts("No");
14
        return ;
15
    }
16
    vector<P> block;
17
    for (int i=1;i<=n;i++)
18
        if (str[i]!=str[i-1])
19
            block.push_back(P{str[i],1});
20
        else
21
            block.back().second++;
22
    int cnt_zero=0,cnt_one=0;
23
    for (P p:block)
24
        if (p.first=='0')
25
            p.second=1,cnt_zero++;
26
        else
27
            cnt_one+=p.second;
28
    if (cnt_one>cnt_zero){
29
        puts("Yes");
30
        return ;
31
    }
32
    else
33
        puts("No");
34
}

C - Increasing Sequence with Fixed OR #

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

n=(1111011110)_2\\

那就会有

ans_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

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

1
typedef long long ll;
2

3
ll n;
4
#define lowbit(x) ((x)&(-(x)))
5

6
void solve(void){
7
    cin>>n;
8
    vector<ll> ans;
9
    ll mask=n;
10
    ll x=n;
11
    ans.push_back(n);
12
    while (x){
13
        if (n-lowbit(x))
14
            ans.push_back(n-lowbit(x));
15
        x^=lowbit(x);
16
    }
17
    cout<<ans.size()<<endl;
18
    for (int i=ans.size()-1;i>=0;i--)
19
        cout<<ans[i]<<' ';
20
    cout<<endl;
21
}

D - The Omnipotent Monster Killer #

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

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

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

12
输出：
13
20010

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

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

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

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

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

dp[u][k]=k\times a[u]+\sum \min_{t\in[1,\max] ,t\neq k} (dp[v][t])

因此一个朴素的写法是

1
int n;
2
ll a[maxn+5];
3

4
vector<int> G[maxn+5];
5

6
int max_cnt;
7
ll dp[maxn+5][25];
8

9
void dfs(int u,int fa){
10
    for (int k=1;k<=max_cnt;k++)
11
        dp[u][k]=k*a[u];
12
    for (int v: G[u])
13
        if (v!=fa){
14
            dfs(v,u);
15
            for (int k=1;k<=max_cnt;k++){
16
                ll delta=inf;
17
                for (int j=1;j<=max_cnt;j++)
18
                    if (k!=j)
19
                        delta=min(delta,dp[v][j]);
20
                dp[u][k]+=delta;
21
            }
22
        }
23
}
24

25
void solve(void){
26
    cin>>n;
27
    max_cnt=(int)log2(n)+1;
28
    memset(dp,127,sizeof(dp));
29
    for (int i=1;i<=n;i++)
30
        G[i].clear();
31
    for (int i=1;i<=n;i++)
32
        cin>>a[i];
33
    for (int i=1,u,v;i<n;i++){
34
        cin>>u>>v;
35
        G[u].push_back(v);
36
        G[v].push_back(u);
37
    }
38
    dfs(1,0);
39
    ll ans=inf;
40
    for (int k=1;k<=max_cnt;k++)
41
        ans=min(ans,dp[1][k]);
42
    cout<<ans<<endl;
43
}

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

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

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

1
int n;
2
ll a[maxn+5];
3

4
vector<int> G[maxn+5];
5

6
int max_cnt;
7
ll dp[maxn+5][25];
8

9
void dfs(int u,int fa){
10
    for (int k=1;k<=max_cnt;k++)
11
        dp[u][k]=k*a[u];
12
    for (int v: G[u])
13
        if (v!=fa){
14
            dfs(v,u);
15
            ll minn=inf,min2=inf;
16
            int pos;
17
            for (int k=1;k<=max_cnt;k++)
18
                if (dp[v][k]<minn)
19
                    min2=minn,minn=dp[v][k],pos=k;
20
                else if (dp[v][k]<min2)
21
                    min2=dp[v][k];
22
            for (int k=1;k<=max_cnt;k++)
23
                dp[u][k]+=(k!=pos)?minn:min2;
24
        }
25
}
26

27
void solve(void){
28
    cin>>n;
29
    max_cnt=(int)log2(n)+1;
30
    for (int i=1;i<=n;i++)
31
        for (int k=1;k<=max_cnt;k++)
32
            dp[i][k]=inf;
33
    for (int i=1;i<=n;i++)
34
        G[i].clear();
35
    for (int i=1;i<=n;i++)
36
        cin>>a[i];
37
    for (int i=1,u,v;i<n;i++){
38
        cin>>u>>v;
39
        G[u].push_back(v);
40
        G[v].push_back(u);
41
    }
42
    dfs(1,0);
43
    ll ans=inf;
44
    for (int k=1;k<=max_cnt;k++)
45
        ans=min(ans,dp[1][k]);
46
    cout<<ans<<endl;
47
}

A - Split the Multiset#

B - Make Majority#

C - Increasing Sequence with Fixed OR#

D - The Omnipotent Monster Killer#

A - Split the Multiset #

B - Make Majority #

C - Increasing Sequence with Fixed OR #

D - The Omnipotent Monster Killer #