并查集 提供一种只需使用并查集的好写的方法。 统一蓝和统一红只有一个取反的差别，以下默认全部统一为蓝。 一条蓝边，它的两个端点要么都选，要么都不选。 一条红边，它的两个端点只选择其中之一。 于是对每个点建立两个事件“它选”和“它不选”，可以用诸如 $i,i+n$ 的一类方法记录，以下以 $i$ 表示选，$...

二分 首先有一个比较明显的性质，直径最多经过两条边。 设全局最小值为 $m$。考虑从任意一点 $u$ 出发，经过全局最小值所在的点，然后再到任意点，花费是 $2\times m$ 的。而任意边权 $\geq m$，走两条后的权值必定 $\geq 2\times m$。所以最多就是花费 $2\tim...

找规律 貌似跟官方题解有点出入，不过好像本质是一样的。 看到 “hacks are disabled” 回忆起这应该是个诈骗啥的。 看操作，先看非特殊行，一个数 $+1$，相邻数 $-1$，并且一次有两个这样的东西。 这个东西是不是很像差分后搞区间长度为 $1$ 区间加的操作。 所以做一下前缀和再看看...

纪念一下赛时想出正解细节调炸心态。 找性质+二维偏序 首先拿到题没啥思路，感觉可能是高妙的数据结构但是不会。 硬着头皮写下式子： 对于 $j\in [x_i-p_i,x_i]$ 水位增加 $p_i-x_i+j$。 对于 $j\in (x_i,x_i+p_i]$ 水位增加 $p_i-j+x_i$...

贪心构造 首先题目里面保证了必定有一个合法的状态，我们不妨先构造一个出来。 经过某个经典转换，将左右括号分别标为 $+1,-1$，那么一个串合法当且仅当这个串的和为 $0$ 且任意前缀和 $\geq 0$ 。 所以贪心地选择先填写左括号，使得前缀和尽量大即可构造出一个合法串。 然后考虑判断是否能通过改变...

网络最大流 大概是最劣解？但能过嘿嘿。 考虑到对 $b$ 中某个值进行操作的时候能取到的值不多大概是 $O(\log^2)$ 种，所以想办法处理出这些数然后跟 $a$ 里面的数匹配，匹配的话当然是建图跑最大流就好啦。 很遗憾，tle on test 30 ，考虑剪枝： 集合 $a$ 和 $b$...

贪心 因为 $a_i\geq 0$，所以明显多选不亏。 可以从高到低位考虑，改动原来的数必须往小了改，所以改动的最高位必须是 $1$ 改成 $0$。如果选择将某一个 $1$ 变为 $0$，那么后面的数无论怎么改都是小于原数的，所以全部填上 $1$ 就可以了。 所以具体来说做一个从低位到高位的前缀...

01-Trie 上状压 dp 首先可以发现，如果两个数的二进制前面 $B$ 位相等，那么这 $B$ 位数无论 $x$ 为多少都无法产生贡献。 然后还可以发现，第一个不相等的位可以确定两个数的大小。 考虑把 $a$ 序列插到 01-Trie 里面，这样从顶点到某个点的路径代表这棵子树中的值前面的...

二分 + 2-SAT + cdq优化建图 首先看到 $k$ 的限制， $k$ 越大越不可能合法，可以二分。 然后考虑一个划分中一个数非 $a$ 即 $b$ ，可以用 2-SAT 判定。 然后发现连边稍微有点多，但是连边的时候可以一下子连某个区间，考虑可以数据结构优化一下。 再细看一下，前两个条...

不管AB卷了就按洛谷的排列顺序来写吧。 1.卡牌游戏 问题可以看成是选最多 $m$ 个 $b_i$ 所能达到的最佳答案。 直接 $a,b$ 混在一起排序（当然要记录下这个数原来是 $a$ 还是 $b$ ）。然后要做的就是尽量砍掉两头的数。 直接双指针记录前面删 $i$ 个数是后面最多删多少个数，扫一遍求个最...