20联赛集训day2 题解
A发现限制形如选了一条边之后，不能选和它端点相同的边。我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式...
A发现限制形如选了一条边之后，不能选和它端点相同的边。我们建一张新图，新图中的点代表原图中的边，如果两个边不能同时选就连边。首先可以证明问题一定有解：因为这个问题等价于对于每个弱连通分量找出一个环，而只要出度入度都为 $1$ 就一定有环，所以这种情况下更有环。我们发现原图的一种答案对应了新图的一种二分图染色方式，所以我们可以得到新图的每个连通块都是一个二分图，每个连通块有 $2$ 种染色方式...
A类似后缀数组算本质不同串的思路，考虑 $S$ 的第 $i$ 个前缀和第 $i+1$ 个前缀有多少个都会被计算，发现被算重的后缀等价于 $T$ 中 $S[i+1]$ 的出现次数。举个例子：abc abc 第 1 个前缀和第二个前缀都会算到 abc,原因是第一个前缀是 "a"+"bc"，第二个是 "ab"+"c"...
qbxt 10 月 Day6 讲课BZOJ1112肯定都变成中位数。维护两个 multiset 分别维护前一半大和后一半大。记录一下和。POJ 2777注意到颜色数量才 $30$，所以可以直接维护区间或。HDU 2795对于每一行都记录一下还剩多少，线段树二分。POJ 3667维护前缀 $0$ 后缀 $0$ ，区间最长 $0$ 的长度，修改的时候线段树二分到区间即可。CF 365D出现偶数次...
这场ABC都是Div2 ABC种偏难的。。但是后面难度就上不去了（可能是我只会做一点点套路题的原因？）A这里的反转是 reverse，不是取反。。自闭了。。设这两个数是 $a,b$，其中 $a > b$，由于字典序最小，所以我们从低位向高位看，要求尽量是 $0$。我们找到 $b$ 的 $\text{lowbit}$ $p$，发现比 $p$ 低的位都是无法改变的（由 $a$ 决定），我...
CF 875F对于一个公主，我们建边连接两个王子，边权为这个公主的权值。这样一个子图合法当且仅当每个边都能找到一个点配对，并且每个点只被用至多一次。发现合法的形态只有基环树森林（树林是基环树森林的一种特别情况）。这里有个结论是基环树森林的求法也可以对边排序后直接贪心。也就是维护每个连通块是否已经是基环树，如果当前边在一个连通块并且这个块是树就可以将其变成基环树；合并不同集合的边的时候不能合并...