2022年长春理工大学蓝桥杯校选赛题解

A.算数

计算机基础知识 & 小学数学题

一个 $intint$ 变量 $4B4B$ ，$1MB=1024KB1MB=1024KB$，$1KB=1024B1KB=1024B$

$512MB512MB$ 能创建 $512\ast 1024\ast 1024\mathrm{/}4=134217728512*1024*1024/4=134217728$ 个 $intint$ 变量

Answer：134217728

B.龙神的工资

高中数学&组合数学-插板法

题目可以抽象为 $nn$ 个相同的小球，放进 $mm$ 个不同的箱子，箱子允许为空，答案即为 $C_{n+m-1}^{m-1}C\_\{n+m-1\}^\{m-1\}$

答案对 $10^9+910^9+9$ 取模。

Answer：863690645

C.龙神的口头禅

高中/大学数学&容斥原理&组合数

设命题 $AA$ 为字母 $ll$ 至少出现一次的方案数，命题 $BB$ 为 字母 $zz$ 至少出现一次的方案数，命题 $CC$ 为 字母 $qq$ 至少出现一次的方案数，命题 $DD$ 为字母 $nn$ 至少出现一次的方案数。那么所求答案就抽象成就 $A\cap B\cap C\cap DA\; \backslash cap\; B\; \backslash cap\; C\; \backslash cap\; D$。正面计算很复杂，利用容斥原理可得

$A\cap B\cap C\cap D=\bar{A}\cup \bar{B}\cup \bar{C}\cup \bar{D}-(\bar{A}\cup \bar{B}\cup \bar{C}+\bar{A}\cup \bar{B}\cup \bar{D}+\bar{A}\cup \bar{C}\cup \bar{D}+\bar{B}\cup \bar{C}\cup \bar{D})+(\bar{A}\cup \bar{B}+\bar{A}\cup \bar{C}+\bar{A}\cup \bar{D}+\bar{B}\cup \bar{C}+\bar{B}\cup \bar{D}+\bar{C}\cup \bar{D})-(\bar{A}+\bar{B}+\bar{C}+\bar{D})A\backslash cap\; B\backslash cap\; C\backslash cap\; D=\backslash bar\{A\}\backslash cup\backslash bar\{B\}\backslash cup\backslash bar\{C\}\backslash cup\backslash bar\{D\}-(\backslash bar\{A\}\backslash cup\backslash bar\{B\}\backslash cup\backslash bar\{C\}+\backslash bar\{A\}\backslash cup\backslash bar\{B\}\backslash cup\backslash bar\{D\}+\backslash bar\{A\}\backslash cup\backslash bar\{C\}\backslash cup\backslash bar\{D\}+\backslash bar\{B\}\backslash cup\backslash bar\{C\}\backslash cup\backslash bar\{D\})+(\backslash bar\{A\}\backslash cup\backslash bar\{B\}+\backslash bar\{A\}\backslash cup\backslash bar\{C\}+\backslash bar\{A\}\backslash cup\backslash bar\{D\}+\backslash bar\{B\}\backslash cup\backslash bar\{C\}+\backslash bar\{B\}\backslash cup\backslash bar\{D\}+\backslash bar\{C\}\backslash cup\backslash bar\{D\}\; )-(\backslash bar\{A\}+\backslash bar\{B\}+\backslash bar\{C\}+\backslash bar\{D\})$

由于$A\mathrm{、}B\mathrm{、}C\mathrm{、}DA、B、C、D$方法数一致，所以上式可以简化为 $A\cap B\cap C\cap D=C_4^4\times (\bar{A}\cup \bar{B}\cup \bar{C}\cup \bar{D})-C_4^3\times (\bar{A}\cup \bar{B}\cup \bar{C})+C_4^2\times (\bar{A}\cup \bar{B})-C_4^1\times (\bar{A})A\backslash cap\; B\backslash cap\; C\backslash cap\; D=C\_4^4\; \backslash times\; (\backslash bar\{A\}\backslash cup\backslash bar\{B\}\backslash cup\backslash bar\{C\}\backslash cup\backslash bar\{D\})-C\_4^3\backslash times(\backslash bar\{A\}\backslash cup\backslash bar\{B\}\backslash cup\backslash bar\{C\})+C\_4^2\backslash times(\backslash bar\{A\}\backslash cup\backslash bar\{B\})-C\_4^1\; \backslash times(\backslash bar\{A\})$

如果实在想不到，也可以使用 dfs ，搜索结果，大概需要 $11$ 分钟左右出结果。

Answer：14676024

D.好客龙神

大学编程课内题&求约数个数

对于每个数 $xx$ ，使用朴素算法 $O(x)O(x)$ 的求约数个数，大概要跑 $22$ 年。

对于每个数 $xx$，使用略加优化的算法 $O(\sqrt{x})O(\backslash sqrt\{x\})$ 的求约数个数，大概要跑 $22$ 分钟。

对于每个数 $xx$ ，使用 Eratosthenes 筛法 $O(nlog(n))O(nlog(n))$ 的求约数个数，大概要跑 $22$ 毫秒

对于每个数 $xx$ ，使用 线性筛法 $O(n)O(n)$ 的求约数个数，大概要跑 $0.20.2$ 毫秒

之后从 $11$ 枚举到 $2021120720211207$ 比较每个数的约数个数和之前的约数个数最大值，若当前的约数个数大于等于之前的约数个数，则答案+1

Answer：135

E.龙神的时钟魔法

模拟&数学:

钟表上秒针一秒钟转$6\mathrm{°}6°$，时针一小时转$30\mathrm{°}30°$，即时针一秒钟转$\frac{1}{120}\mathrm{°}\backslash frac\{1\}\{120\}°$，一天$8640086400$秒，直接模拟时针秒针何时夹角$\alpha \le 30\mathrm{°}\backslash alpha\; \backslash leq\; 30°$即可。可能会卡精度，可以将角度同时乘$120120$倍即可没有浮点数运算。

