关于日记的某年某月某日的不知道该叫什么和哪天进行的 B 层模拟赛于是把这些全都塞进标题的这档子事 | 题解
A. 日记和绝世好课
A1. 题意简述
给定 $n, m, q, a_i, b_i, k_j, l_x, r_x(1\leq i\leq n, 1\leq j\leq m, 1\leq x\leq q)$，请对每个 $x$ 计算以下表达式的值：
$$\sum\limits_{i=1}^{n}\sum\limits_{j=l_x}^{r_x}a_i[b_i\geq k_j] \pmod{10^9+7}$$
A2. 部分分 - 20
按题意模拟即可。时间复杂度：$O(nmq)$。
A3. 部分分 - 32~48
如果我们对所有的 $i,j$ 计算出 $a_i[b_i\geq k_j]$ 的值，并求出二维前缀和，就可以在 $O(nm)-O(1)$ 的时间内求出答案。如果只求了一维前缀和，复杂度会变成 $O(nm)-O(m)$，可以得到 32 分。
A4. 题解
中间的部分分我真不知道怎么做。
考虑这个式子的含义。它的含义是，对于每一个学员 $i$，他的贡献是他的权值 $a_i$ 乘上在 $[l_x, r_x]$ 区间内的、他能切掉（$b_i\geq k_j$）的题的个数。但是显然，这样不太好做。能不能换一个处理方式？
对于一道题，哪些学员能与它产生贡献？能切掉它的学员。因此，我们将学员按水平 $b$ 排序，这样可以 $O(\log n)$ 地找到能与一道题产生贡献的所有学员。这些学员的贡献为他们的权值 $a$ 之和，于是先 $O(n)$ 处理出权值前缀和，就可以做到 $O(\log n + 1) = O(\log n)$ 地计算贡献。
我们对每道题都这样计算一次，复杂度是 $O(m\log n)$ 的。这之后，询问就变成了查询 $[l_x, r_x]$ 范围内每道题的贡献和，可以套一层前缀和。
总的复杂度：$O(m\log n + q)$。为了卡掉询问带 $\log$ 的做法，迫不得已增加了 $q$ 的范围。
B. 日记和一车双端队列
B1. 题意简述
看起来像可持久化双端队列的题。有双端队列的基本操作，每次询问两个版本的共同元素的个数。
B2. 部分分 - 24
考虑存储每个版本里每个数是否出现，时间和空间复杂度均为 $O(nW)$。每次询问需要枚举每个元素，时间复杂度为 $O(qW)$，大概能跑到 24pts，如果常数太大可能只有 16pts。
B3. 部分分 - 40
发现询问相当于是把两个版本与一下再 popcount，因此可以 bitset 优化。其具有 $\frac{1}{64}$ 的时间常数和 $\frac{1}{8}$ 的空间常数，可以跑到 $5\times 10^4$，有 40 分。大概给了 O2 优化。
B4. 部分分 - 60
这部分是 $k=1$ 的情况。我们记一个数出现的版本为 $[l_i,r_i]$，由于一个数最多出现一次，出现的版本一定在一个区间内。这样，对询问 $[x,y]$ 有贡献的数就一定满足 $l_i\leq x\leq y\leq r_i$，可以二维偏序。
原题：CCPC2023 吉林站 I. Deque
B5. 题解
以上的做法可以对这个做法有所启发。一个数最多出现两次，也就是其出现的版本可能为两个区间 $[l_{1,i},r_{1,i}] \cup [l_{2,i},r_{2,i}]$。贡献条件可能为 $l_{1,i}\leq x\leq y\leq r_{1,i}$ 及其对称 $l_{2,i}\leq x\leq y\leq r_{2,i}$，也可能为 $l_{1,i}\leq x\leq r_{1,i}\leq l_{2,i}\leq y\leq r_{1,i}$。前两者都很好做，只要按以上的做法二维偏序即可。
用括号来表示一个数出现和删除的时刻，则贡献条件可以写作 ([])(), ()([]), ([)(])。第三种情况如果我们查询 $x\leq r_{1,i}\leq l_{2,i}\leq y$ 的话会多算上 [()()], [()(]), ([)()] 这些情况，考虑把这三种处理掉——再查询这三种情况。
但是，查询 [()(]) 或 ([)()] 时还会查询到 [()()]。所以，我们可以记 [()()] 的个数为 $a$，[()(]) 的个数为 $b$，([)()] 的个数为 $c$，([)(]) 的个数为 $d$。
接下来就可以做偏序了。如果我们记四次偏序的结果分别为 ans[1][i], ans[2][i], ans[3][i], ans[4][i]$，则：
1 | a = ans[1][i]; |
C. 日记和日记怪谈
C1. 题意简述
每步会走到当前节点子树内的随机节点，求不同的路径个数、走到 $n$ 的概率、期望的步数。
C2. 部分分 - 36
数据太烂了，导致暴力放了 36 分。考虑枚举每种情况，并按概率进行贡献。
C3. 部分分 - 68a
如果你写出了转移式，但不知道如何线性求解，你能得到 68 分。
C4. 部分分 - 68b
如果你不会算期望步数，你能得到 68 分。
C5. 题解
第一个问题是很好做的，我们记 $f_i$ 为从 $i$ 出发的路径个数，则：
$$
f_i = \begin{cases}
1 & i\in \mathrm{leaf}\
\sum\limits_{j\in \mathrm{subtree}_i}f_j & i\in \mathrm{leaf}\
\end{cases}
$$
第二个问题涉及到了概率。记 $g_i$ 为从 $i$ 出发的成功概率，则：
$$
g_i = \begin{cases}
1 & i=n\
0 & i\in \mathrm{leaf}, i\neq n\
\dfrac{\sum\limits_{j\in \mathrm{subtree}_i}g_j}{\mathrm{size}_i-1} & i\in \mathrm{leaf}\
\end{cases}
$$
因为每个转移是等概率的，因此可以把每个转移的成功概率加起来，并除以转移个数。
最后是期望步数 $h_i$。这个转移与成功概率很类似：
$$
h_i = \begin{cases}
0 & i\in \mathrm{leaf}\
\dfrac{\sum\limits_{j\in \mathrm{subtree}_i}h_j}{\mathrm{size}_i-1} + 1 & i\in \mathrm{leaf}\
\end{cases}
$$
先用一样的套路求出每个转移的期望步数的平均值，此时要将其 $+1$ 才能得到期望步数（因为这次转移需要一步）。
注意，这些转移里都需要求子树和，需要在维护 $f,g,h$ 的同时维护 $\sum f, \sum g, \sum h$。如果没有维护，复杂度会退化为 $O(n^2)$，只有 68 分。
D. 日记和三分图
众所周知，这道题假掉了，所以这里的题解注释了。如果你真的想看，可以 F12 取消注释。
E. 日记和文化课
E1. 题解
直接求。$\mathrm{ans} = \sum\limits_{i=1}^n a_ip_i$。
F. 日记和完美构造
F1. 题解
抛开那些形式化定义，插入一个数字使得整个数为 9 的倍数。插入什么数字是可以确定的，插入位置可以贪心：从高往低，如果当前位置能减小字典序，则当前位置一定最优；否则放到末尾一定最优。