第十二届蓝桥杯大赛软件赛省赛第二场 C/C++ 大学 A 组 题解

输出 \(2021!! \bmod 10^4\)

for 循环每次减 \(2\) 即可

B. 格点

求第一象限整点中，\(xy\leq 2021\) 的整点个数

for 循环暴力遍历 \(2021\times 2021\) 的平面，统计答案即可

C. 整数分解

求 \(2021\) 分解为 \(5\) 个正整数的有序分解方案数

令 \(f_{n, p}\) 表示 \(n\) 被分解为 \(p\) 个正整数的有序分解方案数

搜索或递推均可

D. 城邦

给定编号为 \(1\)~\(2021\) 的 \(2021\) 元完全图，定义点权为编号数码的集合的元素和（例如 : \(2021\) 的为 \(2+0+1=3\)）。

定义连接两点 \(a, b\) 的边权为两点点权之和

求 MST 边权和

先暴力把 \(1\)~\(2021\) 的点权跑出来，然后所有边已知

由于是提交答案题，跑 Kruskal 或者 Prim 算法均可

E. 游戏

给定数值 \(n\) ，两人轮流进行游戏。每一轮可将数字 \(n\) 化为其因数之一，直到 \(n\) 变为 \(1\)

问 \(n=20210509\) 时的游戏方案数

令 \(f_d\) 表示从 \(d\) 开始，游戏的方案数，初始 \(f_1=1\)

用刷表法，将 \(d\) 的所有倍数 \(n\) ，均执行 \(f_n+=f_d\)

复杂度为 \(\displaystyle \sum_{i=1}^n \lfloor{n\over i}\rfloor\approx \sum_{i=1}^n {n\over i}=O(n\log n)\)

期望时长为 \(5s\)

F. 小平方

求 \([1,n)\cap Z\) 中，模 \(n\) 意义下，平方严格小于 \({n\over 2}\) 的数的个数

\(n\leq 10^4\)

for 循环暴力验证即可

G. 完全平方数

给定正整数 \(n\) ，求最小的正整数 \(x\) ，使得 \(nx\) 为完全平方数

\(n\leq 10^{12}\)

考虑到 \(n\) 大于 \(\sqrt n\) 的质因数最多 \(1\) 个

否则任意两个乘起来也超过 \(n\)

因此优先用欧拉筛或埃氏筛打出 \(\sqrt n\leq 10^6\) 范围内的质因数，将该部分的每个质数在 \(n\) 中的次数求出

若次数为奇数，则 \(x\) 中必须出现奇数次该质数，故取 \(1\) 次；否则 \(x\) 中需为偶数次，取 \(0\) 次

最后验证 \(n\) 是否仍有其他质因数，若有，则 \(x\) 中该质因数必须出现奇数次，同样取 \(1\) 次

H. 负载均衡

\(n\) 台计算机，第 \(i\) 台算力为 \(v_i\)

\(m\) 个任务，每个在 \(a_i\) 时刻送达，需要消耗 \(b_i\) 号计算机 \(c_i\) 的时间与 \(d_i\) 的算力

若分配任务时，计算机算力充足，必须执行任务，并输出剩余算力；否则输出 \(-1\)

\(n, m\leq 2\times 10^5\)

考虑将任务拆成两瓣：

1. \(a_i\) 时到达的，消耗 \(b_i\) 号计算机 \(d_i\) 算力的
2. \(a_i+c_i\) 时到达的，消耗 \(b_i\) 号计算机 \(-d_i\) 算力的

且第二个子任务奏效当且仅当第一个子任务奏效

因此，对任务标记原来的序号 \(i\) ，再按时间排序；时间相同时，算力为负数的任务（第二类任务）优先

维护每台计算机的剩余算力，按时间顺序执行任务

当执行第一类任务时，检查算力是否充足，充足则执行当前任务，更新剩余算力并输出；若不充足，则标记当前任务原来序号 \(i\) 不生效，并且输出 \(-1\)

当执行第二类任务时，检查当前任务是否生效，若不生效则直接退出；否则更新算力

复杂度为 \(O(n\log n)\)

I. 国际象棋

规定国际象棋棋盘中，位于点 \((x,y)\) 的马可以攻击 \(8\) 个方向：

1. \((x-2, y-1)\)
2. \((x-2, y+1)\)
3. \((x-1, y-2)\)
4. \((x-1, y+2)\)
5. \((x+1, y-2)\)
6. \((x+1, y+2)\)
7. \((x+2, y-1)\)
8. \((x+2, y+1)\)

   求 \(n\times m\) 的棋盘中，放置 \(k\) 匹马且不互相攻击的方案数

   \(n\leq 6, m\leq 100, k\leq 20\)

状压 dp ：预处理 \(n_{1, S}\) 表示当前行状态状态为 \(S\) 时，下一行的最大可选集合；\(n_{2, S}\) 表示下两行最大可选集合；\(cnt_S\) 表示 \(|S|\)

记 \(f_{m, S, T, k}\) 表示第 \(m\) 行状态为 \(S\) 且第 \((m-1)\) 行状态为 \(T\) 时，放置了 \(k\) 匹马且不互相攻击的方案数

不难得出，当且仅当 \(S\subseteq n_{1, T}\) 时方程有意义，且初始状态为 \(f_{1, S, 0, cnt_S}=1\)

