环
Description
对于一个长度为 $n$ 的 $01$ 串，下标从 $0$ 到 $n-1$ 。定义两种类型的操作：
A类型：选择一个 $x$，将序列循环右移 $x$ 位，也就是新序列的第 $(i+x) \bmod n$ 位对应原序列的第 $i$ 位。
B类型：选择一个 $x$ ，满足序列的第 $x$ 个位置位 $1$ ，且第 $(x+1) \bmod n$ 位不为 $1$ ，交换序列的第 $x$ 个位置和第 $(x+1) \bmod n$ 个位置的字符。
给定 $n,k,l$ 。请构造一个由 $l$ 个长度为 $n$ 的 $01$ 串构成的序列 $S$，下标从 $0$ 开始。使得序列中每个串恰好有 $k$ 个 $1$ 。且对于 $0 \le i < l-1$，$S_i$ 既可以通过一次A类型的操作，也可以通过一次B类型的操作，变为 $S_{i+1}$。
Hint
$2 \le n,l \le 100$, $0 \le k \le n$, $1 \le T \le 10$。
Solution
首先，容易证明当 $k$ 与 $n$ 不互质时无解。 设 $S_i$ 中所有 $1$ 的位置的下标之和为 $W_i$ ，假设 $S_i$ 能够通过循环移位得到 $S_{i+1}$ ，那么必然存在整数 $x$ ，使得 $W_i+xk \equiv W_{i+1} \pmod n$ 。同时如果 $S_i$ 能够通过将一个 $1$ 右移一位得到 ，那么有 $W_i+1 \equiv W_{i+1} \pmod n$ ，由两式可以得到 $xk \equiv 1 \pmod n$ ，所以 $n, k$ 互质是解存在的必要条件。
当 $k$ 与 $n$ 互质时，容易给出一种构造。 因为 $k$ 与 $n$ 互质，所以 $k$ 一定存在模 $n$ 意义下的逆元，令 $S_0$ 的 $\frac{0}{k}, \frac{1}{k}, \cdots, \frac{k-1}{k}$ 位置处（这里和后面的位置均是指在模 $n$ 意义下）为 $1$ ，其余处为 $0$ 。同样的对于 $S_i$ ，我们令其 $\frac{i}{k}, \frac{i+1}{k}, \cdots, \frac{k+i-1}{k}$ 处为 $1$ ，其余处为 $0$ 。显然，从 $S_i$ 变成 $S_{i+1}$ 可以通过向右循环移位 $\frac{1}{k}$ 实现，同时发现 $\frac{i}{k} + 1 = \frac{k+(i+1)-1}{k}$ ，于是我们将 $S_i$ 的 $\frac{i}{k}$ 位置变成 $0$ ，将 $\frac{i}{k}+1$ 位置变成 $1$，即可用 $b$ 操作将 $S_i$ 变成 $S_{i+1}$ 。
DNA 序列
Description
给定 $n$ 个只包含 “A”,“T”,“C”,“G” 字符串，每个字符串取一个非空前缀，然后将这些前缀按任意顺序链接起来，问能获得的字典序最小的字符串是什么。
Hint
$1 \le n, m \le 50$。
Solution
首先，每个字符串后面加一个很大的字符（例如”Z”）。
对于每个字符串 $s$ ，找到最短的前缀 $x$ 满足 $x^\infty < s$ ，然后将字符串 $s$ 分成 $x^y+z$ ，使得 $x$ 不是 $z$ 的前缀。
那么合并的顺序一定是按照 $x^\infty$ ，字典序升序然后相同按照 $z+’Z’$ 的字典序降序。
我们可以考虑是每次我们希望找个最小的 $x$ ，然后加入尽量多的 $x$，但是 $x$ 加完之后我们希望能加的字符尽量小，所以我们把尾巴字典序最小的放后面。
知道顺序之后，倒着枚举前缀的长度暴力贪心就行了。
探寻
Description
给定一棵 $n$ 个点， $n-1$ 条边的树，边带权，节点编号为 $0 \sim n-1$ ，其中根的编号为 $0$，一开始你在根上，第一次走一条边需要花与边权相同数目的钱，走过一次这条边后再走这条边就不需要花钱，如果钱不够则不能走，第一次走到一个点 $x$ 可以获得 $val_x$ 的钱，之后再到达 $x$ 就不会获得钱，标记其中一个叶子为目标节点，求出到达目标节点所需的最少的初始钱数。
Hint
$2 \le n \le 2 \times 10^5, 0 \le cost_i, val_i \le 10^9$。
Solution
每次只走一步的贪心显然是错的，因为没有考虑走完这一步后的情况，所以我们从 $x$ 走到 $y$ 的时候，需要考虑 $y$ 整棵子树内的情况。
我们将走一个子树内的连通块成为一个决策，一个决策有两个属性 $(need, get)$，代表使用这个决策的前提是有 $need$ 的钱，使用完这个决策后的收益是 $get$，只有 $get > 0$ 的决策才是有用决策。
设当前节点为 $x$ ，$y \in son_x$ ，只走 $x$ 这一个点的决策显然是 $(cost_x, val_x-cost_x)$，如果 $val_x -cost_x < 0$ ，那么就需要从 $y$ 中选择决策增加 $x$ 的收益，这个可以将决策按 $need$ 比较，用可并堆维护子树内的决策即可，时间复杂度 $O(n \log n)$。
军训
Description
起点 $(0,0)$ ，每次只能走恰好曼哈顿距离为 $k$ 的点，构造一种到达 $(x,y)$ 且步数最小的方案，无解输出 -1。
Hint
$1 \le k \le 10^9, -10^5 \le x,y \le 10^5, (x,y) \not = (0,0)$
Solution
因为 $x,y$ 可正可负，不如先将 $x,y$ 取绝对值，输出时判符号。
如果 $k$ 是奇数，那么所有坐标都可达(存在一种方案从 $(x,y)$ 走到 $(x+1,y)$ )。
如果 $k$ 是偶数，那么 $x+y \equiv 1 \pmod 2$ 的所有坐标都不可达，其他坐标都可达(存在一种方案从 $(x,y)$ 走到 $(x+1,y+1)$ )
如果 $x+y > 2k$ ，那么直接向 $(x,y)$ 的方向走即可。
如果 $x+y \le 2k$ ，此时一定有 $2k-x-y \bmod 2 = 0$，设 $x+y+2t = 2k$，则 $t = k-\lfloor \frac{x+y}{2} \rfloor$，然后我们分两步走，每步在其中一个反方向走 $t$，这样两次走的反方向就是 $2t$ ，走过的距离就是 $x+y+2t=k$ ，正好能从 $(x,y)$ 走到 $(0,0)$
命题规范
Description
有 $n$ 种需要满足的命题规范，$m$ 个出题人，提供 $a_{i,j}$ 个大样例可以让第 $j$ 个出题人满足第 $i$ 个规范，在找到第 $i$ 个出题人满足规范之前，需要先提供 $b_i$ 个大样例。
求满足所有命题规范最少提供多少大样例。
Hint
$1 \le n \le 10^5, 1 \le m \le 25, 1 \le a_{i,j},b_i \le 10^9$
Solution
直接暴力是 $O(nm2^m)$ 的，首先 $2^m$ 没办法省掉，那么需要避免每次枚举 $nm$ 来计算答案。
如果还是保留暴力的取 $\min$ ，是没办法降低时间复杂度的，因为取 $\min$ 无法继承贡献。
考虑出题人选定时每道题的贡献: 最小的出现在出题人集合里的数。
一个小 trick: 差分数组的前缀和是原数，这样的话我们可以把取 $\min$ 变成求和操作，方便继承贡献。
对于一道题 $i$ ，设 $a_{i,p_1} \le a_{i,p_2} \le \cdots \le a_{i,p_m}$，设选择的出题人集合为 $S$ ，对于 $1 \le j \le m$，若 ${p_1, p_2, \cdots, p_{j-1}} \subseteq {1,2,\cdots,m} \setminus S$ ，则答案需要加上 $a_{i,p_j}-a_{i,p_{j-1}}$，我们将这个数作为集合 ${p_1, p_2, \cdots, p_{j-1}}$ 的贡献。
出题人集合 $S$ 的答案即为 ${1,2,\cdots,m} \setminus S$ 的子集和。
时间复杂度 $O(nm \log m + m2^m)$。
前置知识
Description
给定两个长度为 $n$ 的序列 $a,b$，求一个 $1$ 到 $n$ 的排列 $c$ ，最小化:
$$\sum_{i=1}^{n} \left\lceil \frac{\max(b_i-a_{c_i}, 0)}{k} \right\rceil$$
Hint
$1 \le n \le 10^5, 1 \le a_i,b_i,k \le 10^9$
Solution
考虑一个贪心。
首先问题可以看成每次操作把某个 $b_i$ 减去 $k$ ，求最少次数使得存在排列 $c$ 满足 $b_i \le a_{c_i}$。
对比当前 $a,b$ 中最大值，如果 $\max{a} \ge \max{b}$，那么直接把这两个数配成一对即可，否则把 $b$ 种的最大值减去 $k$。
用 map 和 set 加速贪心过程即可，具体就是把 $\lfloor \frac{b_i}{k} \rfloor$ 相同的 $b_i$ 一起处理，时间复杂度 $n \log^2 n$。