CSP 模拟 51

A 排列最小生成树 (pmst)

首先想到 \(n^2\) 建边的做法，然后最小生成树的所有边权都小于 \(n\)，直接从头到尾连都能轻松满足这个。所以很多边是无用的，只要找边权小于 \(n\) 的边即可。所以对于位置差和权值差在 \(\sqrt n\) 以下的都找一遍即可，然后桶排跑 MST 即可。赛时根号都写脸上了，没做出来不应该。

B 卡牌游戏 (cardgame)

考虑一下每个 \(A\) 会去比较的位置，发现比的都是一个余数固定的集合，找到所有余数的集合，然后二分找一下就行了。

C 比特跳跃 (jump)

• 对于 \(S=1\)，发现从 \(1\) 可以用 \(0\) 的代价跳到所有偶数点，通过这些偶数点又可以用 \(0\) 的代价跳到所有二进制无交的奇数点，然后发现对于 \(n\) 点，它在 \(n=2^k-1\) 的情况下跳不到，然后用 \(K\) 和 \(n\) 相连的所有边比一下即可。
• 对于 \(S=2\)，直接考虑优化建图，先想暴力，连出所有异或边即可，但是很多边其实都被其他边间接表示了出来，考虑 \(a\to b\) 只有一个 \(2^k\) 的贡献，\(b\to c\) 只有一个 \(2^s\) 的贡献，那么对于 \(a\to s\) 的贡献 \(2^k+2^s\)，它就可以被上面两条边组合出来，所以直接每个点考虑向只改变一个二进制位的连边即可。
• 对于 \(S=3\)，首先跳跃 \(a\) 到 \(b\) 至少会做出 \(\min(a,b)\) 的贡献，这是在有子集关系的情况下。所以从 \(1\) 到奇数点最优，跳到偶数点只会多出来 \(1\) 的贡献，所以先建出来 \(1\) 的所有边，跑一遍 dij，然后考虑节点的松弛，一个节点只有可能被它的子集节点跳跃松弛，不然还不如从 \(1\) 条，这时候枚举子集还是 \(3^{\log n}\)，但是只需要找到子集中最小的 dis 即可，所以从小到大枚举，每次在子集上扩展一位，时刻取个 min，把能松弛的节点再放到队列里，然后再跑一遍 dij 即可。

观察性质题，赛时连异或都没做出来还是太菜了。

D 区间 (interval)

说是历史版本和板子题，太麻烦了以后再说，所以说下部分分。

• 对于 \(n\le 3000\)，可以单调栈出最大值的控制范围，然后找有多少个 \(B\) 符合条件即可，上数据结构即可，\(\mathcal{O}(n^2\log n)\)。不是，我都 \(n^2\) 了还上牛魔的数据结构，直接对于每个点暴力找一次存起来不就行了，这个是真的 \(n^2\)。
• 对于 \(A_i\le 3,B_i\le 3\)，手玩发现对于一个右端点，最多有一个左端点符合条件，所以暴力找出来后拍到平面上离线二维数点即可。

赛时咋 \(n^2\) 都不会，你都打暴力了还上牛魔的数据结构。