状态转移采用刷表实现：将 \(f_{m, S, T, k}\) 刷到 \(\forall R\subseteq (n_{1, S}\cap n_{2, T}),f_{m+1, R, S, k+|R|}\)

答案为 \(\displaystyle \sum_S\sum_T f_{m, S, T, k}\)

发现第一维可以滚动成 \(m\bmod 2\) 形式，故空间复杂度为 \(2\times 2^n\times 2^n\times k=O(k\cdot 4^n)\)

时间复杂度为 \(m\times 2^n\times 2^n\times k+2^n\times 2^n=O(mk\cdot 4^n)\) ，显然充足

甚至加上了 \(S\subseteq n_{1, T}\) 的限制，根本拉不到那么大

J. 完美序列

这题题目是真的绕

定义完美序列为：满足除第 \(1\) 个数外，所有数为前一个数的因数的序列。

定义序列的完美值为：该序列所有完美子序列的长度最大值

求 \(1\)~\(n\) 的所有排列 \(P\) 中，每个排列中，所有长度为 \(\{n, (n-1), (n-2), \cdots , 1\}\) 的完美值的完美序列，它们的元素和

\(T\leq 10^5\) 组独立询问，每次询问 \(n\leq 10^6\)

当 \(n=3\) 时，\(\{3, 2, 1\}\) 的完美值为 \(\{2, 1\}\) 的长度 \(2\)

考虑 \(n=3\) 的所有排列：

1. \(\{1,2,3\}\) 不含长度为 \(2\) 的完美序列
2. \(\{1,3,2\}\) 不含长度为 \(2\) 的完美序列
3. \(\{2,1,3\}\) 含长度为 \(2\) 的完美序列 \(\{2, 1\}\)，元素和为 \(3\)
4. \(\{2,3,1\}\) 含长度为 \(2\) 的完美序列 \(\{2, 1\}, \{3, 1\}\)，元素和为 \(7\)
5. \(\{3,1,2\}\) 含长度为 \(2\) 的完美序列 \(\{3, 1\}\)，元素和为 \(4\)
6. \(\{3,2,1\}\) 含长度为 \(2\) 的完美序列 \(\{2, 1\}, \{3, 1\}\)，元素和为 \(7\)

   故答案为 \(0+0+3+7+4+7=21\)

先考虑打出 \(f_n\) 表示严格以 \(n\) 开头的完美子序列长度最大值，则有 \(\displaystyle f_n=\max_{d\mid n}f_d+1\)

因此，同上某题也是因数的，用刷表法算出 \(f_n\)

接着，根据定义，\(\{n, (n-1), (n-2), \cdots , 1\}\) 并没有限制开头值，故其完美值为 \(\displaystyle g_n=\max_{i=1}^n f_i\) ，动态刷前缀最大值更新即可

现考虑贡献：设存在某个完美序列 \(v_{1, 2, 3, \cdots, g_n}\)

则元素和为 \(\displaystyle \sum_{i=1}^{g_n} v_i\)，在所有排列中出现的方案数为 \(\displaystyle P(n, n-g_n)={n!\over g_n!}\)，故贡献为 \(\displaystyle (\sum_{i=1}^{g_n} v_i)\cdot {n!\over g_n!}\)

同时，对于另一个完美序列 \(w_{1, 2, 3, \cdots, g_n}\) ，贡献同样为 \(\displaystyle (\sum_{i=1}^{g_n} w_i)\cdot {n!\over g_n!}\) ，且和 \(v\) 的独立

故需求出所有完美序列的所有元素和：\(A_n\) ，则答案为 \(A_n\cdot {n!\over g_n!}\)

现考虑如何求 \(A_n\) ：

先记 \(c_n\) 表示 \(n\) 开头的完美序列个数

刷表求 \(f_n\) 时，考虑由 \(f_d\) 更新 \(f_n\) 的一幕

当 \(f_d+1=f_n\) 时，说明 \(n\) 的后续接 \(d\) 是当前最优的策略之一，故更新 \(\begin{cases}A_n+=A_d+n\times c_d\\c_n+=c_d\end{cases}\)

当 \(f_d+1>f_n\) 时，说明 \(n\) 的后续接 \(d\) 比之前的都更优，故更新 \(f_n=f_d+1\) ，且 \(\begin{cases}A_n=A_d+n\\c_n=c_d\end{cases}\)

同理，后续刷表求 \(g_n\) 时，由于 \(g_n=\max(g_{n-1}, f_n)\)

当 \(g_{n-1}=f_n\) 时，说明以 \(n\) 开始和以某些比 \(n\) 小的数开始都是最优策略，故更新 \(\begin{cases}A_n+=A_{n-1}\\c_n+=c_{n-1}\end{cases}\)

当 \(g_{n-1}>f_n\) 时，说明不以 \(n\) 开始是最优策略，故更新 \(\begin{cases}A_n=A_{n-1}\\c_n=c_{n-1}\end{cases}\)

算法瓶颈在打出 \(A_n\) 与 \(g_n\) 以及阶乘极其逆元，复杂度在于枚举枚举倍数的 \(O(n\log n)\) 和线性扫描的 \(O(n)\)

故总复杂度为 \(O(n\log n+T)\)