近五年 CSP NOIP 补题记录

2025.6.18

NOIP2024 T4 树上查询

To be updated.

Submission

CSP-S2019 江西 T3 网格图

To be updated.

Submission

2025.6.19

CSP-S2019 D1T2 括号树

To be updated.

Submission

CSP-S2021 T3 回文

To be updated.

Submission

CSP-S2019 江西 T1 日期

To be updated.

Submission

CSP-S2019 江西 T2 和积和

记 \(s_i=\sum_{j=1}^i a_j\)，\(t_i=\sum_{j=1}^i b_j\)，原式等价于

\[\sum_{1\le l\le r \le n}(s_r-s_{l-1})(t_r-t_{l-1}) \]

将式子拆开分别计算

\[\sum_{1\le l\le r \le n}s_rt_r-\sum_{1\le l\le r \le n}s_rt_{l-1}-\sum_{1\le l\le r \le n}s_{l-1}t_r+\sum_{1\le l\le r \le n}s_{l-1}t_{l-1} \]

固定右端点，令 \(r=i\)，即

\[\sum_{i=1}^n (is_it_i-s_i\sum_{j=0}^{i-1}t_j-t_i\sum_{j=0}^{i-1}s_j+\sum_{j=0}^{i-1}s_jt_j) \]

对后三项分别前缀和预处理（或顺便计算），时间复杂度 \(O(n)\)。

Submission

CSP-S2019 D1T1 格雷码

直接按照题意从高位到低位模拟，如果当前 \(k\) 在 \(n\) 位格雷码中在右半段，则输出 \(1\)，并根据对称性对应到左半段，继续递归下去即可。

只需维护区间长度的一半可以只用 unsigned long long，不用 int128。

Submission

CSP-S2019 江西 T5 多叉堆

设 \(f_u\) 表示以 \(u\) 为根的子树构成不同多叉堆的方案数。显然最小的 \(0\) 应该分配给 \(u\)，剩下的分给子节点 \(v_1,v_2,\cdots,v_k\)，根据乘法原理，有

\[f_u=\prod_{i=1}^k \binom{siz_u-1-\sum_{j=1}^{i-1}siz_{v_j}}{siz_{v_i}}f_{v_i} \]

将组合数和 \(f\) 分开，观察到组合数全部乘起来后分子即为 \((siz_u-1)!\)，分母即为子节点大小阶乘的乘积，即

\[f_u=\dfrac{(siz_u-1)!}{\prod_{i=1}^ksiz_{v_i}!}\prod_{i=1}^kf_{v_i} \]

直接使用并查集维护点的关系，并在合并时更新对应的 \(f\) 即可。使用快速幂计算逆元，时间复杂度 \(O(n\log n+q)\)。

Submission

CSP-S2020 T2 动物园

首先通过按位或运算求出哪些位置上有 \(1\)。由于 \(q_i\) 互不相同，故只需要记录某个位置是否需要购买（别的买不买没关系）。当某个位置上已经有 \(1\) 或这个位置不需要购买任何东西时，则编号在这个位置可以为 \(0/1\)。记这样位置的数量为 \(ans\)，则答案为 \(2^{ans}-n\)。注意细节：

• 当 \(n=0,ans=64\)，答案为 \(2^{64}\)，超出 ull 范围，要特判输出。

• 当 \(ans=64\) 时，利用 ull 的自然溢出，直接输出 \(-n\) 即可。

• 其他情况正常输出。

Submission

2025.6.20

CSP-S2022 T4 数据传输

以下的矩阵乘法均为广义矩阵乘法，即若矩阵 \(C=A\times B\)，则

\[C_{i,j}=\min_k A_{i,k}+B_{k,j} \]

根据所学显然满足结合律，证明略。

• \(k=1\)

答案即为路径上的点权和。考虑 dp，则有 \(f_i=f_{i-1}+a_i\)，写成矩阵即为：

\[\left[ \begin{array}{}f_i\\0\\0\\ \end{array} \right] = \left[ \begin{array}{}a_i & +\infty & +\infty\\+\infty & 0 & +\infty\\+\infty & +\infty & 0 \end{array} \right]\left[ \begin{array}{}f_{i-1}\\0\\0\\ \end{array} \right] \]

• \(k=2\)

此时显然不会走到路径外面。假设从 v 走向父节点 u，如果走去 u 的另一个子节点，那么下一步必须要走到 u 的父节点，显然不优于直接从 v 走到 u 的父节点。写成 dp 就是 \(f_i=\min(f_{i-1},f_{i-2})\)，矩阵：

\[\left[ \begin{array}{}f_i\\f_{i-1}\\0\\ \end{array} \right] = \left[ \begin{array}{}a_i & a_i & +\infty\\0 & +\infty & +\infty\\+\infty & +\infty & 0 \end{array} \right]\left[ \begin{array}{}f_{i-1}\\f_{i-2}\\0\\ \end{array} \right] \]

