不管AB卷了就按洛谷的排列顺序来写吧。
1.卡牌游戏
问题可以看成是选最多 $m$ 个 $b_i$ 所能达到的最佳答案。
直接 $a,b$ 混在一起排序（当然要记录下这个数原来是 $a$ 还是 $b$ ）。然后要做的就是尽量砍掉两头的数。
直接双指针记录前面删 $i$ 个数是后面最多删多少个数，扫一遍求个最小值就好了。
1 |
|
2.矩阵游戏
首先容易构造出一个值域为 $\Z$ 的 $a’$ 数组（直接钦定第一排第一列为 $0$ 即可），然后考虑调整。
考虑对整行整列进行操作，发现给矩阵奇偶黑白染色后，对整排或整列的黑点 $+1$ ，白点 $-1$ 结果仍然合法。
然后设第 $i$ 行加了 $r_i$ ，第 $j$ 列加了 $c_j$ ，那么真实的 $a$ 满足：
$a_{i,j}=a’_{i,j}+(r_i-c_j)(i+j\bmod 2==1)$
$a_{i,j}=a’_{i,j}-(r_i-c_j)(i+j\bmod 2==0)$
然后就可以根据 $a_{i,j}\in[0,10^6]$ 列出差分约束的不等式了。
1 |
|
3.图函数
遇事不决先找性质，并且相信奇迹，$O(n^3)$ 过 $1000$ ！
找一找性质，可以发现：一个点 $x$ 合法当且仅当它仅经过 $y\in(x,n)$ 的点能够同时存在 $i\rightarrow x,x\rightarrow i$ 的路径。
证：若 $u\in[0,x)$ 合法，$u$ 已经被删除；若不合法，不存在 $i\rightarrow u\rightarrow i$ ，则不存在 $i\rightarrow u\rightarrow v\rightarrow i$ 或 $i\rightarrow v\rightarrow u\rightarrow i$ 。
然后对于依次加边统计答案转化为第 $i$ 条边边权为 $i$ ，按一条路径经过边的最小值进行差分。
找最小值可以用 $\rm Floyd$ ，$O(n^3)$ 暴力也能过。（关于能不能过可以现场试一下，$\rm Floyd$ 运行次数比较稳定）。
1 |
|
4.数对
$B$ 卷的签到题我当然是不会的啦。
$a\leq5\times 10^5$ ，由于顺序无关，直接 $O(alna)$ 暴力统计答案就行。
1 |
|
5.宝石
写了个贴着数据范围的复杂度 $O(n+c\sqrt{n}+q\sqrt{n}\ logn)$ 的垃圾做法。
首先考虑将 $P$ 序列下标映射到宝石上（因为 $P$ 不相同），然后就变成在这个路径上搞出最多连续的 $123…x$ 。
然后路径直接树剖搞出来映射到 $\rm dfs$ 序上，然后问题转化成当前选到了 $p$ ，经过一个区间后选到了谁。
分块常数小，我们要相信奇迹，直接上分块 $O(\sqrt{n}\ logn)$ 查询就行了（个人喜欢固定块长，复杂度较玄学）。
然后直接处理每个块内传入 $p$ ，传出谁，暴力跳就行了，当然正反都要处理一下下。
代码很无脑，调的时候出了一个小错误，基本算是一遍过：
1 |
|
6.滚榜
首先尝试相信奇迹打一个 $O(n!\times n)$ 的暴力，然后仍然不会 。可以发现 $b$ 序列有贪心分法。
不妨令 $f_i=a_i+b_i$ ，考虑枚举排列 $P$，先报 $P_1$ ，然后必须使 $f_{P_1}>\max {a}$ ，于是 $b_1$ 的值就出来了。
然后接下来就继续贴着合法条件给出 $b$ ，最后剩余的一股脑塞给 $P_n$ 就行。
考虑把上面式子化一化，发现 $Sum=\sum (a_{P_{i-1}}-a_{P_i}+(P_i>P_{i-1}))\times(n-i+1)$ ，发现 $a_i$ 的贡献可以拆开来算。
然后 $dp_{S,i,j}$ 表示选了 $S$ 集合，最后为 $i$ ，和为 $j$ 的方案数 $\rm dp$ 就行。复杂度 $O(2^nn^2m)$ 。
1 |
|
7.支配
不会支配树，不做了。 于是抄了抄题解 （逃
以 $1$ 为一个有向图的 “根” ，然后暴力枚举每个点找到这个点的支配集（就是直接 $dfs$ 看哪些点不再可达）。
然后由一个点向距离它最近的支配点连边建树（可以用 $\rm topo$）。
如果一个点 $x$ 的 $fa_x$ 不再支配 $x$ ，那么 $x$ 整棵子树会改变并计入答案。
考虑当" $1$ 不经过 $fa_x$ 可以到达 $u$ “且” $v$ 不经过 $fa_x$ 可以到达 $x$ " ，$fa_x$ 不再支配 $x$ 。
第一个命题可以转化为 $fa_x$ 不支配 $v$ ，第二个命题可以建反图预处理。然后特判 $fa_x =v$ 和 $fa_x=1$ 的情况不成立。
最后处理出满足条件的点从上到下遍历支配树统计答案即可。复杂度 $O((n+q)n)$ ，卡常。
1 | #include<cstdio> |
8.取模
玄学题，（其实我不会证复杂度也不想证了QAQ （~懒
考虑 $O(n^2logn)$ 做法，可以枚举模数，对剩下的数按取模后从大到小排序。不妨设为 $b$ 。
最大与次大值加起来有可能是答案，然后继续用双指针枚举 $a_l+a_r<a_i$ 的 $l,r$ 取 $\max$ 。
然后考虑玄学优化：
-
两个以上重复的数没有任何用处，去个重。
-
模数从大到小枚举，如果答案已经大于当前模数就可以停止枚举了。
正确性显然，复杂度玄学，据称是 $O(nlognlogV)$ 的，可以尝试手玩一下。
1 |
|