UOJ Round #23
A. 民意调查
20
$n \le 20$
$V \le 800$
暴力枚举所有子集。
时间复杂度 $\mathcal O(2^n n)$。
60
$n \le 30$
$V \le 100$
把整个序列从小到大排序，将子集看为一个排序后序列的子序列 $a_{b_1}, a_{b_2} \ldots, a_{b_{2 k + 1}}$，中位数看做 $a_{b_{k + 1}}$ 这一项。
枚举中位数在序列中的位置，再枚举 $k$，对于平均数和中位数关系的限制可以对两边分别进行背包求出答案。
时间复杂度 $\mathcal O(n^4 V)$，空间复杂度 $\mathcal O(n^2 V)$。
90
$n \le 50$
$V \le 800$
注意到每次的背包一定是一个前缀和一个后缀，所以预处理出每个前缀和每个后缀的背包并对一边做前缀和，这样每次枚举完中位数和 $k$ 之后只需枚举某一边选出数字之和即可。
时间复杂度 $\mathcal O(n^3 V)$，空间复杂度 $\mathcal O(n^3 V)$。
100
$n \le 70$
$V \le 800$
可以从前到后枚举中位数，这时对于前缀的背包就可以自然地每次加入一个数，而不用保留之前那些前缀的背包。
对于后缀的背包，可以先处理出所有数的背包，每次从前到后扫中位数时，将一个数从背包中移出，就可以得到当前想要求出的后缀的背包了。
时间复杂度 $\mathcal O(n^3 V)$，空间复杂度 $\matchal O(n^2 V)$。
B. 地铁规划
10
$n \le 1000$
对于每个左端点，暴力扫右端点直至 check 为零，然后 undo 回去即可。
操作次数 $\frac{n^2}{2}$。
40
$n \le 10^4$
可撤销 DSU 能撤销最近一次的操作，而我们需要撤销最远一次的操作，不难想到采用一种 “双栈结构” 来维护它。
具体地，加入 DSU 的边可以用一个栈维护，其中已经翻转过的边用 0 表示，未翻转过的边用 1 表示，只要时刻保证栈顶为 0 边即可直接进行 undo 操作。
对于当前左端点的查询，它会使得栈顶加入若干个 1 边，考虑暴力弹栈顶直至弹出来的 0 边和 1 边数量相等，然后把 1 边按原顺序加回栈，再把 0 边按原顺序加回栈，这样就满足栈顶为 0 边，可以直接 undo 了，特殊情况是把栈弹空了仍然不满足 0 边和 1 边数量相等，此时如果栈中压根没有 0 边，我们就把所有 1 边倒着加回栈中，这样所有 1 边变成了 0 边，否则我们仍按照上述方式加回栈中即可。