Task A
显然,$sum_{\text{反面}}=21-sum_{\text{正面}}$
Task B
将字符串翻转,并且把所有 6
换成 9
。
Task C
寻找 $A_i=B_{C_j}$ 的 $(i,j)$ 对数。
令 $P_i$ 为 $A$ 中为 $i$ 的个数。
令 $Q_i$ 为 $B_{C_k}=i$ 中 $k$ 的个数。
答案即为 $\prod P_iQ_i$。
Task D
字符串 $S$ 有 $A$ 个 a
和 $B$ 个 b
。
求所有 $S$ 中字典序第 $k$ 小的。
形象来说,所有的字符串是类似于这样的。
a......
a......
...
...
a.....
b.....
...
...
b......
首先确定 第一位是落在 $a$ 上还是 $b$ 上。
其中,以a开头的有$C_{a+b}^a$个。拿 $k$ 和这个分界线比较。如果是b开头就减去这个数。
接下来更新 $a,b$ 的剩余量。
类似地比较后面的位置。
Task E
写一个数据结构维护 深度为 $d$ 且在 $u$ 子树里的点。
先写出 dfs 序,化为区间问题。
问题转化为求区间内等于 $x$ 的数的个数。
这个用莫队可以维护。
为什么我会想到这么奇怪的做法。。。
最后在 $21:43$ 成功写完。
因为 AtCoder 的评测机很快,时限松,还可以加火车头,所以 $O(n\sqrt q)$ 随便跑 $2\times 10^5$。
其实E题也可以用树剖解决(