给定 $n$ 个线段，将线段分成两个集合，两个集合之间的线段没有交集。
按左端点排序，将和第一个相交的一整段抠出来，剩余放在第二个集合内。
求树上最长路径，满足路径上点权的 $\gcd$ 大于 $1$。
点分治一下。
点权不是很大，考虑把路径的质因子抠出来 $dp$。
给定一个长度为 $n$ 的序列，将序列分成最多线段，满足线段集合的任意子集没有异或和为 $0$。
转换成前缀和，即变成选择最多的单点，且必须选择最后一个点，使得任意子集异或和不为 $0$，即线性无关，线性基插入即可。
按照时间顺序给定一场比赛某些时刻的比分，求最多有多少时刻出现平局。
时间按照不降序给出，相邻两个时间点可能会出现重合，维护一下最后统计的平局时间，防止遗漏。
给定一个 $n \times m$ 的表，表示第一块 $n$ 个物品和第二块 $m$ 个物品之间的权值关系，大于，小于或相等，要求恢复出每个物品的权值。
将权值相同的点缩点后跑拓扑排序即可。
一开始缩点的时候没写 find(x) 挂了一堆 T^T。
有一个 $1$ 到 $n$ 的排列，有 $n-1$ 次操作，每次将两个数字所属的块合并，这两个块一定相邻，要求恢复出原排列。
并查集维护一下所属关系，链表维护每个块内有哪些点。
给一个 $10^6$ 位的大数（每位数均为 $1$ 到 $9$），一次操作可以保留一段连续区间，其余位置置 $0$。
有 $q$ 次询问，每次询问一次操作后得到的最小的 $m$ 的倍数。
类似于询问区间异或等于 $0$，这里变成模 $m$ 加法，询问一段连续区间模 $m$ 为 $0$。
从低位往高位扫一遍，维护每种模数出现的最后位置，第一次出现同余即是最小的 $m$ 倍数。
询问 $[l,r]$ 区间内有多少个数在 $k$ 进制表示下有 $m$ 个尾 $0$。
转化为前缀和。
$k$ 进制下恰好有 $m$ 个尾 $0$，即是 $k^m$ 倍数而不是 $k^{m+1}$ 的倍数。
为了避免一些乱七八糟的情况，我选择交 python。
给定一个有向无环图，每个点有一个权值 $a_i$，求 $1$ 到 $n$ 的路径中，路径经过点的点权的中位数的最大值。
二分答案，$check$ 能否构造出中位数为 $mid$ 的路径。
将点权大于等于 $mid$ 赋值为 $1$，否则为 $-1$，求 $1$ 到 $n$ 的 DAG 最长路，判断最长路是否非负即可。
给定一个序列，求大小为 $m$ 的子集中的方差最小值。
排过序后，一定是连续的 $m$ 个数，扫一遍即可。
给定一个序列，求有多少个位置删除后，奇数位置和等于偶数位置和。
预处理每个后缀的奇数和，偶数和即可。
回文矩阵，左右翻一下，上下翻一下，都和原矩阵相同。
注意一下奇数时的处理即可。
写错了个条件 FST 了 T^T。
有 $n$ 杯咖啡，要写 $m$ 页书。每杯咖啡有权值 $a_i$，每天喝第一杯咖啡可以写 $a_i$ 页，第二杯咖啡 $max(0,a_i-1)$ 页，第三杯咖啡 $max(0,a_i-2)$ 页。求最少多少天可以写完 $m$ 页。
对所有咖啡权值排序。
二分答案。显然，权值大的咖啡尽量在每天第一个喝。
给一个序列，找平均值最大且最长的连续区间的长度。
差点没反应过来？平均值最大一定是序列的最大值，就是找最长的连续最大值。
给一个长度为 $n$ 的 UDLR 风向序列周期出现，每天你会被风向吹一格，你自己可以移动一格，两者独立，求从起点走到终点最少需要多少天。
二分天数。当天数大于最小值时，显然可以反方向走风向，也可以到达终点，因此可以二分。
预处理出，周期序列上每天的风向偏移量，可以得到 $mid$ 天后总共偏移了多少，最后判断一下曼哈顿距离即可。
求长度为 $n$ 的满足条件的不同 01 串个数，0 必须是连续的 $m$ 个位置。
考虑 $dp[i]$ 表示长度为 $i$ 的答案，有转移方程 $dp[i]=dp[i-1]+dp[i-m]$。
由于 $n$ 很大，$m$ 很小，矩阵快速幂加速 $dp$ 转移即可。
给定一个串，要你猜某个 $1$ 到 $n$ 的排列，按照这个排列做一个映射得到的加密串是什么。
你只有 $3$ 次询问，$1 \le n \le 10000$。
由于 $26^3 > 10000$，对每个位置 $26$ 进制拆分后，最多 $3$ 位数。
第一次询问，$abc…zabc…z…$，则 $a$ 相同的位置无法确定，第二次询问即是 $26$ 进制拆分的第二位，第三次询问同样。
1 | struct Mat { |
$1$ 到 $n$ 个地点排成一行，相邻两个距离为 $1$，现在要从 $1$ 不回头走到 $n$。
走一个单位距离，消耗一点油，油箱最大容量为 $v$，每个点有一个加油站，第 $i$ 点加油的费用为 $i$ 块钱每升，求最小花费。
一开始尽量加满，然后每个位置如果油箱有空余且不能支持走完全程，就加油。
写错加油的容量，过了好久才过 T^T。
给一个一个序列，选两个数 $a_i$ 和 $a_j$，选一个 $a_j$ 的因子 $x$，将两个数变成 $xa_i$ 和 $a_j \over x$，求序列总和最小能变成多少。
式子写出来
贪心的想，$a_i$ 肯定选最小的，$j$ 枚举即可。
给一个序列，求有多少长度为偶数的连续子序列，满足序列前一半和后一半的异或和相等。
其实这个一半是骗你的，往一半上想就凉了。
实际上，就是求长度为偶数的区间，异或和为 $0$，统计一下每种异或前缀和的个数即可。
将一个回文串，切几刀，拼成一个和一开始不同的回文串，求最小切几刀。
首先，判断出无解的情况，显然如果前一半每个字母都相同，不管怎么切都不会弄成一个不同的回文串。
对于一个回文串，他肯定存在一个前缀不是回文串，对称地切两刀，交换前后缀位置就是一个新的回文串，且与之前不同，所以刀数最多为 $2$。
所以就要判断能不能切一刀，可以发现这个串是一个回文循环串，由于 $1 \le n \le 5000$，暴力即可。
求满足条件的 $n$ 个点带边权的树个数，边权取值范围是 $1$ 到 $m$，满足给定了 $a$ 和 $b$，树上 $a$ 到 $b$ 路径长度恰好为 $m$。
先只考虑 $a$ 到 $b$ 的路径，我们可以枚举这个路径上的边数 $i$，然后相当于将 $m$ 划分成了 $i$ 个数，由插空法可知有 $m-1 \choose i-1$ 种情况。路径上有 $i-1$ 个点可以随意选择，方案数为 $(i-1)!{n-2 \choose i-1}$。剩下 $n-1-i$ 条边的边权可以随意选择，方案数为 $m^{n-i-1}$。最后一部分就是求剩下的点挂在这条链上的树的个数。
由 Cayley定理，我们知道 $n$ 个带标号的点组成 $k$ 棵无根树的森林的方案数为 $k n^{n-k-1}(1 \le k \le n-1)$。
我们可以考虑将前一步选出来的路径上 $i+1$ 个点拿出来，加上剩余的点组成 $i+1$ 棵无根树。对于每棵无根树，为避免重复，将树上标号最小点设置定为根，这些根按第一部分连成树链即可。因此，只需要在最后乘上 $(i+1)n^{n-i-2}$。
点分治可以处理一类静态树上路径信息统计的问题。
点分治，选择一个点作为根，处理过这个根的路径，在将树分成若干子树递归的处理。
和序列的分治一样，我们希望树尽量平分，使得递归层数尽可能的小。
贪心的解决这个问题，选一个最大子树最小的点，即树的重心。这样递归的层数是 $O(\log n)$。
1 | struct LinearBase { |
1 | struct LinearBase { |
1 | LinearBase intersect(const LinearBase& A, const LinearBase& B) { |