2023牛客暑期多校训练营7

A. Random Addition

B. Tree Climber

C. Beautiful Sequence

题意：求第 $k$ 大的单调不降序列，满足 $A_i \oplus A_{i+1}=B_i$

首先将式子转化一下，可以发现求第 $k$ 大的序列本质上就是求第 $k$ 大的 $A_1$，而对于 $B_i$，要想满足 $A_i \leq A_{i+1}$，有一个很明显的性质：$B_i$ 的最高 $1$ 位上 $A_i$ 是 $0$，$A_{i+1}$ 是 $1$，由于 $B_1 \sim B_{i-1}$ 都是确定的，我们可以等价转换为 $A_1$ 这一位上必须是 $0/1$，最后只要求满足上述条件的第 $k$ 大的 $A_1$ 即可，直接贪心，总复杂度 $O(n\log B)$，可以通过

~~这道题赛时调了好久，后来才发现是 i<MAXB 的 while 后面没加 i==MAXB 的 break 导致的，以后要记住~~

D. Game on Tree

E. Star Wars

F. Counting Sequences

G. Cyperation

H. Mountain View

I. We Love Strings

题意：给定 $n$ 个总长度为 $O(400)$ 的正则 01 串，求有多少个 01 串可以匹配其中至少一个 01 正则串

首先考虑 $n$ 比较小的时候怎么做，很明显有 $2^n$ 的容斥暴力，而 $n$ 比较大的时候由于有 $\sum |s| \leq 400$，所以我们可以分治一下，当 $n \leq B$ 时容斥，否则直接枚举暴力的结果直接判，这样复杂度就是 $O(2^B|s|+2^{\frac nB}|s|)$，当 $B=\sqrt n$ 时取得最小值 $O(2^{\sqrt n}|s|)$，可以通过

J. Is it a tree?

K. Set

L. Misaka Mikoto's Dynamic KMP Problem

题意：给定 $s$，要求支持单点修改 $s$ 的字符值和动态查询 $s$ 的 border 和给定 $t$ 中 $|s|$ 出现次数的乘积，$q$ 次询问，强制在线

看起来是道很麻烦的题，其实一点也不麻烦 容易发现当 $|s|>|t|$ 时询问的答案就是 $0$，所以我们可以只在 $|s| \leq |t|$ 时计算答案，由于 $\sum |t|$ 是可以输入的复杂度，所以我们完全可以每次重新 KMP 一遍，复杂度就是 $O(\sum |t|)$，可以通过

M. Writing Books

题意：求 $1 \sim n$ 用十进制表示的长度和

签到题，直接按十进制位分块即可，复杂度 $O(T\log n)$，可以通过