手速前三题，D题想到树形dp但是没做出来。

A. Split the Multiset

题意

给你一个多集，一开始这个多集里只有一个数字。每次操作可以选择删掉多集里的一个数，然后添加 \(k\) 个数，并且使得这 \(k\) 个数的和等于删掉的数。问你最少需要操作多少次多集里的数的个数等于等于 \(n\) 。

思路

把每次操作看成添加 \(k-1\) 个数，你需要添加 \(n-1\) 个数。最少的操作次数为 \(\lceil \frac{n-1}{k-1} \rceil\) 。

代码

void solve()
{
    int n,k;
    cin>>n>>k;
    k--,n--;
    if(n==0) cout<<0<<endl;
    else cout<<(n-1)/k+1<<  endl;
}

B. Make Majority

题意

给你一个 \(0/1\) 序列，每次操作可以选择区间 \([l,r]\) ，然后让这段区间变成这段区间内出现最多的数。问你最后能不能让初始序列变成只有一个 \(1\) 。

思路

考虑贪心，为了让最后的序列变成 \(1\) ，那么在最后的序列中 \(1\) 的个数肯定是最多的。那么我们每次就把连续的 \(0\) 给缩成一个 \(0\) 。然后全部缩完之后比较一下序列里面 \(0\) 和 \(1\) 的个数。

代码

void solve()
{
    int n;
    string s;
    cin>>n>>s;
    int num1=0,num0=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1') num1++;
        if(s[i]=='0' && (i==0 || s[i-1]=='1')) num0++;
    }
    if(num1>num0) cout<<"YES\n";
    else cout<<"NO\n";
}

C. Increasing Sequence with Fixed OR

题意

给你一个整数 \(n\) ，让你构造一个最长的序列 \(a\) 满足一下要求:

• 对于所有 \(1\le i\le k\) , \(a_i\le n\) .
• 对于所有 \(2\le i\le k\) , \(a_{i-1}\leq a_i\) .
• 对于所有 \(2\le i\le k\) , \(a_i\,|\,a_{i-1}=n\) .

思路

首先为了让两个数 \(xor\) 起来为 \(n\) ，那么我们能填的最大值只能是 \(n\) 。为了让构造的长度最长， \(n\) 肯定只能填在序列的最后。既然最后一个知道填什么了，那我们就能往前推。为了让构造的序列能够异或出 \(n\) ，那么 \(n\) 在二进制下有 \(1\) 的位置异或出来一定要是 \(1\) 。换句话说，\(a_{i}\) 和 \(a_{i-1}\) 在 \(n\) 是 \(1\) 的位上至少要有一个 \(1\) 。所以我们先记录一下 \(n\) 的哪些位上是 \(1\) 。为了能填更多的数，我们要尽量的让填数最大，直到不能填为止。为了满足以上两种构造条件，我们可以先删掉 \(n\) 最低位的 \(1\) ，即 \(n\) 的 \(\text{lowbit}\) 。然后我们考虑每次把高位上的 \(1\) 向后移动到低位的 \(1\) 上，这样既能保证最大，又能保证异或为 \(n\) 。

代码

void solve()
{
    int n;
    cin>>n;
    vector<int> ans,pos;
    for(int i=0;(1ll<<i)<=n;i++)
    {
        int num=1ll<<i;
        if(num&n) pos.push_back(num);
    }
    ans.push_back(n);
    n-=pos[0];
    if(n==0)//特判一下2的幂次方
    {
        cout<<1<<endl;
        cout<<ans[0]<<endl;
        return;
    }
    ans.push_back(n);
    for(int i=1;i<pos.size();i++)//每次移动就相当于把高位的1移动到下一位是1的位上
    {
        n-=pos[i];
        n+=pos[i-1];
        ans.push_back(n);
    }
    reverse(ans.begin(),ans.end());
    cout<<ans.size()<<endl;

    for(auto x:ans) cout<<x<<' ';
    cout<<endl;
}

D. The Omnipotent Monster Killer

题意

给你一棵树，树上有 \(n\) 个点，每个点都有一个点权。在你每次操作之前你会受到现存点的点权之和的伤害，你每次操作可以选择删除一些点，但是你删除的这些点两两之间不能有边相连。问你删完所有的点受到的最小伤害是多少。

思路

这题拿来一看特别像没有上司的舞会这道题，都是不能同时选定两个相邻的点，然后求最值。（这个东西好像有个名字叫最大独立集还是什么）

但是没有上司的舞会他只需要选一次，并不需要全部选完，这道题要求了全部选完。之后我又考虑到如果这个点不选并且他的儿子也不选，那么这两个点中的其中一个点要等到第三次操作才能选，所以我就特判了一下这种情况，很可惜WA#3了。最后看了 \(\text{LuckyBlock}\) 大佬的博客，我们对于每个点再开一维表示这个点是在哪次操作的时候被移除的。那么此时他对答案的贡献就是 \(j\times a_i\) 。又因为根据某个神秘结论，这棵树至多删 \(log_n\) 次就能全部删除。所以转移的时候直接暴力枚举次数就行了。复杂度 \(O(n{log_n}^2)\) 。

代码

#include<bits/stdc++.h>
void solve()
{
    int n;
    cin>>n;
    vector<int> e[n+1],a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector dp(n+1,vector<int>(22));
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    function<void(int,int)> dfs=[&](int u,int fa)
    {
        for(int i=1;i<=20;i++) dp[u][i]=a[u]*i;
        for(auto v:e[u])
        {
            if(v==fa) continue;
            dfs(v,u);
            for(int j=1;j<=20;j++)
            {
                int minn=1e18;
                for(int k=1;k<=20;k++)
                {
                    if(j==k) continue;
                    minn=min(minn,dp[v][k]);
                }
                dp[u][j]+=minn;
            }
        }
    };
    dfs(1,0);
    int ans=dp[1][1];
    for(int i=1;i<=20;i++) ans=min(ans,dp[1][i]);
    cout<<ans<<endl;
}