题目链接：Codeforces Round 958 (Div. 2)
总结：C因为常数没转\(long long\) \(wa\)两发，难绷。
A. Split the Multiset
fag：模拟
Description：给定一个\(n\)和一个\(k\)，每次可以将\(n\)减掉一个数\(u\)，然后插入\(x\)个数，\(x <= k\)，并且插入的数之和等于\(u\)。求将其转化为全\(1\)的最小操作次数。
Solution：因为最后要得到全\(1\)，所以每次操作我们插入尽可能多的\(1\)，即插入\(1, 1, ..., u - (k - 1)\)。相当于每次将\(n\)减少\(k - 1\)。那么答案为\(k --, (n - 1 + k - 1) / k\)，这里是向上取整。
void solve(){
cin >> n >> k;
k --;
if (n == 1){
cout << 0 << endl;
return;
}
n --;
cout << (n + k - 1) / k << endl;
}
B. Make Majority
fag: 思维
Description: 给定一个只含\(0\)或\(1\)的字符串，每次操作可以选择一个区间\(l, r\)，将这个区间变为一个数（区间内出现次数最多的数）。
问能否将其变为\(1\)。
Solution：手摸几组样例发现：我们可以把所有连续的多个\(0\)变为一个\(0\)，如果我们需要将一个\(0\)去掉，那么至少需要两个\(1\)。
- 那么统计连续\(0\)的区间个数\(x\)，\(1\)的个数\(y\)。
- 当\(y >= x + 1\)时，有解，否则无解。
void solve(){
cin >> n;
cin >> s;
int x = 0, y = 0;
for (int i = 0; i < n; i ++){
if (s[i] == '0')
x ++;
else
y ++;
}
int xx = 0;
bool flag = true;
for (int i = 0; i < n; i ++){
if (s[i] == '0' && flag){
xx ++;
flag = false;
continue;
}
if (s[i] == '1')
flag = true;
}
if (y >= xx + 1){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
C. Increasing Sequence with Fixed OR
fag：位运算
Description：给定一个\(n\)，求一个最长的序列，序列满足\(ai < a_{i +1}\)，且\(a_i | a_{i + 1} == 1\)。输出序列的长度和序列值。
Solution：显然我们需要将\(n\)转化为二进制。模拟样例后发现，如果\(n\)的二进制含有\(x\)个\(1\)，那么序列长度为\(x + 1\)。
然后考虑如何构造。我们只需要依次去掉低位\(1\)，就可以满足以上要求。注意对常数进行位运算时，需要将其强制转化为long long
void solve(){
cin >> n;
vector<int> ans;
ans.eb(n);
for (int i = 0; i < 64; i ++){
if (n >> i & 1){ // 这一位是1
ans.eb(n ^ (1LL << i)); // 注意这里
}
}
if (ans[ans.size() - 1] == 0) // 注意特判
ans.pop_back();
cout << ans.size() << endl;
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i ++){
cout << ans[i] << " ";
}
cout << endl;
}
D. The Omnipotent Monster Killer
fag：树形DP
Description：一颗有\(n\)个点的数，每个点有一个权值\(a_i\)，每回合所有点会对玩家造成大小为自身权值的伤害。玩家每回合可以消灭一些点（不能删除被一条边相连的两点）。求玩家受到的最小伤害。
1 <= n <= 3e5
1 <= ai <= 1e12
Solution：只需要最多\(L\)个回合即可，\(L <= log_{2}n + 1\)，我们令\(L = 20\)即可，不太会证。
-
如果一个节点在第\(i\)个回合删除，那么它的伤害为\(i * a_{i}\)
-
令\(f[x][j]\)表示，\(x\)节点在第\(j\)个回合删除，以\(x\)为根的子树的伤害最小值。\(f[x][j] = j * a_x + \sum_{i \in son(x)}min(f[i][k]), k != j\)
-
答案\(ans\): \(min(f[0][j], 1 <= j <= 20)\)
void solve(){
cin >> n;
vector<int> a(n);
vector g(n, vector<int>());
vector f(n, vector<int>(21, 0));
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n - 1; i ++){
int a, b;
cin >> a >> b;
a --, b --;
g[a].eb(b), g[b].eb(a);
}
auto dfs = [&](auto self, int u, int v) -> void {
for (int i = 1; i <= 20; i ++){
f[u][i] = i * a[u];
}
for (auto x : g[u]){
if (x == v)
continue;
self(self, x, u);
for (int i = 1; i <= 20; i ++){
int mi = 1e18;
for (int j = 1; j <= 20; j ++){
if (i == j)
continue;
mi = min(mi, f[x][j]);
}
f[u][i] += mi;
}
}
};
dfs(dfs, 0, -1);
int ans = 1e18;
for (int i = 1; i <= 20; i ++){
ans = min(ans, f[0][i]);
}
cout << ans << endl;
}