给一棵 $n$ 个点带权边权的无根树，要求在在树上选一些边，构成树上的正好 $m$ 条路径，并且每条边最多只能在一条路径中出现，要求最大化每个选择方案中的最小路径长度。
二分答案。
二分答案，$check(mid)$ 判断能不能将一条链划分成 $m$ 个最小值为 $mid$ 的段，每段可以贪心的选取大于等于 $mid$ 的最小段。
只有两种情况，一种是只选择一条边，第二种是选择跨过根节点的两条边。
对于长度大于等于 $mid$ 的边，单独构成一条链，对于长度小于 $mid$ 的边，贪心地去和最小的能连在一起长度大于等于 $mid$ 的边组成一条链。
树上每个节点与其父亲只有一条边，因此在一个节点完成类似于菊花情况的匹配的时候，可能会剩下多条边，而这些边中选一个最大的传递到父节点，与当前节点到父节点的边组成一条链，在父亲节点类似的做菊花情况的操作。
Candidate Master！
模拟。
差点不会 dfs 了。
给 $n$ 个括号序列，两两配对，每个最多出现在一对里面，求最多能匹配上多少对。
将所有括号序列转成 $l$ 个左括号和 $r$ 个右括号。当且仅当，左右括号至少一个为 $0$ 才对答案有贡献，统计每种左右括号个数的出现次数，左右括号相等时才能凑成一对，已经平衡的序列个数除二加到答案里面。
给出一个数 $n$ 和次数 $k$，每次将这个数随机变成他的一个因子，这个操作恰好执行 $k$ 次，求最后出现的数的期望。
大力猜了一发，只需要求 $n$ 的所有素因子 $p^\alpha$ 的期望 $f_p(\alpha, k)$，全部乘起来即可。
实际上，从每个素因子里面取这个事件之间相互独立，乘积的期望等于期望的乘积。
下面求这个 $n=p^\alpha$ 的期望，有递推式
$$
f_p(\alpha, k) = \frac{1}{\alpha + 1}\sum_{i=0}^\alpha f_p(i, k-1) \
f_p(\alpha, 0) = p^\alpha, f_p(0, k) = 1
$$
推了半天推不出公式，直接记忆化搜索，复杂度不知道。
出题人是不是弹丸粉？
维护 $n$ 个多重集合，有 $4$ 种操作：
第 $x$ 个集合变成 ${v}$；
第 $x$ 个集合变成第 $y,z$ 两个集合的多重集的并集；
第 $x$ 个集合变成第 $y,z$ 两个集合的积集元素的 gcd；
询问第 $x$ 个集合内有多少个 $v$，模 $2$ 输出答案。
询问要求模 $2$，考虑用 bitset 进行维护，如果我们维护的是每个数的出现次数，操作三将难以维护。
转化为维护集合内每个数是多少个数的因子，记集合内有 $a(d)$ 个数含有因子 $d$，$x$ 的出现次数为 $f(x)$，那么
$$
a(d)=\sum_{i=1}^\infty f(id) \
f(n)=\sum_{i=1}^\infty \mu(i) a(in)
$$
下面那个是我抖机灵凑出来的。
因子和询问系数可以预处理得到。
对于操作一，直接将因子集合赋值，操作二等价于按位异或，操作三等价于按位且，操作三等价于用预处理的容斥系数作用在 bitset 上，即按位且后 $1$ 的个数。
对于操作三，单独考虑某一个因子，他对积集的这个因子出现次数的贡献为另一个集合含有这个因子的个数，最终这个因子出现次数就是两个集合内出现次数的乘积。
$ans=3min(y,b-1,r-2)$。
给出 $n$ 组坐标和 $n$ 组偏移，每一个坐标对应一个偏移，顺序打乱，但是所有坐标加偏移得到的位置相同。
答案为 $x$ 和 $y$ 的均值。
$n$ 个人组成一个环，从第 $1$ 个开始间隔 $k(1 \le k \le n)$ 报数，直到回到 $1$，定义 $f_k$ 表示这个循环节的编号之和，输出 $n$ 的所有可能 $f$。
编号为 $k$ 的路径是一个首项为 $1$ 的公差为 $\gcd(n,k)$ 的等差数列（由裴蜀定理容易知道），$O(1)$ 计算 $f_k$。因为只有 $n$ 的因子才对答案有贡献，质因数分解即可。
将 $1,2,\cdot\cdot\cdot,n$ 的所有排列按字典序连在一起，求长度为 $n$ 的连续子区间之和为 $\frac{n(n+1)}{2}$ 的个数。
将每个排列分成两块，前面 $k$ 个的排列的每一个对应了 $n-k$ 的排列，连续的 $(n-k)!$ 个两边连在一起对答案有贡献，$g(k)=\frac{n!}{k!}(k!-1)$，对 $g(k)$ 求和。
$n+1$ 个点的图，给出前 $n$ 个点的度数序列，问第 $n+1$ 个点的所有可能取值。
根据握手定理可以知道最后一点度数的奇偶性，并且如果度数可以取到 $x,y(x < y)$，那么 $[ x, y ]$ 中都可以很容易构造出来。
因此可以二分上下界。
对于一个点的度数是否可行，可以应用 Erdos-Gallai Theorem 判定。
一个人从左往右走，道路被分为很多条草地、水和山，在草地上速度为 $5m/s$，在水里游的速度为 $3m/s$，飞的速度为 $1m/s$，每走或游一米可以获得一点能量，飞行每一米都需要一点能量，求最小时间（所有路程能量都是在实数范围内取值）。
考虑贪心，在草上走路，在水里游，在山上飞。如果飞山时能量不足，就在之前补充能量。如果最后能量多余，能量的一半提供给草地和水里（消耗能量和没有获取能量）。能量兑换为路程时，必须要满足路程数的两倍不超过能量总数，因为飞山的时候可能会要求必须在草里获取能量。
First AK Div3…
模拟。
序列删掉一个数后最小极差。
显然要么删除最后一个，要么删除第一个。
构造，将 $n$ 划分成恰好 $k$ 个 $2$ 的幂次数之和。
我的构造方法：将 $n$ 二进制分解，从最高位往最低位拆，看能不能拆成 $k$ 个。
$n$ 个人围成一个环，每个人知道自己前面的两个人是谁，要求恢复出原来的环，保证有解。
实际上是已知了图上的 $n$ 条边，建图 dfs，把环跑出来，特判一下绕行的正反方向。
给定一个括号序列，数一下有多少个位置翻转后可以使括号序列平衡。
一个括号序列平衡的条件是，对于其每个前缀，左括号数量都大于等于右括号数量，并且最终括号总数相同。
那么可以将左括号设置 $+1$，右括号设置为 $-1$，跑一下序列的前后缀和，然后判断这个位置和其前后缀和加起来是否能够等于 $0$ 即可。
但是这里实际上不能保证满足第一个条件，可以再维护一下前后缀到多少满足这个条件，如果当前位置的子串包含这些非法的前后缀，则跳过。
注意一个细节：左括号变成右括号时，前缀和不能为 $0$。（因为要匹配新加入的括号，不过我的写法好像不需要特判？）
给定 $n$ 个点的点权，两个点连边的代价是两个点的点权之和，给定 $m$ 条边，这条边可以选择使用点权和或者这条边权，求最小生成树。
不考虑 $m$ 条边，实际上只需要从点权最小的点连向每一个点即可。
考虑 $m$ 条边，和点权最小的点连出的边一起加到最小堆内，跑一遍 Kruskal。
在 $[l,r]$ 内找到 $(x,y)$，满足 $x|y$ ，保证有解。
输出 $(l,2l)$。
在母串中删除一个子串，使得只剩下一种字母，求方案数。
分类讨论：
在正 $n$ 边形内取三个顶点连成大小为 $ang$ 的角。给定 $ang$，找最少正多少边形。
做出外接圆，圆周角对应的弧跨过 $k$ 条边，$ang=\frac{180k}{n}$，即找到最小的 $k$ 使得 $ang|180k$，并且 $k \le n-2$ （最多只能跨过 $n-2$ 条边）。
枚举一下 $k$ ，注意 $k$ 最大为 $360$。
在字符串 $s$ 中删掉一些字符，使得 $s$ 中不含有子序列 “hard”，删掉第 $i$ 个字符的代价是 $a_i$ ，求最小代价。
考虑 $dp[n][4]$，第一维表示使得前 $n$ 个字符不含 ‘h’ 的最小代价，第二维表示使得前 $n$ 个字符不含 ‘ha’ 的最小代价，第三维表示使得前 $n$ 个字符不含 ‘har’ 的最小代价，第四维表示使得前 $n$ 个字符不含 ‘hard’ 的最小代价。
转移方程：
当 $s[i]=$”$hard$”$[j]$ 时，
$$
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j]+a[i])
$$
否则：$dp[i][j]=dp[i-1][j]$。
$1$ 到 $n$ 的排列中有一些位置未知，求逆序数的期望。
好题！
排列中没有位置已知，那么期望是 $n(n-1)\over 4$ ，因为对排列中的任何一对数他们对逆序数贡献的期望为 $1\over 2$。
排列中所有位置已知，树状数组维护，倒着数一遍。
因此，我们只需要知道已知数和未知数之间的逆序数对期望的贡献。
记未知数有 $m$ 个，对于每个未知位置，他取到任何一个未知数的概率均为 $1 \over m$。
对于一个已知位置，其右边有 $k$ 个未知位置，那么如果这个数和后面任何一个未知位置对期望有贡献，则未知位置需要取一个小于当前数的未知数，每个位置之间是相互独立的，全部加起来即可。
对于这个已知位置的左边，也可以类似地 $O(1)$ 求出贡献。
模拟。
求解关于 $x$ 的不定方程 $(x / k) * (x % k) = n$ 的最小解。
对 $n$ 质因数分解即可。
平面分成了无数 $1 \times 1$ 的方格，给定 3 个方格的坐标，用最少的方格让这三个联通。
枚举两两之间的 6 个最近点，找这个最近点与第三个点的最短路径。
给一棵树，给树上每条边加一个非负实数范围上的权值，权值总和为 $S$，最小化树的直径。
显然，对于任意一条直径，都会经过两个度数为 1 的顶点，那么必须要给每个这样的叶子上的边平均分配 $S$。
二分了一个小时是怎么回事啊？
给一个数字 $n \le 1e9$ ，每次操作可以将 $n$ 减去一个不是其因子的数，求最小的结果。
显然，$gcd(n, n-1)=1$，直接输出 $1$ 即可。
注意特判掉 $n=2$。
$n$ 个人都戴了一顶某个颜色的帽子，第 $i$ 人的帽子颜色和 $a_i$ 个人不一样，要求恢复出每个人的帽子颜色。
$a_i$ 可以转化为第 $i$ 个人的帽子颜色一共出现 $n-a_i$ 次，对于这种颜色一共有 $n-a_i$ 倍数数量的人与之颜色相同。
有点难写T^T？
一行有 $n$ 个位置，用 $m$ 种颜色染色，要求恰好有 $k$ 个位置，满足该位置和其左边位置颜色不同，求方案数。
显然，$dp[i][j]$ 表示前 $i$ 个位置恰好有 $j$ 个位置满足条件：
$$
dp[i][j] = dp[i-1][j]+(m-1)dp[i-1][j-1]
$$
给一个无向带权有重边自环的连通图，给出 $k$ 个关键点，求每个关键点到最远的关键点的距离（距离是路径最大边的长度的最小值）。
考虑对边权排序，按照 $Kruskal$ 的方式加边，维护每个联通块内关键点的个数，当所有关键点加入到一个联通块时，这里的边权就是相同的 $k$ 个答案。
证明，每次合并两个联通块时，联通块内的路径距离一定小于当前的边，当前边加入后，两个联通块内的答案就是一个块内关键点到另外一个块内的关键点的路径，路径距离即为新加入的边。又由于如果一个联通块内没有关键点，实际上答案并不会更新，实际上由于图的联通性，当关键点恰好加入一个块内时，所有点的答案都被更新了，并且向这个联通块内加入点并不会影响答案。
给一个长度为偶数的序列的所有偶数项 $a[2i]$，满足所有前缀和都是完全平方数。
简单推一推可知前缀和 $s[2i-1]$，$s[2i]$ 仅与给出的 $a[2i]$ 有关，即要求解方程 $p^2-q^2=a[2i]$，即 $(p-q)(p+q)=a[2i]$，质因数分解即可。另外由于前缀和要求严格单调，每次贪心地解出最小的 $s[2i]$ 。
