2019 CCPC Online Contest
Problem A
Solved by Xiejiadong. 00:19:03 (+1)
题意：给出 $A$ 和 $B$ ，求最小的 $C$ 使得 $(A\; xor \; C)\; and \; (B\; xor\; C)$ 。
题解：按位考虑，显然只有在 $A$ 和 $B$ 同时为 $1$ 的时候， $C$ 才需要为 $1$ 。
那么显然，其他情况肯定是 $0$ 最优。
但又需要保证是正整数，所以想办法在 $A$ 和 $B$ 不想等的位置上，让 $C=1$ ，这样可以不影响 $(A\; xor \; C)\; and \; (B\; xor\; C)$ 的结果。
如果不存在这样的位置，那就只能 $C=1$ 让结果变大了。
Problem B
Solved by Xiejiadong && Kilo_5723. 04:27:56 (+2)
题意：要求支持两个操作，给一个数增加 $10^7$ ，询问一个前缀区间，求一个数，满足 $\ge k$ ，且与前缀区间中的每一个数都不同。
题解：每一个数增加了就是增加 $10^7$ ，而 $k\le 10^6$ ，相当于从区间里删掉了这个数。
给出的是一个排列，考虑维护每一个数所在的位置，于是就变成了求后缀区间第一个大于 $r$ 的位置。
线段树维护一下就好了。
Problem C
Solved by Xiejiadong. 03:00:29 (+)
题意：求字符串中和一个子串相同的第 $k$ 次出现的开始位置。
题解：无脑上 SAM ，对于每一个询问，找到询问的子串所在的结点。
方法是，先定位到 endpos $=r$ 的结点，然后在后缀树上二分向上倍增找到子串所在的状态。
于是剩下的问题，就是询问每一个状态的 endpos 集合中第 $k$ 大数，可以在树上启发式合并，用平衡树维护一下第 $k$ 大数就好了。
好像是个 SA 的经典题，直接在 height 上搞就好了。
Problem D
Solved by Kilo_5723. 03:06:41 (+1)
题意：给定一张有向图，每次询问其中第 $k$ 大的路径。
题解：对所有路径排序吼，考虑每次找到比当前路径的下一条路径。
用 $path_u$ 代表一条从 $u$ 出发的可能为 $0$ 的路径，用 $Pset(u)$ 代表从 $u$ 出发的所有路径的集合，$next(path_u)$ 代表按长度顺序访问 $Pset(u)$ 中所有的路径时，$path_u$ 的下一条路径。那么首先，对于所有的 $path_u$，它肯定能表示为 $(u,v)$ 或 $(u,v)+route(v)$，其中 $(u,v)$ 代表一条从 $u$ 到 $v$ 的路径。
我们发现，$Pset(u)=\{0\}+\sum_{(u,v)exists}\{path_u|path_u=(u,v)+path_v\}$。要顺序访问 $Pset(u)$ 中的每一条路径，如果能顺序访问 $Pset(v)((u,v)exists)$ 中的路径，就相当于每次对当前每个 $v((u,v)exists)$ 所枚举到的路径 $path_v$，找到其中 $(u,v)+path_v$ 最小的，取出并将 $path_v$ 替换成 $next(path_v)$。
Problem E
Solved by Weaver_zhu. 01:03:31 (+)
Problem F
Solved by Kilo_5723. 00:17:27 (+1)
题意：给出一副写有数字的牌，每一次把一个数字的牌抽到第一张，求最后的牌的序列。
题解：按照抽牌的倒序拿出还未拿出的牌，再在原来的牌里顺序拿出还未拿出的牌。
Problem G
Solved by Kilo_5723. 00:06:32 (+)
题意：按题意生成一个 $2^k \times 2^k$ 的 $C/P$ 矩阵。
题解：根据题意模拟。
Problem H
Solved by Kilo_5723. 01:16:27 (+)
题意：池塘里有 $n$ 条鱼，抓一条鱼上来要 $k$ 分钟，煮第 $i$ 条鱼需要 $t_i$ 分钟。同一时间只能煮一条鱼，鱼一旦开始煮，直到煮好都不能拿出，求最少花多少时间把所有鱼都钓上来煮好。
题解：首先，我们要花费 $k$ 分钟钓上第一条鱼。接下来，可以证明模型可以转化为把 $n-1$ 次钓鱼时间分配给每一个 $t_i$，而每一条鱼花费的时间是煮的时间与分配的钓鱼时间的较大值。
对于每一个 $t_i$，可以免费分配 $\lfloor \frac{t_i}{k} \rfloor$ 次，这之后分配一次的代价是 $k- t_i\;{\rm mod}\;k$。对每一个 $k- t_i\;{\rm mod}\;k$ 排序，选出其中较小的几个和之前免费分配的凑出 $n-1$。
Problem I
Unsolved.
Problem J
Unsolved.
Problem K
Unsolved.