本文主要是介绍第十二届蓝桥杯大赛软件赛省赛第二场 C/C++ 大学 A 组 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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}\) 的限制，根本拉不到那么大

这篇关于第十二届蓝桥杯大赛软件赛省赛第二场 C/C++ 大学 A 组 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！