Codeforces Round 958 (Div. 2)

[比赛链接https://codeforces.com/contest/1988](https://codeforces.com/contest/1988)

A. Split the Multiset

题意

起初$S$中只有一个数字 $n$ , 你每次操作可以选择$S$中的一个任意一个数$x$，将他拆分成最多k个数，并且这k个数的和仍为$x$ ，问最少需要多少次拆分，能让$S$中只剩下$n$个$1$

思路

可以发现，每次拆分出$k-1$ 个 1 效率最高。 所以对于$n,k$ ,我们有总拆分次数为undefinedlceil \frac{n-1}{k-1} \rceil$ 。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n,k;
    cin>>n>>k;
    cout<< (n -1 + k - 2) / (k - 1)<<endl;
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B. Make Majority

题意

给你一个长度为n的01序列$a$，你可以进行任意次如下操作：

1. 选择两个数$l,r (1\le l\le r \le |a|)$ , 其中 $|a|$ 表示a的长度。
2. 将这段区间替换为$c$， (如果选择的区间中1的数量**大于**0的数量，那么c=1，否则c=0）

问能否在进行一定次数的操作后， 使得a变为 1

思路

首先我们可以先选择连续的0 ， 这样这些连续的0就一定会变为一个0 。这样每个0周围都会有1~2个1 。 我们说此刻的序列为$a'$

于是我们每次可以选择一个0，以及它旁边的两个1， 这样这三个数就会被替换为。不断循环往复， 每次替换都会减少一个1以及一个0。 因此我们直接统计$a'$ 中1和0的数量，若1的数量更多那么就输出$Yes$, 否则输出$No$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    string s;
    rep(i,0,n-1){
        if(str[i] == '0'){
            s += str[i];
            while(i<n && str[i] == '0') i++;
        }
        if(i == n) continue;
        s += str[i];
    }
    int c0 = 0,c1 = 0;
    for(auto p : s){
        if( p == '0') c0 ++;
        else c1 ++;
    }
    if(c0 >= c1) cout<<"No\n";
    else cout<<"Yes\n";
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C. Increasing Sequence with Fixed OR

题意

给你一个数$n$ , 请你构造一个数列$a$ , 使得$1 \le a_1 < a_2 < ... < a_k$ , 并且对于任意的$2\le i \le k$ 都有 $a_{i-1} | a_i = n$ 其中|表示按位或运算。要求你构造的$k$尽可能大。

思路

因为要求相邻的数按位或都是n， 所以对于任意的 $a_i$ ，一定有$a_i | n = n$， 即$a_i$ 一定是从二进制的n中选择一些1来组成。于是我们便只需要考虑n为全1的情况即可（因为n中的数位0在 $a_i$ 中一定为$0$ )

• 因为$a_i | a_{i+1} = n$ 所以对于某一位$j$ ,若$a_{i,j} = 0$ 那么 一定有$a_{i+1,j} = 1$ 。
• 再根据另一个条件$1 \le a_1 < a_2 < ... < a_k$ ，我们可以得知，当$a_{i,j} = 1$ 时 ，那么$a_{i+1,j},a_{i+2,j},...,a_{k,j}$ 都是1。

于是我们便可以这样构造我们的数列：01111,10111,11011,11101,11110,11111 , 于是若n的二进制中中有t个1，那么我们构造的数列长度便为$t+1$ . 构造方法即 **让0从高到低地位于t个位中的每一位，最后再加上n本身**。

需要注意的是，如果n是二进制数， 即n中只有一位1，那么答案是1，数列的值为n本身。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;

void solve(){
    int n;
    cin>>n;
    vector<int> v;
    for(int i = 0;i<63;i++){
        if((1ll<<i) & n){
            v.push_back(i);
        }
    }
    if(v.size() == 1) {cout<<1<<'\n'<<n<<'\n';return ;}
    cout<<(v.size()+1)<<endl;
    for(int i = v.size()-1;i>=0;i--){
        int t = n;
        t ^= (1ll<<v[i]);
        cout<<t<<" ";
    }
    cout<<n<<'\n';

}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D. The Omnipotent Monster Killer

题意

有$n$头怪兽， 每个怪兽都有其自己的攻击力，他们通过$n-1$条边连成一个树。 你可以进行足够多的回合。在每个回合中， 会进行如下过程：

1. 所有活着的怪兽都对你造成一次等同于其攻击力的伤害
2. 你选择一些怪兽（这些怪兽不能相邻），将他们杀死

问最少受到多少伤害，你才能够杀死所有的怪物。

思路

首先可以发现，对于n头怪兽，我们最多需要 $log_2n$ 个回合就可以在最优解的情况下将他们全部击杀。（考虑完全树）。

这样对于$n < 3 * 10^5$ ,总回合数最多19个回合就可以将他们全部击败。

于是我们考虑树形dp， 设定节点1为$dp[i][j]$ 表示节点$i$在第$j$ 个回合被杀死，那么以它为根节点的子树所造成的总伤害。

于是有：

最终答案：$ans = min_{1\le j \le 19} dp[1][j]$

状态转移：$dp[i][j] = \sum_{v\in sons(i)} min_{1\le k\le 19 \& k \not=j} dp[v][k] + ack[i] * j$

复杂度$O(n * log^2n)$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int dp[300005][25];
int ack[300005];
vector<int> edge[300005];
void dfs(int u,int fa){
    for(int i = 1;i<=22;i++){
        dp[u][i] = INF;
    }
    for(auto p : edge[u]){
        if(p == fa) continue;
        dfs(p,u);
    }
    for(int j = 1;j<=22;j++){
        bool f = 0;
        dp[u][j] = 0;
        for(auto p : edge[u]){
            if(p == fa) continue;
            f = 1;
            int mn = INF;
            for(int k = 1;k<=22;k++){
                if(k == j) continue;
                   mn = min(mn,dp[p][k]);
            }
            dp[u][j] += mn;
        }
        dp[u][j] += ack[u] * j;
    }
    return ;
}
void solve(){
    int n;
    cin>>n;
    rep(i,1,n) cin>>ack[i];
    if(n == 1) {cout<<ack[1] << endl; return ;}
    rep(i,1,n) edge[i].clear();
    for(int i = 1;i<n;i++){
        int x ,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,0);
    int ans = INF;
    for(int i= 1;i<=22;i++){
        ans = min(ans,dp[1][i]);
    }
    cout<<ans<<'\n';
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

优化$O(nlogn)$

对于递推过程，如果我们用前缀/后缀 数组记录 前缀最小值，以及后缀最小值。

即$pre[u][i] = MIN_{1\le j\le i} dp[u][j] \\lst[u][i] = MIN_{i\le j\le 19} dp[u][j]$

于是我们在递推时就可以直接写$dp[i][j] = \sum_{v\in sons(i)} min(pre[v][j-1],lst[v][j+1]) + ack[i] * j$ 。

我们就可以省去一层循环。 实现复杂度$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int dp[300005][25];
int ack[300005];
vector<int> edge[300005];
int pre[300005][25];
int lst[300005][25];
void dfs(int u,int fa){
    for(int i = 1;i<= 19;i++){
        dp[u][i] = INF;
    }
    for(auto p : edge[u]){
        if(p == fa) continue;
        dfs(p,u);
    }
    for(int j = 1;j<= 19;j++){
        bool f = 0;
        dp[u][j] = 0;
        for(auto p : edge[u]){
            if(p == fa) continue;
            f = 1;
			//直接利用前后缀求出mn
            int mn = min(pre[p][j-1],lst[p][j+1]);
            dp[u][j] += mn;
        }
        dp[u][j] += ack[u] * j;
    }
	// 求前后缀
	pre[u][0] = INF;
	for(int i = 1;i<= 19;i++){
		pre[u][i] = min(dp[u][i],pre[u][i-1]);
	}
	lst[u][20] = INF;
	for(int i =  19;i>=1;i--){
		lst[u][i] = min(dp[u][i],lst[u][i+1]);
	}
    return ;
}
void solve(){
    int n;
    cin>>n;
    rep(i,1,n) cin>>ack[i];
    if(n == 1) {cout<<ack[1] << endl; return ;}
    rep(i,1,n) edge[i].clear();
    for(int i = 1;i<n;i++){
        int x ,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,0);
    int ans = INF;
    for(int i= 1;i<= 19;i++){
        ans = min(ans,dp[1][i]);
    }
    cout<<ans<<'\n';
}
signed main(){
    int T = 1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

优化$O(n)$

如果再细心一些，可以发现，对于一个节点$i$ , 设它的度数为$deg_i$ ， 它会在第$b_i$ 轮被杀死， 那么一定有$b_i \le deg_i$ 。于是我们没必要对每个结点都循环到19, 只需要循环到它对应的度数即可。