Answer：14402

F.这真的是一道很简单很简单的题

输出输出&加减乘除运算

对于 $30\mathrm{\%}30\backslash \%$ 的做法，直接读入两个 $intint$ 类型的 $x,px,p$，输出 $x\mathrm{\%}px\; \backslash \%\; p$即可

对于 $100\mathrm{\%}100\backslash \%$ 的做法

$PythonPython$ 可直接输出 $x\mathrm{\%}px\; \backslash \%\; p$

$JavaJava$ 可使用大整数类，读入 $x,px,p$ 再输出 $x\mathrm{\%}px\; \backslash \%\; p$

$C++C++$ ：对于一个数 $1432414324$, 可以分解为 $((((((0\ast 10)+1)\ast 10)+4)\ast 10+3)\ast 10+2)\ast 10+4((((((0*10)+1)*10)+4)*10+3)*10+2)*10+4$，那么，对于 $xx$ ，以字符串的形式读入，对于每一位迭代处理，取模即可，需要注意一下 $longlonglong\; long$ 溢出。

G.Super赛亚人

排序&前缀和

要想怒气值最快到达 $kk$ 那么一定优先选大数，对给定的 $nn$ 个数排序，从大到小进行累加，如果累加和大于 $kk$ 则输出累加的个数，若 $nn$ 个数都累加了还没有达到 $kk$ ，那么则输出 $-1-1$ 。

对于 $40\mathrm{\%}40\backslash \%$ 的做法，可以使用 $O(n^2)O(n^2)$ 的排序算法进行排序。

对于$100\mathrm{\%}100\backslash \%$ 的做法，可以使用 $O(nlog(n))O(nlog(n))$ 的排序算法进行排序。

H.龙神的竖锯解构

数据结构&线段树

对于 $40\mathrm{\%}40\backslash \%$ 的做法，模拟题目中的操作，加减乘除运算，累和输出即可。

对于 $100\mathrm{\%}100\backslash \%$ 的做法，已知每个数 $a_{i}a\_i$ 小于等于 $10^{9}10^9$ 那么对于 $a_{i}a\_i$ 进行除法操作，最多不超过 $3030$ 次就可以把 $a_{i}a\_i$ 变成 $00$ ，考虑线段树维护区间最大值以及区间和，若当前区间最大值为 $00$ ，那么则不对当前区间进行更新，否则对每个待修改值进行单点更新，时间复杂度 $O(30\ast nlog(n))O(30*nlog(n))$。

I.龙神的口头禅集合

动态规划&计数问题

**对于$30\mathrm{\%}30\backslash \%$的测试点：**因为 $nn$ 小于 $1010$，所以可以枚举所有子序列，一共是 $2^{n}2^n$ 个子序列，复杂度 $O(2^n)O(2^n)$

**对于$70\mathrm{\%}70\backslash \%$的测试点：**考虑动态规划，用 $dp[i]dp[i]$ 表示以 $ii$为结尾位置的所有子序列，考虑如何去重，设该字符上次出现位置为 $qq$，那么 $qq$ 前面的所有子序列都以 $qq$ 结尾过一次，所以 $qq$ 前面的字符串无法以 $ii$ 结尾。所以转移方程$dp[i]={\sum }_{x=p}^{i}dp[x]dp[i]=\backslash sum\_\{x=p\}^\{i\}dp[x]$，如果 $ii$ 位置的字符是首次出现，$dp[i]=dp[i]+1dp[i]=dp[i]+1$，复杂度$O(n^2)O(n^2)$

**对于$100\mathrm{\%}100\backslash \%$的测试点：**考虑优化动态规划，我们发现每个点的 $dpdp$ 转移，都是对于一段区间求和，所以我们可以使用前缀和来优化，只需要记录每个字符首次出现的位置即可。复杂度 $O(n)O(n)$。也可以从后往前考虑，设 $allall$ 为到当前字符之前，所有本质不同的子序列数量，设 $cn{t}_{x}cnt\_x$ 为到当前字符之前，以 $xx$ 开始的的子序列个数，那么以当前字符 $chch$ 开始的子序列数量为 $all-cnt[ch]+1all-cnt[ch]+1$，每次更新 $all,cnt[ch]all,cnt[ch]$，时间复杂度为$O(n)O(n)$

J.祖龙传说

树&数据结构&倍增&差分&前缀和&dfs相关

给出各边的关系，以 $11$ 为根节点，建一棵有根树。

对于 $40\mathrm{\%}40\backslash \%$ 的做法，对每个点 $xx$ 向上暴力跳 $kk$ 个父节点同时进行单点修改，到 $11$ 节点仍不满 $kk$ 个节点，则终止跳跃。

对于$10\mathrm{\%}10\backslash \%$ 链的做法，维护差分数组，最后求前缀和输出即可。

对于 $10\mathrm{\%}10\backslash \%$ 菊花图的做法，因为对于每个节点，祖先数目小于等于1，所以最朴素的做法可过。

对于 $100\mathrm{\%}100\backslash \%$ 的做法，倍增求每个点 $xx$ 的 $kk$ 级祖先是哪一个点，若 $kk$ 级祖先超过 $11$ 则将祖先设置为 $11$，树上点差分，对于差分数组 $nu{m}_{fa[x]}+=c,nu{m}_{fa[fa[x][k]][0]}-=cnum\_\{fa[x]\}\; +=\; c,num\_\{fa[fa[x][k]][0]\}-=c$，对树进行 $dfsdfs$ 求子树和输出即可，时间复杂度 $O(nlog(n))O(nlog(n))$。