Codeforces Round 958 (Div. 2)

$CodeforcesRound958(Div.2)$

比赛链接：https://codeforces.com/contest/1988

Problems A. Split the Multiset

题意

给出一个数组，每次可以选择数组中的一个数，并将其拆为不超过$k$个数。

问最少需要几次可以构造出全$1$数组（数组中只包含$1$）。

思路

贪心的想，我们每次可以将选出的数字x拆为1+1+1+…+(x-k+1)。

那么结果即为：
$$\lceil \frac{n-1}{k-1}\rceil$$

标程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);void Solved() {int n, k; cin >> n >> k;n --;cout << (n + k - 2) / (k - 1) << endl;
}signed main(void) {IOSint ALL = 1; cin >> ALL;while(ALL -- ) Solved();return 0;
}

Problems B. Make Majority

题意

给出一个$01$串，每次可以选择一个区间，若区间$su{m}_0\ge su{m}_1$，则将该区间变为一个数字$0$，否则变为一个数字$1$。

求是否可以令$01$串最后变为一个数字$1$。

思路

贪心的想，我们每次可以令全$0$子串变为一个$0$。

然后容易发现，对比现在子串中的$0,1$个数即可判断是否能构造出数字$1$。

标程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define endl '\n'void Solved() {int n; cin >> n;string s; cin >> s;int c0 = 0, c1 = 0;string s1;for(int i = 0; i < n;  i ++ ) {if(s[i] == '0') {c0 ++;if(i == 0 || (i && s[i - 1] == '1')) s1 = s1 + '0'; }else {c1 ++;s1 = s1 + s[i];}}int x= 0, y = 0;for(int i = 0; i < s1.size(); i ++ ) {if(s1[i] == '0') x ++;else y ++;}if(c1 > c0) {cout << "YES\n"; return;}if(x < y) cout << "YES\n";else cout << "NO\n";
}signed main(void) {IOSint ALL = 1; cin >> ALL;while(ALL -- ) Solved();return 0;
}

Problems C. Increasing Sequence with Fixed OR

题意

给出一个正整数$n$，要求构造出一个序列：

• $a_i\le n(1\le i\le k)$。

• $a_i>a_{i-1}(2\le i\le k)$，$a$数组是严格递增的

• $a_i|a_{i-1}=n(2\le i\le k)$， $|$ 表示按位异或操作。

要求构造出一个符合要求的最长的序列并输出。

思路

考察位运算。

很明显能发现，构造出的数列的最后一项一定是$n$，因此我们考虑从后往前构造。

为了符合递增和相邻数字异或和为$n$，我们考虑从低位到高位，依次让二进制下为$1$的位变为零；对于该题，这即是最优情况。

但是需要特判一下当二进制下只有$1$位$1$时，能构造出来的序列只有其本身，特判即可。

标程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long 
#define endl '\n'void Solved() {int n; cin >> n;bitset<63> b(n);vector<int> a;int sum = 0, x = -1;for(int i = 0; i < 64; i ++ ) {if(b[i] == 1) {sum ++;a.push_back(i);}if(b[i] == 1 && x == -1) x = i;}x = 64 - x;if(sum == 1) {cout << "1\n" << n << endl; return;}int t = n, k = 0;vector<int> v;for(int i = a.size() - 1; i >= 0; i -- ) {k ++;t = t - (1ll << (a[i]));for(int j = i + 1; j < a.size(); j ++ ) {t |= (1ll << (a[j]));}v.push_back(t);}v.push_back(n);cout << k + 1 << endl;for(auto i : v) cout << i << ' ';cout << endl;}signed main(void) {IOSint ALL = 1; cin >> ALL;while(ALL -- ) Solved();return 0;
}

Problems D. The Omnipotent Monster Killer

题意

有一颗树，树上有若干的怪物，每个怪物有对应的攻击值；每回合都会按顺序发生下面两种情况：

1. 所有存活的怪物攻击你，你的生命值将会减少其攻击值的总和。
2. 选择若干怪物杀掉，选择的限制条件是：不能同时选择一条边上的两只怪物。

当杀死全部怪物后结束游戏。求最少受到的攻击值。

思路

树形DP

假设游戏进行的回合数为$L$，怪物$i$在第$S_i$轮被杀死，并且满足同一条边上的两只怪物$i,j(S_i!=s_j)$，那么攻击值为：
$$\sum _{i=1}^L{a}_i\times S_i$$
然后我们会发现本题的求解思路和这道题相同：P4395 [BOI2003] Gem 气垫车 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 。

关于树形DP练习，可以参考这一篇博客：树形dp（学习过程+刷题总结）

对于本题，我们可以用时间复杂度为$O(n{L}^2)$来进行树形DP，用二维数组$f_{x,j}$表示$S_x=j$时，以$x$为根的子树价值之和的最小值，则有：
$$f_{x,j}=S_x\times a_x+\sum _{i\in son(x)}\underset{S_J!=S_x}{\min }(f_{i,j})$$
那么答案即为：
$$\underset{1\le i\le L}{\min }(f_{1,i})$$
关于$L$的范围：$L\le \lfloor {\log }_{2}n\rfloor +1$

标程

#include<bits/stdc++.h>using namespace std;#define IOS ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
#define int long long 
#define endl '\n'const int N = 3e5 + 10; vector<int> a(N), b[N], f[N];void dfs(int x, int y) {for(int i = 1; i <= 20; i ++ ) {f[x][i] = i * a[x];}for(auto i : b[x]) {if(i == y) continue;dfs(i, x);for(int j = 1; j <= 20; j ++ ) {int mi = (j == 1 ? f[i][2] : f[i][1]);for(int k = 1; k <= 20; k ++ ) {if(j == k) continue;mi = min(mi, f[i][k]);}f[x][j] += mi;}}
}void Solved() {int n; cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> a[i];f[i].clear(); f[i].resize(21);b[i].clear();}for(int i = 1; i < n; i ++ ) {int x, y; cin >> x >> y;b[x].push_back(y); b[y].push_back(x);}dfs(1, 0);int res = f[1][1];for(int i = 1; i <= 20; i ++ ) {res = min(res, f[1][i]);}cout << res << endl;
}signed main(void) {IOSint ALL = 1; cin >> ALL;while(ALL -- ) Solved();return 0;
}