• \(k=3\)

此时最优的方案可能出现到路径距离为 \(1\) 的点。不难发现，这个点的点权一定是到同一个点的距离为 \(1\) 的点中的最小值。先预处理出每个点到其距离为 \(1\) 的点权最小值 \(w_i\)，设 \(f_{i,{0/1/2}}\) 表示跳到离 \(i\) 距离 \(0/1/2\) 的最小总权值，则有转移：

\[\begin{array}{l}f_{i,0}=\min(f_{i-1,0},f_{i-1,1},f_{i-1,2})+a_i \\ f_{i,1}=\min\left\{ \begin{array}{l} f_{i,0}+w_i，从这个点直接跳过来\\ \min(f_{i-1,0},f_{i-1,1})+w_i，从上一个点（或到其距离为 1）跳过来，并取这个点\\ f_{i-1,0}，从上一个点不花费代价跳过来，只是为了方便下一次转移（只跳了 2 次） \end{array} \right. \\ f_{i,2}=f_{i-1,1},到上一个点距离为 1 的点到该点距离为 2\end{array} \]

整理并代入 \(f_{i,0}\)，将所有式子写成 \(\min\) 形式。

\[\begin{array}{l}f_{i,0}=\min\left\{ \begin{array}{l} f_{i-1,0}+a_i\\ f_{i-1,1}+a_i\\ f_{i-1,2}+a_i \end{array} \right. \\ f_{i,1}=\min\left\{ \begin{array}{l} f_{i-1,0}+0\\ f_{i-1,1}+w_i\\ f_{i-1,2}+a_i+w_i \end{array} \right. \\ f_{i,2}=\min\left\{ \begin{array}{l} f_{i-1,0}+\infty\\ f_{i-1,1}+0\\ f_{i-1,2}+\infty \end{array} \right. \end{array} \]

写成矩阵就是

\[\left[ \begin{array}{}f_{i,0}\\f_{i,1}\\f_{i,2} \end{array} \right] = \left[ \begin{array}{} a_i & a_i & a_i\\ 0 & w_i & a_i+w_i\\ +\infty & 0 & +\infty \end{array} \right]\left[ \begin{array}{}f_{i-1,0}\\f_{i-1,1}\\f_{i-1,2} \end{array} \right] \]

答案应取 \(0\) 位置对应的值。

预处理出每个点对应的转移矩阵 \(m_i\)，使用倍增预处理和快速计算从下往上和从上往下一段的矩阵乘法，分别记为 \(m_1\) 和 \(m_2\)。取深度较深的一点作为起点 \(u\)，则最终的矩阵乘法结果为 \(m_v\times m_{fa_v}\times\cdots\times m_{\operatorname{LCA}(u,v)}\times\cdots\times m_{fa_u}\times nw\)（根据矩阵乘法的定义，从右往左运算，运算时靠左的矩阵作为 \(A\)，靠右的作为 \(B\)，又满足结合律，故可以先计算除 \(nw\) 外的部分），其中

• \(k=1,2\) 时，

\[nw=\left[ \begin{array}{}a_u & +\infty & +\infty\\+\infty & 0 & +\infty\\+\infty & +\infty & 0 \end{array} \right] \]

• \(k=3\) 时，

\[nw=\left[ \begin{array}{}a_u & +\infty & +\infty\\a_u+w_u & 0 & +\infty\\+\infty & +\infty & 0 \end{array} \right] \]

即除了有 \(a,w\) 的部分其它为广义下的单位矩阵。最左边一列即对应 \(f_u\) 的值（即推导中的 \(f_1\) 的值，边界条件）。时间复杂度 \(O(L^3(n+q)\log n)\)，其中 \(L=3\)。

Submission

2025-6-27

CSP-S2020 T3 函数调用

发现操作 \(1\) 是最简单的，考虑把操作 \(2,3\) 都转化为 \(1\)。

首先使用一次拓扑排序求出每个点的乘法标记，即调用一次该函数会使全部数乘上多少。这个要在反图上，因为是从后面的函数乘过来的。

由于一次操作 \(2\) 乘 \(k\) 可以转化为 \(k\) 次操作 \(1\)，因此可以再拓扑一次，求出每个函数的执行次数。这次是在正向图上，且由一个函数递归到子函数时应倒序遍历子函数（后执行的子函数对先执行的子函数有乘法影响），并且乘上子函数的乘法标记。初始时可以设 \(0\) 为主函数，执行次数为 \(1\)，并与依次要执行的函数建边。最后每个数自身要乘上主函数 \(0\) 的乘法标记。时间复杂度 \(O(n+m+q)\)。

Submission