CF388D
对于一个不同的线性基，对应着一种不同的 Perfect Set 。只要线性基能异或出来的数都得在 Perfect Set 里面。
于是考虑一个数位 $dp$ ，设 $dp[i][j][0/1]$ 表示当前考虑到了第 $i$ 位，已经有 $j$ 个位的线性基填过数，到现在最高位是否贴着上界的方案数量。
我们考虑第 $i-1$ 位。
$k = 0$
这一位可以随便填或者不填。如果这一位填了 $1$ ，那么之前位的这一位都不能有值。转移系数是 $1$ 。如果这一位不填 $1$ ，之前可以任意填，转移系数 $2^j$。
$k = 1$
如果填入这一位，则仍然是卡着上界的。转移系数是 $1$ 。
如果不填，则如果之前这一位上有偶数个 $1$ ，那么就不再卡着上界了。转移系数是 $\binom n 0 + \binom n 2 + \dots = 2^{j-1}$ ，因为对于所有选择偶数个数的方案，我们只要把第一个位置给反转一下，就一定可以得到一个选择奇数个数的方案，并且明显方案一定两两对应。
如果之前这一位上有奇数个 $1$ ，那么仍然卡着上界，系数是 $2^{j-1}$ 。
Gym 100543L / P4766
为什么我就是想不到呢
可以把人看作一条 $(a_i,d_i) \to (b_i,d_i)$ 的线段。
考虑区间 $dp$ ，设 $dp[l][r]$ 表示被 $[l,r]$ 完全包含的区间全部被干掉最小的代价。
我们每次从区间内部选择一个最高的区间，然后把它砍掉同时分成两个区间即可。
复杂度 $O(n^3)$ 。
CF584E
首先，我们可以变成一个给排列排序的问题。设 $p_i$ 表示当前 $i$ 位置最终需要到达的位置。
答案是有下界的。总共需要移动的代价至少是 $\sum |i - p_i|$ ，即使每一步都最优地操作，也只能让当前需要的代价减少 $2|i-j|$ ，也就是两个数都像自己的目标点移动了 $|i-j|$ ，所以答案的下界是 $\frac{\sum |i-p_i|}{2}$。
一定取得到这个下界吗？考虑从小到大还原数。设我们当前还原到了 $t$ ，处于的位置是 $pos_t$ 。那么 $1\sim t$ 这些位置的值一定已经被还原好了。我们可以从 $pos_t$ 往前找一个数 $q$ ，使得 $p_q > pos_t$ ，然后交换这两个数，不难发现这样就可以让代价减少 $2|i-j|$ 。一定可以找到这样的数吗？如果找不到，说明 $t \sim pos_t-1$ 的数只需要内部交换就可以全部归位。但是 $t$ 这个东西需要到达 $t$ ，也就是说从 $t$ 到 $pos_t-1$ 的可以用的位置总是比数的个数少 $1$ 的，所以必然不能全部归位，所以一定可以找到这个数 $q$ 。一直这么找下去，必然可以把 $t$ 归位，同时每步操作都是尽量优秀的。
APOJ ACPC13
就边权从小到大加入来保证路径权值递增，然后设个 $dp[u][i]$ 表示当前到了 $u$ ，经过了 $i$ 条边的最小代价，对每个起点跑一次 $dp$ 即可。因为经过的边数肯定是不超过 $n$ 的，所以复杂度 $O(n^2m)$ 大概。
染色
神仙题。
考虑差分一下，变成同色点间距离 $\ge k$ 。
然后按照 $\text{BFS}$ 顺序加入点。这样加点的时候每轮都加入的是一个叶子。然后结论就是，加入一个点对方案的贡献就是 $m-t$ 其中 $t$ 是当前与这个点距离不到 $k$ 的点的个数。
为啥这样是对的呢？啥时候这样会炸，就是有两个点，它们到加入的叶子距离都不到 $k$ ，但是它们之间的距离超过了 $k$ 。事实上，这种情况是不存在的。我们考虑这个点的一个祖先，如果有两个点到这个点的路径在这个祖先交汇。
也就是 $dis_1 + dis_2 \ge k , dis_1 + dis_3 < k, dis_2 + dis_3 < k$ 存在了。
也就是说 $dis_1 > dis_3 , dis_2 > dis_3$ 存在。但是我们是按照 $\text{BFS}$ 顺序加入的，加入是按照到根的 $dis$ 顺序来的，所以不存在。
唯一一条有可能大于等于 $k$ 的路径就是这个祖先向根方向走的路径了。但是这种路径只有一条，所以也不存在这种情况。
于是拿点分树维护一下即可。
CF1188C
去年做的题现在忘了。。。
考虑枚举一下最终的最小差值，然后求相邻两项的差值都必须大于等于这个差值的方案数量。
设 $dp[i][k]$ 表示当前正在选择第 $i$ 个数，已经有 $k$ 个数被选进序列。转移就是一个双指针 + 前缀和。
不难发现，最小差值不超过 $\frac v k$ ，所以复杂度其实是 $O(nv)$ 的。。。
P5405 氪金手游
考虑如果所有边都是从根向下的，那么对于一个点，它必须在子树内所有点之前被取。这个点被取的概率是 $a$ ，子树内的点被取的概率是 $b$ 的话，那么概率就是
在这里，我们知道一个点被取的概率是 $\frac{a}{S}$ 子树的某个点被取的概率是 $\frac{s_u - a_u}{S}$ ，那么总的来说，这个点比子树内的所有点都先取的概率就是 $\frac{a}{s_u}$ 。于是我们可以树形背包解决全是根向下的边的情况，记 $dp[u][x]$ 表示 $u$ 子树之中所有数的权值和位 $x$ 的概率即可。边界是最开始给 $dp[u][1,2,3]$ 分别放初值 $p_{u,1,2,3} \times 1,2,3$ 这些东西，最后给 $dp[u][k]$ 除以 $k$ 即可。
考虑反向边的情况，我们可以钦定一些反向边不合法，剩下的反向边任意，容斥系数显然是 $(-1)^k$ ，算出来的就是恰好 $0$ 个反向边不合法的方案数量。
某个题
数点 $x \le a,y \le b,x+y\le c$。
考虑如果 $a+b \le c$ ，那么我们只数前两个条件即可。
否则，如果 $a+b>c$ ，考虑容斥前两个条件，钦定一些不合法，那么算的就是：
这四个情况中前三个都是二维数点。最后一个，由于 $x+y > a+b > c$ ，必然不存在。
于是复杂度 $O(n\log n)$ 。