那些你不要的
注意到操作不改变位置下标的奇偶性，即最终答案必然在初始下标为奇数的数中
同时，每次操作恰可删除其中任意一个，进而答案即这些数的中位数（若偶数个则取较大项）
用nth_element实现即可，时间复杂度为\(O(n)\)
比特迷宫
从大到小枚举\(k\in [0,n]\)，并调整（二进制下）恰包含\(k\)个\(1\)的位置：
钦定\(s=a+b\)恰包含\(k+1\)个\(1\)，取\(a\)为将\(s\)中若干位变为\(0\)，即可翻转对应的恰包含\(k\)个\(1\)的位置
换言之，仅需构造一个\(s\)的集合，使得其可以"覆盖"所有恰包含\(k\)个\(1\)的位置
这可以贪心实现，即每次选择能能额外覆盖最多位置中最小的\(s\)，最终\(s\)的总数为\(157884\)
另外，这还会翻转\(s\)自身，这仅需在之前的调整中将其设为\(1\)即可
时间复杂度为\(O(n^{2}2^{n}+3^{n})\)
璀璨宝石
当第\(i\)次购买发展卡时，在\([1,i]\)中恰剩一张卡未选，并需在其与\(i+1\)间决策
考虑暴力DP，定义\(f_{i,j,a,b,c,d,e}\)表示所剩的卡为\(j\)且还需要\(a,b,c,d,e\)个宝石的答案
-
若\(a,b,c,d,e\)中仅存在一项非\(0\)，此类状态可直接表示
-
否则，即其中任意非\(0\)两项配对后均严格劣，进而存在一项使得仅包含其与其余项的配对
此时，状态仅取决于该项编号和其余项的数量和
状态数为\(O(Cn^{2}m)\)（其中\(C=5\)），并考虑转移：
-
对于第一类状态，枚举新的宝石编号，转移即形如
\[\forall i\in [l,r],2\mid (i-l),f_{i}=\min(f_{i},s-\lfloor\frac{i}{2}\rfloor) \]可以用单调队列优化
但实际上直接暴力就能过了 -
对于第二类状态，配对方式唯一，可以直接转移
时间复杂度为\(O(C^{2}n^{2}m)\)
火星式选拔
对于前\(k-1\)大的\(b_{i}\)，其总能加入且不会作为最小的\(b_{i}\)删除，必然在最终答案中
在最后一个前\(k\)大的\(b_{i}\)加入前，其余\(k-1\)个均在答案中，进而加入后答案恰为这\(k\)个
对于第\(k\)大的\(b_{i}\)，在此后找到第一个\(\ge b_{i}\)的\(a_{j}\)，即转换为\(k=1\)的子问题，倍增即可
时间复杂度为\(O(n\log n)\)
反重：求熵
钦定\(x_{0}=0\)，并将限制转换为\(\forall 0\le i<j\le n,L_{i,j}\le x_{j}-x_{i}\le R_{i,j}\)
当确定\(x_{0},...,x_{n-1}\)后，\(x_{n}\)的范围即\([\max_{0\le i<n}x_{i}+L_{i,n},\min_{0\le j<n}x_{j}+R_{j,n}]\)
枚举取到\(\max,\min\)的\(i,j\)（多个取最小），即要求\(\forall 0\le k<n,\begin{cases}x_{k}+L_{k,n}+[k<i]\le x_{i}+L_{i,n}\le x_{k}+R_{k,n}\\x_{k}+L_{k,n}\le x_{j}+R_{j,n}\le x_{k}+R_{k,n}-[k<j]\end{cases}\)
此时即为\(x_{0},x_{1},...,x_{n-1}\)的子问题，且每组方案对答案的贡献为\(\sum_{x_{n}\in [x_{i}+L_{i,n},x_{j}+R_{j,n}]}1\)
重复此过程，维护答案多项式\(f(x_{0},x_{1},...,x_{n})\)，每次即求\(\sum_{x_{n}\in [l,r]}f(x_{0},x_{1},...,x_{n})\)
预处理出\(g_{k}(x)=\sum_{i=1}^{x}i^{k}\)，并将\(x_{n}^{k}\)用\(g_{k}(r)-g_{k}(l-1)\)代替即可，时间复杂度为\(O(C(n!)^{2})\)
同时，注意到\(i,j\)间独立，时间复杂度为\(O(Cn!2^{n})\)（其中\(C\)为多项式项数）
鸽子收费站
咕咕咕