2021.09.27模拟赛

竹杖芒鞋轻胜马，谁怕？一蓑烟雨任平生

2021.09.27模拟赛

A. e

e

先把树上主席树建出来，找到 $\min(|a_p-r|)$ 就是找 $r$ 的前驱后继，可以在主席树上二分

因为是最小值，所以不用考虑链重复的问题，不用把虚树建出来，只用查询所有点到 lca 链上的前驱后继即可

code

B. 简单的序列

简单的序列

考虑如果中间 $m$ 的字符串有 $k$ 个未匹配的右括号，$l$ 个未匹配的左括号

那么需要左边有 $k$ 个未匹配的左括号，右边同理，还需要枚举 $j$ 个括号作为左边匹配右边的

预处理 $\mathrm{cnt}_{i,j}$ 表示 $i$ 个括号有 $j$ 个未匹配的左括号

考虑当前加入一个右括号，会抵消一个，转移到 $\mathrm{cnt}_{i+1,j-1}$

否则是 $\mathrm{cnt}_{i+1,j+1}$

复杂度 $O((n-m)^2)$

C. 简单的期望

简单的期望

emm

显然 $2$ 的次数就是二进制下末尾连续 $0$ 的个数

发现一个关键性质是只有 $200$ 次操作，而 $2^8 > 200$

所以第 $9$ 位的进位最多只会进一次

那考虑 $dp_{i,S,k,0/1}$ 表示操作了 $i$ 次，低 $8$ 位状态为 $S$ ，第 $9$ 位为 $0/1$ 后面连续的概率

大力转移即可

code