随笔题解 Ct. 4
第一次试图在实验室过夜并打 Codeforces Global Round。
d*m「听上去很容易下分的样子。」
85 min 写出来四题我觉得已经可以开香槟了。这波上大分。
于是从考场偷偷溜出来写一写题解（
用户名 CLT，如果想要 AC 代码请去 CF 翻提交记录。（考场代码，不保证可读性）
A. Glory Addicts
您有 $n$ 个技能。第 $i$ 个技能的类型为 $a_i$（只能为 $0$ 或 $1$，$0$ 表示火属性技能，$1$ 表示冰属性技能），威力为 $b_i$。
您需要将这 $n$ 个技能每个释放恰好一遍。
如果释放一个技能时，之前刚刚释放过一个不同类型的技能，那么当前这个技能威力翻倍。
试求所有技能实际威力之和的最大值。
多组数据。$1\leqslant n\leqslant 10^5$，$a_i\in\{0,1\}$，$1\leqslant b_i\leqslant 10^9$。$\sum n\leqslant 10^5$。
$\texttt{2s/512MB}$。
假设火属性技能的数量严格大于冰属性技能的数量，那么有一种思路是：
- 释放威力最低的火属性技能
- 释放威力最高的冰属性技能
- 释放威力最高的火属性技能
- 释放威力第二高的冰属性技能
- 释放威力第二高的火属性技能
- ……（如此重复直到所有的冰属性技能均被释放过）
- 释放剩余的火属性技能
这样一来，所有的冰属性技能和等数量的威力最高的火属性技能被以双倍威力释放。
反过来，如果释放的第一个技能是威力最低的冰属性技能，模拟一遍会发现，除了这个威力最低的冰属性技能的威力从双倍变成了单倍，其他方面没有任何变化。因此，火属性技能较多时，释放的第一个技能应当是火属性技能。
同理，冰属性技能较多时，释放的第一个技能应当是冰属性技能。
但是如果两种技能恰好数量相同，那么就不得不牺牲一个威力最低的技能了（它只能以单倍威力释放）。
B. Prefix Sum Addicts
假设有一个长度为 $n$ 的单调不下降序列 $a$。定义其前缀和序列 $s$ 为
现在给定 $s_{n-k+1},s_{n-k+2},\dots,s_n$，试求是否存在一个符合条件的 $a$。
多组数据。$1\leqslant n\leqslant 10^5$，$1\leqslant k\leqslant n$，$|s_i|\leqslant 10^9$。$\sum n\leqslant 10^5$。
$\texttt{2s/512MB}$。
如果 $k=1$ 那么必定有解。以下考虑 $k\gt 1$。
首先肯定是检查一下它给的这部分 $s$ 是否满足差分单调不下降。
然后如果 $k=n$ 还需要有 $s_1\leqslant s_2-s_1$。
然后令 $x=s_{n-k+2}-s_{n-k+1}$，那么对于所有的 $1\leqslant i\leqslant n-k+1$，需要有 $a_i\leqslant x$。
那么显然只要 $(n-k+1)x\geqslant s_{n-k+1}$ 就必定会有解。至于这个解具体长什么样，这不重要。
C. Even Number Addicts
Alice 和 Bob 在一起玩游戏。
现在他们面前有 $n$ 个数 $a_1,a_2,\dots,a_n$。每次一个人可以选择其中的一个数，将其加入自己的得分，然后将其删去。Alice 先手。
等到所有数都被删去之后，如果 Alice 的得分是偶数，那么 Alice 获胜；否则，即若 Alice 的得分是奇数，那么 Bob 获胜。
Alice 和 Bob 都足够聪明。试判断谁会获胜。
多组数据。$1\leqslant n\leqslant 100$，$|a_i|\leqslant 10^9$。$1\leqslant T\leqslant 100$，这里 $T$ 表示数据组数。
$\texttt{2s/512MB}$。
令 $O(x,y)$ 表示当前剩余 $x$ 个奇数和 $y$ 个偶数，且 Alice 先手时，Alice 能否让自己的最终得分为奇数。
$E(x,y)$ 类似，不过是能否让自己的最终得分为偶数。
首先考虑边界条件。手玩一下可以发现
其中 $\texttt{T}$ 表示 true，$\texttt{F}$ 表示 false。
考虑 $x\geqslant 1$ 且 $y\geqslant 1$ 时。此时 Alice 有两种选择：删去一个奇数，或者删去一个偶数。
如果 Alice 希望她的得分是奇数，且她选择删去一个奇数，那么当前局面变为 $x-1$ 个奇数和 $y$ 个偶数，且 Alice 之后的得分需要是偶数。
此时 Bob 同样有两种选择：（$x\geqslant 2$ 时才可以）删去一个奇数，或者（任何情况都可以）删去一个偶数。
这两种情况分别对应了 $(x=1\vee E(x-2,y))$ 和 $E(x-1,y-1)$。显然只有这两种情况的结果均为 $\texttt{T}$ 时 Alice 才能获胜。
以此类推，还有如下三种情况：
- Alice 希望她的得分是奇数，且她选择删去一个偶数
- Alice 希望她的得分是偶数，且她选择删去一个奇数
- Alice 希望她的得分是偶数，且她选择删去一个偶数
总而言之我们有
其中
读者可自行验证正确性。
D. Permutation Addicts
给定一个长度为 $n$ 的排列 $a_1,a_2,\dots,a_n$ 和 $0\leqslant k\leqslant n$。
现构造序列 $b$。对于每个 $1\leqslant i\leqslant n$：
- 如果 $a_i\leqslant k$，令 $b_{a_i}$ 的值为所有满足 $1\leqslant j\lt i$ 且 $a_j\gt k$ 的 $j$ 中最大的 $j$ 对应的 $a_j$。如果不存在这样的 $j$，令 $b_{a_i}$ 的值为 $n+1$。
- 如果 $a_i\gt k$，令 $b_{a_i}$ 的值为所有满足 $1\leqslant j\lt i$ 且 $a_j\leqslant k$ 的 $j$ 中最大的 $j$ 对应的 $a_j$。如果不存在这样的 $j$，令 $b_{a_i}$ 的值为 $0$。
现给定构造好的 $b$，要求还原出 $k$ 的值和整个的 $a$。多解则任意输出。
多组数据。$1\leqslant n\leqslant 10^5$，$0\leqslant b_i\leqslant n+1$。$\sum n\leqslant 10^5$。输入数据保证有解。
$\texttt{2s/512MB}$。
为了方便，以下称 $\leqslant k$ 的数为小数，$\gt k$ 的数为大数。
如果 $b_y=x$，一种简单的思路就是直接把 $y$ 摆在 $x$ 右侧一个位置。$x=0$ 和 $x=n+1$ 的情况则是摆在排列最左侧。
如果有多个两两不同的 $y_1,y_2,\dots,y_s$ 满足 $b_{y_i}=x$，那么这些 $y_i$ 都摆在 $x$ 右侧最靠近的位置即可，且它们之间的相对顺序无影响。
但是可能会存在一些 $z_1,z_2,\dots,z_t$ 满足 $b_{z_j}=y_{i_0}$，这样的话 $y_{i_0}$ 必须要在其他 $y_i$ 的右侧，然后再往右侧直接接 $z_j$。
考虑到，无论如何，$y_i$ 和 $z_j$ 不可能同时是小数或大数，必定是以下两种情况恰好之一：
- $y_i$ 都是小数，$z_j$ 都是大数。
- $y_i$ 都是大数，$z_j$ 都是小数。
如果存在超过两个 $y_{i_0}$，那么无论如何排列这些 $y_i$，都会出现要么有一些 $z_j$ 无法紧跟在对应的 $y_{i_0}$ 的右侧，要么两个相邻的 $y_j$ 之间插入了一些 $z_j$（这样 $b_{y_j}$ 的值会不对）。这不符合题目的「保证有解」的限制条件，即每次这样的 $y_{i_0}$ 至多存在一个。