Educational Codeforces Round 168 (Rated for Div. 2)

明早再补，睡睡睡。

A. Strong Password

给定一个字符串，若 \(s_i \neq s_{i-1}\)，则 \(s_i\) 的代价为2，否则为1。

向这个字符串中插入一个字符，使得代价最大。

在相邻相同的两个字符中间插入即可，没有相邻相同就在末尾插入，插入的字符与前后字符不同。

---

B. Make Three Regions

有一个 \(2 \times n\) 的房间，相邻房间可以相互到达，能够相互到达的房间构成一个区域，一些房间不能进入（经过）。保证读入的房间至多有一个区域。

问有多少个可进入的房间满足，删去这个房间后剩余房间构成三个区域？

只有当房间这样分布时，才满足条件。

0	0	0
1	0	1

---

C. Even Positions

给定一个残缺的长度为 \(n\) 的括号序列。（\(n\) 为偶数）

所有奇数位残缺，填上残缺位使括号序列合法，且代价最小。

括号序列的代价定义为所有括号对的代价，一对括号对的代价定义为左右括号的距离。

对于每一个奇数位，贪心的填括号，如果前面有左括号，那么填右括号和它匹配。否则填右括号。

由于是奇数位，所以前面一定有偶数个左括号，若为0则填右括号。若不为0，则至少有两个左括号，填上右括号不会出现下一个偶数位匹配的情况。

---

D. Maximize the Root

给定一颗以1为根的有根树，每个节点有一个初始权值 \(a_i\)。

可以执行任意次如下操作：

选取一个节点 \(i\)，使 \(a_i = a_i + 1\)，并使它的子树内所有其他节点 \(j\)，\(a_j = a_j - 1\)。

求 \(a_1\) 的最大值。

设 \(dp[i]\) 表示以 \(i\) 为根的子树中，最少的数为 \(dp[i]\)。（也就是能被 \(fa_i\) 操作 \(dp[i]\) 次）

转移时记 \(mx = max\{dp[son_i]\}\)。

若 \(a_i \ge mx\)，则 \(dp[i] = mx\)。

若 \(a_i < mx\)，则 \(dp[i] = \lfloor \frac{a_i + mx}{2} \rfloor\)。

---

E. Level Up

Monocarp在玩游戏，最初战斗力为1，他会依次挑战 \(n\) 只怪物。

若Monocarp的战力严格高于当前怪物，当前怪物会直接逃跑，否则会和Monocarp对决。

Monocarp每对决 \(k\) 次，战斗力会加1。

\(q\) 次询问，每次给定 \(k\) 和 \(i\)，问当升级间隔为 \(k\) 时，第 \(i\) 只怪物时候会和Monocarp对决？

容易发现，若第 \(i\) 只怪物能在升级间隔为 \(k\) 时和Monocarp对决，那么当升级间隔为 \(k + 1\) 时也一定会和Monocarp对决，具有单调性。

注意到当升级间隔为 \(k\) 时，最多升级 \(\lfloor \frac{n}{k} \rfloor\)，总共会升级

\[\sum_{i = 1}^{n} \lfloor \frac{n}{i} \rfloor \sim n \log n \]

次。

设 \(f_{i, j}\) 表示当升级间隔为 \(i\) 时，战斗力为 \(j\) 的最后一场对决的对手是第 \(f_{i, j}\) 只怪物。

转移时，需要找到区间 \([f_{i, j} + 1, n]\) 中战斗力大于 \(j\) 的第 \(i\) 只怪物。若没有则 \(f_{i, j + 1} = n + 1\)。

可以权值线段树上二分实现 \(O(\log n)\) 转移。

具体的，对于战斗力大于 \(j\) 的限制，可以通过改变枚举顺序，先枚举 \(j\) ，并将小于等于 \(j\) 的数在权值线段树上删去。

对于区间左端点的限制，可以用前缀和做差，即先查出区间 \([1, f_{i, j}]\) 中战斗力大于 \(j\) 的怪物数 \(sum\)，并计算区间 \([1, n]\) 上战斗力大于 \(j\) 的第 \(sum + i\) 只怪物。

复杂度 \(O(n \log^2 n)\)

我有一个跑的飞快的复杂度为 \(O(n \log n)\) 整体二分的方法，但是过于抽象，难以解释。

---

F. Chips on a Line