对于 CodeForces 1049 Div.2 的题解~
C - A Ultimate Value
设 $f=\mathrm{cost}+(a_1-a_2+a_3-a_4\cdots a_n)$。进行如下操作无穷次，Alice 想最大化 $f$，Bob 想最小化 $f$。Alice 先手。
- 选择 $1\le l\le r\le n$，交换 $a_l,a_r$，$\mathrm{cost}$ 增大 $r-l+1$。
- 结束游戏。
当 Bob 交换一对 $(l,r)$ 时，Alice 可以换回来。这样，在序列不变的同时，$\mathrm{cost}$ 会增大。因此只要轮到 Bob，Bob 必然选择结束游戏，否则必然不优。因此，只需考虑 Alice 的第一次操作即可。如果选择交换下标奇偶性相同的两个位置，答案只会增加相应的长度，这显然要选左右极值的。因此，做出如下分类讨论：
- $L$ 奇 $R$ 偶。
- 那么答案增值为 $R-L+1+2a_R-2a_L$。我们分别维护 $\max(-2a_L-L)$ 与 $\max(2a_R+R)$，注意 $L<R$，可以 $\mathcal O(n)$ 地计算。
- $L$ 偶 $R$ 奇。
- 那么答案增值为 $R-L+1-2a_R+2a_L$。我们分别维护 $\max(2a_L-L)$ 与 $\max(-2a_R+R)$，注意 $L<R$，可以 $\mathcal O(n)$ 地计算。
- $L$ 与 $R$ 奇偶性相同。
- 答案增值为 $\begin{cases}n-1,&n\text{ is odd.}\ n-2,&n\text{ is even.}\end{cases}$
最后对上面三个增值取 $\max$ 即可。
考虑一个 corner case：$n=2$。若 $a_1>a_2$，直接结束游戏。反之，交换 $a_1,a_2$ 后结束游戏。这一点要十分注意相等情况，导致了我被卡了 1h。
D - A Cruel Segment’s Thesis
给出 $N$ 条线段 $[l_i,r_i]$，求两两匹配，使每一对 $(i,j)$ 的 $r_j-l_i$ 和最大。
一个显然的思路使选 $\dfrac n2$ 个 $R$ 最大的，减掉 $\dfrac n2$ 的 $L$ 最小的。然而可能 $L$ 与 $R$ 同属一条线段。写出答案的贡献式：
$$\begin{aligned}\sum\limits_{i\in H}r_i-\sum\limits_{i\in L}l_i&=\sum\limits_{i=1}^n r_i-\sum\limits_{i\in L}(l_i+r_i)\end{aligned}$$
可以发现，我们只需最小化 $\sum\limits_{i\in L}(l_i+r_i)$ 就能最大化答案。
对于奇数的情况，继续写式子：
$$\begin{aligned}\sum\limits_{i\in H}r_i-\sum\limits_{i\in L}l_i&=\sum\limits_{i=1}^n r_i-\sum\limits_{i\in L}(l_i+r_i)-r_{rest}\end{aligned}$$
其中 $r_{rest}$ 是剩下未匹配的那个线段的右端点。发现只需要枚举每条线段作为 $rest$ 的情况（若 $rest$ 在算的 $L$ 中，只需向后顺延一位即可，这是 $\mathcal O(1)$ 的），就算完答案了。
E1. Prime Gaming (Easy Version)
给出长度为 $n\le 20$，值域为 ${1,2}$ 的序列 $A$ 以及合法索引。可以进行如下操作：
- 选择一个 合法 索引 $i$，删除，并将序列重新标号。
- 只剩下一个，结束游戏。
Alice 希望最大化剩下的值，Bob 希望最小化。Alice 先手。求所有序列 $A$ 的最终剩余值之和，对 $10^9+7$ 取模。
设 $f_{n,S}$ 表示 Alice 先下，长度为 $n$ 的序列 $S$ 的答案。$g_S$ 表示 Bob 先手下，长度为 $n$ 的序列 $S$ 的答案。
$n$ 很小，考虑暴力枚举所有序列 $A$。发现 $f_{n,S}$ 使可以转移的。也就是说枚举 Alice 的初始选点。假设这个初始选点将当前序列分成 $L$ 与 $R$ 两部分，那么答案就是 $g_{n-1,L+R}$，这里的加操作是将 $L$ 与 $R$ 拼接后的序列。对所有的 $g_{n-1,L+R}$ 取 $\max$，就是 $f_{n,S}$。
对于 $g$ 也是类似的，进行维护。最终是对所有 $f_{n-1,L+R}$ 取 $\min$。
答案即为 $\sum f_{n,S}$，复杂度为 $\mathcal O(n^22^n)$。
E2. Prime Gaming (Hard Version)
较上题，该题值域变为 $[1,m]\bigcap \mathbb{N}$，其中 $m\le 10^6$。
对于一个值 $t\in[1,m]$，尝试更改序列 $1/2$ 的含义：$1$ 表示该位 $\le t$，$2$ 表示该位 $>t$。$S$ 不再代表原序列，而是代表一类的序列。$f_{n,S}$ 与 $g_{n,S}$ 的含义随之改变。设 $\operatorname{popcount}(S)$ 为 $S$ 中 $1$ 的数量。
那么对于满足 $f_{n,S}=1$ 的一类序列 $S$，就有 $\operatorname{cnt}(S,t)=t^{\operatorname{popcount}(S)}\cdot(m-t)^{n-\operatorname{popcount}(S)}$ 种对应生成的序列。根据这个性质，$f_{n,S}=1$ 就代表有 $\operatorname{cnt}(S,t)$ 的最终博弈结果 $\le t$ 的答案。那么结果 $=t$ 的是 $\le t$ 与 $\le t-1$ 差分的结果，也就是 $\operatorname{cnt}(S,t)-\operatorname{cnt}(S,t-1)$ 种。设所有 $\operatorname{popcount}(S)=a$ 的一类序列个数为 $c(a)$，$\operatorname{s}(t)=\sum\limits_{S\subseteq U}\operatorname{cnt}(S,t)=\sum\limits_{x=0}^nc(x)\cdot t^x\cdot(m-t)^{n-x}$，$U$ 是全体序列集合。于是答案即为 $\sum\limits_{t=1}^m t\cdot(\operatorname{s}(t)-\operatorname{s}(t-1))=\operatorname{s}(m)-\sum\limits_{t=1}^{m-1}\operatorname{s}(t)$。
时间复杂度为 $\mathcal O(n^22^n+mn)$。