1988(958div2)

A. Split the Multiset

多集是一个数字集合，其中可以有相等的元素，数字的顺序并不重要。例如， ${2, 2, 4}$ 就是一个多集合。

你有一个多集合 $S$ 。最初，这个多集合只包含一个正整数 $n$ 。即 $S = {n}$ 。此外，还有一个给定的正整数 $k$ 。

在一次操作中，可以选择 $S$ 中的任意一个正整数 $u$ ，并从 $S$ 中删除一份 $u$ 。然后，在 $S$ 中插入不超过 $k$ 的正整数，使得所有插入的整数之和等于 $u$ 。

求使 $S$ 包含 $n$ 个的最少操作次数。

我觉得无论怎样分，尽量分多一些就是最优了，所以每次都 $k - 1$ 个 1，一个不是 1 这样分，是过了，但是感觉很蠢

void solve() {
    int n, k;cin >> n >> k;
    priority_queue<int>q;
    q.push(n);
    int ans = 0;
    while (q.size()) {
        int x = q.top();q.pop();
        if (x == 1)break;
        if (x > k) {
            q.push(x - k + 1);
        }
        ans++;
    }
    cout << ans << '\n';
}

这个思路和我一样，相当于每次减少 $k - 1$ ，答案则为 $⌈ \frac{n - 1}{k - 1} ⌉$

void solve() {
    int n, k;cin >> n >> k;
    cout << (n + k - 3) / (k - 1) << "\n";
}

B. Make Majority

给您一个序列 $[a 1, . . ., a n]$ ，其中每个元素 $a_{i}$ 要么是 $0$ 要么是 $1$ 。您可以对序列进行若干（可能为零）操作。在每次操作中，您都要选择两个整数 $1 \leq l \leq r \leq | a |$ （其中 $| a |$ 是 $0$ 或 $1$ 。(其中 $| a |$ 是 $a$ 的当前长度），并将 $[a_{l}, \dots, a_{r}]$ 替换为单个元素 $x$ ，其中 $x$ 是 $[a_{l}, \dots, a_{r}]$ 的多数。

这里，由 $0$ 和 $1$ 组成的序列的多数数定义如下：假设序列中分别有 $c_{0}$ 个 0 和 $c_{1}$ 个 1。

如果是 $c_{0} \geq c_{1}$ ，多数为 $0$ 。
如果是 $c_{0} < c_{1}$ ，多数是 $1$ 。

请判断能否用有限次的运算做出 $a = [1]$ 。

先将多个 0 合并在一起(将 0 个数弄到最小)算最有可能得到 $[1]$ ，字符串变为 $1 (k_{1}) 01 (k_{2}) 0$ ，变为这样之后更好处理，若 1 的个数占超过一半则能，否则不能。

void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int cnt0 = 0, cnt1 = 0, ok = 0;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '1') {
            cnt1++;ok = 0;
        } else {
            if (!ok) {
                cnt0++;ok = 1;
            }
        }
    }
    if (cnt1 > cnt0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

C. Increasing Sequence with Fixed OR

给你一个正整数 $n$ 。求满足以下条件的正整数 $a = [a_{1}, a_{2}, \dots, a_{k}]$ 的最长序列：

$a_{i} \leq n$ 。
$a$ 数组严格递增。
$a_{i} OR a_{i - 1} = n$

这个题目难度和 B 相同

只需要每个元素去掉一位为 1 的二进制位即可。所以方法个数是 $popcount(n) + 1$ (还需要加上自身)

坑点：

__builtin_popcount() 参数是 unsigned int，对于 long long 不适用
当数据范围超 int 之后，都需要 1ll<<i 这样，养成习惯
需要特判一下只有一个二进制位是 1 的情况，因为去掉一位之后就是 0 了，而题目要求正整数。需要去掉

#define int long long
void solve() {
    int n;cin >> n;
    int k = 0;
    vector<int>ans;
    for (int i = __lg(n);i >= 0;i--) {
        if ((n >> i) & 1) {
            k++;
            ans.push_back(n - (1ll << i));
        }
    }
    if (k == 1) {
        cout << "1\n" << n << "\n";
        return;
    }
    cout << k + 1 << '\n';
    for (auto x : ans)cout << x << " ";
    cout << n << '\n';
}

D. The Omnipotent Monster Killer

你是怪物杀手，想要杀死一群怪物。这些怪物位于一棵有 $n$ 个顶点的树上。在编号为 $i$ ( $1 \leq i \leq n$ ) 的顶点上，有一个攻击点为 $a_{i}$ 的怪物。你需要与怪物战斗 $10^{100}$ 个回合。

在每个回合中，会依次发生以下情况：

所有活着的怪物攻击你。你的生命值会按照所有活体怪物攻击点的总和减少。
您选择一些（可能是全部，也可能是一个都没有）怪物并杀死它们。被杀死后，怪物将无法再进行任何攻击。

有一个限制条件：在一个回合内，您不能杀死由一条边直接相连的两只怪物。

如果您以最佳方式选择攻击的怪物，那么在所有回合后，受到的最小伤害是多少？

Solution

若这个题目只有一个回合，实际上就是树的最大权值的独立集。即没有上司的舞会

树形 DP

$d p_{i, j}$ 代表在 $i$ 的子树中， $i$ 节点是第 $j$ 次删除。在某个子树(顶点个数为 $n$ )中，最多 $\log n$ 次就可以将这个子树删光。

$d p_{u, i} = \sum_{v \in s o n (u)} min_{i \neq j} d p_{v, j} + i \times a_{u}$

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    vector<array<int, 30>> dp(n + 1);
    auto dfs = [&](auto self, int u, int fa = -1)->void {
        for (int i = 1; i <= 25; i++) dp[u][i] = a[u] * i;
        for (auto v : g[u]) {
            if (v == fa) continue;
            self(self, v, u);
            for (int i = 1; i <= 25; i++) {
                int mn = 9e18;
                for (int j = 1; j <= 25; j++)
                    if (i != j) mn = min(mn, dp[v][j]);
                dp[u][i] += mn;
            }
        }
        };

    dfs(dfs, 1);
    int res = 9e18;
    for (int i = 1; i <= 25; i++) res = min(res, dp[1][i]);
    cout << res << '\n';
}

E. Range Minimum Sum

对于长度为 $n$ 的数组 $[a_{1}, a_{2}, \dots, a_{n}]$ ，定义 $f (a)$ 为所有子段的最小元素之和。也就是说

f (a) = \sum_{l = 1}^{n} \sum_{r = l}^{n} min_{l \leq i \leq r} a_{i} .

一个排列是长度为 $n$ 的从 $1$ 到 $n$ 的整数序列，其中每个数都恰好包含一次。给你一个排列 $[a_{1}, a_{2}, \dots, a_{n}]$ 。请为每个 $i$ 独立解决下面的问题：

从 $a$ 中删除 $a_{i}$ ，连接剩余部分，得到 $b$ 。
计算 $f (b)$ 。

待补，目前无计划...