CF 板刷记录
CF1748E (*2300) 经过观察可以发现符合要求的 b 序列的充要条件是和 a 的笛卡尔树相同。 这个笛卡尔树比较特别，单看权值时是一个大根堆不是小根堆，把权值取反即可，差不多的。 想到笛卡尔树就好办了，建出笛卡尔树然后在上面 dp 即可。 Code CF 1737D (*2200) 先说结论：最短路一定是将某一条边变为连接 1 和 n ，然后直接走这条边。容易反证得出。 那么我们现在的问题就是求出对于每一条边，同时经过两个端点和这条边的最短路径，求出来之后乘以边权再取最小值即可。 做法很多，但是既然 n 这么小就还是 Floyed 好了。 总时间复杂度 $O(n^3+nm)$。 Code CF 1726E (*2400) 很厉害的数数题。 首先有一个性质：将 $i$ 与 $p_..
NOIP 2022 退役记
NOIP 2022 退役记 Day -16 打模拟赛，补题，摆烂，whk 的同学们在期中考。 Day -15 上午模拟赛，三场大 DS ，笑死了，根本调不完。 下午补了一下午题目，whk 的同学们还在期中考。 晚上打了两道题，然后开摆。 Day -14 上午 VP 了一场之前的模拟赛，很水啊。 接下来下午就是补一些之前的题，CF 的好多题质量确实非常高。 晚上也补题目啊，whk 的同学们期中考考完了，我高中最后一场能咕咕的考试结束了。 今天中午颓了 generals 和 gartic 。 Day -13 上午打模拟赛，有几道题的套路见过的，感觉这个 D 很有意思。 下午打洛谷月赛啊，交互很可做，自己搞了个做法玩玩，但是调试没删喜提 70 。 晚上放假了晚上。 Day -12 补题，补..
CF1641D Two Arrays 题解
真神仙题。 做法一 使用 bitset 优化暴力，对权值开 bitset，匹配时直接或起来即可。 注意到空间很大，可以通过根号分治优化，时间复杂度大概在 $O(\sqrt{\frac{n^3m}{\omega}})$。 做法二 这个容斥是真的 NB。 判断两个集合是否重合的一个方法：枚举两个集合的子集，长度为奇数的子集相同就加一，为偶数的子集相同就减一，最终若有相等元素，则最终值一定为 $1$。 证明：令 $s$ 为交集大小，则我们所求值为 $\sum\limits_{i=1}^{s}\dbinom{i}{s}(-1)^{i+1}$，由二项式定理可以推导得到。 这个方法看似时间复杂度很劣，但是在这道题中有奇用，我们可以用他来判断若干集合中于一个集合有相同元素的集合个数。 具体的，..