CodeForces Chapter1 是我 CF 上截取的一段 2600-2800 的题单，由于题目较多，故合作一篇所以题解会比较简洁，为了达到简洁这一目的，会舍去部分比较平凡的东西以及代码，如果有需要就联系我吧。
事实上前段时间咕了挺久的博客，咱也不好意思说自己是因为最近都在做权限题其实也没做多少，都在摸鱼以及更新多项式板子。
所以这篇就当作平常摸鱼的作品吧……说实话最近的计划老师安排（都不会）的题量还是蛮大的，能写则写吧。
考虑到上 CF 的速度时快时慢，所以这里直接贴洛谷上的网址了。
CF1398G Running Competition
题意
做法
对于每个询问 $l_i$，$O(\sqrt{n})$ 地枚举它的约数，转为判定后发现本质上就是考虑是否存在两个点其距离为 $x$。
由于点的值域在 $10^6$ 以内，所以考虑预处理每个距离是否可行，令数组 $A$ 表示某个位置上是否有点，发现其实就是它与本身减法卷积，可以通过翻转其中一个然后转为加法卷积。
时间复杂度 $O(n\log n)$，似乎有人用 bitset $O(n^2/w)$ 跑过去了。
CF1394C Boboniu and String
题意
定义两个 $01$ 串是相似的，当且仅当可以通过重排使得两者相等。
定义一次操作可以是删除字符串中的某个字符，删除一个 $01/10$，在末尾添加 $0/1/01/10$。
两个 $01$ 串的距离为通过最少的操作次数，使得两者相似。
给定 $n$ 个 $01$ 串 $s_1,s_2,\cdots,s_n$，求一个 $01$ 串 $t$ 使得 $\max_{1\le i\le n}\operatorname{dis}(s_i,t)$ 最小。
$n\le 3\times 10^5,\sum|s_i|\le 5\times 10^5$。
做法
由于两个串相似是通过重排来实现的，所以可以只考虑一个串中 $0$ 和 $1$ 的个数。
以下内容改编自 xuezhe AKIOI 的博客。
事实上，对于此题，我一开始是懵的。
看着题解的解读，疯狂想：怎么做到删除 $01/10$ 子串而破坏上面的思路的？（这边考虑的是子串，而与重排有些冲突）
直到后来，我突然想到了这么一样东西：交界。
一切都解释通了。
请注意这一点：交界。这将是接下来解释的一个基础。
首先删除单个字符以及末尾插入字符和字符串显然不会影响重排后的正确性。那么删除子串呢？我们发现如果当前存在两种字符，那么必然会有交界，交界表示左右两边的字符异或为 $1$。
于是可以仅考虑两个字符的数量，记作 $(x_i,y_i)$。那么我们每次操作可以使得：
- $(x,y)\gets(x\pm1,y)$
- $(x,y)\gets(x,y\pm 1)$
- $(x,y)\gets (x\pm1,y\pm 1)$，这里要求两者同为加或同为减。
把这个问题放到平面直角坐标系上，于是每个串可以被看做一个点，我们要找到一个整点，使得它到其它点的距离（这里的距离是只能上下左右，左下右上的走一步得到的距离）的最大值最小，那么我们二分一个距离 $d$，则一个点能走 $d$ 步到达的点可以这样被刻画：
- 左下及右上没有斜着走的限制，故是一个四边与坐标轴平行的正方形。
- 左上及右下不能直接斜着走，是一个四边与坐标轴夹角为 $45^°$ 的正方形。
形式化地说，它是一个半平面交：
以及 $x,y\ge 0$。
我们发现有很多直线是平行的，可以直接忽略绝大多数直线（对于两条平行且取的半平面同侧的直线，选择离取的半平面侧更近的直线），最后只会剩下六条直线（它们组成一个平行四边形），这六条直线上的任意一个点，要么横纵坐标同时是整数，要么同时不是整数，这时手动半平面交后取最右上的点即可。
二分的上界取 $5\times 10^5$，则时间复杂度为 $O(n\log \sum |S|)$。
CF1394D Boboniu and Jianghu
题意
$n$ 点无根树，点有参数 $a_i,b_i$，要求将树上的所有边恰好分到若干条链上（点可以重复），要求每条链上的点的 $b$ 单调不降或单调不增，一条链的权值是点上的 $a$ 的和，求一种划分方式使得所有链的权值和最小。
$n\le 2\times 10^5$。
做法
为了方便，我们给每条链定向：从小点权到大点权。于是，如果一条边端点 $b$ 值不同，那么它的方向是确定的。
一个显然的是，我们希望一条链如果能继续连下来，那么一定要连下去。
如果体现在一个点上，那么就是尽量让连入这个点的边和连出这个点的边匹配。
对于所有边端点 $b$ 值都不相同的情况，这棵树上的所有边的方向是确定的，我们所要做的无非就是给每个点的入边和出边匹配，它的贡献是 $a_i\times \max(\operatorname{In}_i,\operatorname{Out}_i)$。
换句话说，我们现在需要给端点 $b$ 相同的边定向，考虑 DP。
设 $F(u,0/1)$ 表示点 $u$ 与父亲的边是连入（$0$）还是连出（$1$）时，其子树内的最小贡献和。不妨假设此时它已经确定连出了 $O_i$ 条边，连入了 $I_i$ 条边，则我们希望通过确定剩下的边让 $|I_i-O_i|$ 尽量小。不妨设 $I_i\ge O_i$，我们不妨假设剩下的边都是连入的边，然后在此基础上反转边的方向，权值差为 $F(v,1)-F(v,0)$，以该差为关键字排序，枚举翻转几个，然后贪心选最小的即可。
CF1391E Pairs of Pairs
题意
给定一张 $n$ 点 $m$ 边简单无向连通图，要求以下两种选择任意一种作答：
- 求一条长度至少为 $\lceil n/2\rceil$ 的简单路径。
- 选出至少 $\lceil n/2\rceil$ 个点使得它们可以两两配对并且这些点对中任何两个点对组成的 4 个点的导出子图最多只有两条边。
$n\le 5\times 10^5$，$m\le 10^6$。
做法
像这种题似乎都是搜索树硬上……
建出搜索树，如果树高大于等于 $\lceil n/2\rceil$，那么直接取树根到最深的叶子这条路径。
否则的话现在树高小于 $\lceil n/2\rceil$，这时我们希望完成第二个任务。
考虑任意两对点，我们希望它们的导出子图边数少，那么我们尽可能地让点对间是没有边的。
考察搜索树上的性质：不可能存在横叉边。这意味着同层节点之间是不会有边的，于是我们尽可能地选同层的点凑成一对。这样一来，任意两个点对的导出子图，至多存在两条边（返祖边或连向父亲的边）。
由于每层至多有一个节点没有被选中，树高又小于 $\lceil n/2\rceil$，故选出的节点至少有 $\lceil n/2\rceil$ 个。