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 (+2)

题意：求字符串中和一个子串相同的第 $k$ 次出现的开始位置。

题解：无脑上 SAM ，对于每一个询问，找到询问的子串所在的结点。

方法是，先定位到 endpos $=r$ 的结点，然后在后缀树上二分向上倍增找到子串所在的状态。

于是剩下的问题，就是询问每一个状态的 endpos 集合中第 $k$ 大数，可以在树上启发式合并，用平衡树维护一下第 $k$ 大数就好了。

好像是个 SA 的经典题，直接在 height 上搞就好了。

Problem D

Solved by Kilo_5723. 03:06:41 (+1)

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 (+)

Problem H

Solved by Kilo_5723. 01:16:27 (+)

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.