Codeforces Global Round 23

Codeforces 下分计划 绝赞进行中

Source

Codeforces Global Round 23

A - Maxmina

构造

全 $0$ 则结论平凡 你在哪学的这种数学教材风啊

若有一个 $1$，则一定可以通过不断执行操作 1，将 $n$ 个数减少到 $k$ 个。最后执行操作 2 即可

Code

1746 A

B - Rebellion

贪心

最后一定会成为 $0..01…1$，我们只需要将最后的 $0$ 与最前的 $1$ 不断对调即可

Code

1746 B

C - Permutation Operations

差分，构造

区间修改、对于单调性的判断一定要往差分上面多想想 别老惦记着你那 BIT 逆序对了

令 $d_i = a_{i + 1} - a_i$

改造成递增序列意味着 $d_i$ 均非负，后缀 $[i, n]$ 全部增加 $x$ 意味着 $d_{i - 1}$ 加上 $x$ 且 $\lbrace d\rbrace$ 中其余元素不变

因此注意到，我们第 $i$ 次的操作就是给 $\lbrace d\rbrace$ 中 $n - 1$ 个元素中的某一个加上 $i$，由于 $\lbrace a\rbrace$ 是 $n$ 排列，最极端情况下 $\lbrace d\rbrace$ 是 $n - 1$ 排列，因此我们一定能构造出这样的一组解：

对于 $a_i$，有 $d_{i - 1} = a_i - a_{i - 1} > a_{i - 1}$，故在 $[i, n]$ 后缀加上 $a_{i - 1}$ 即可使得 $d_{i - 1} > 0$

Code

1746 C

D - Paths on the Tree

树形 DP

由题意，一个具有 $s$ 个儿子、能够提供 $p$ 条 path 的结点，每个儿子分配到的 path 应该有 $\lfloor\dfrac{p}{s}\rfloor$ 或 $\lfloor\dfrac{p}{s}\rfloor + 1$ 条

考虑令 $f(u, p)$ 表示以 $u$ 为父结点的树、分配 $p$ 条 path 能获得的最大值，DP 即可

奇怪的是，我脑抽觉得一个 $(u, p)$ 只可能访问一次，没有返回记忆化的值。这种想当然的错误已经在 ICPC 里面犯过一次了（那次是觉得答案不可能超，没取模）

Code

1746 D