Hello World 2024 蓝桥杯选拔赛题解

Hello_World

---

T550164 HelloWorld的变迁

给出一个数字 $n$，如果 $n$ 的末尾的值四位大于等于 $2020$，则输出 $1024$，否则输出 HelloWorld。

注意到 $n$ 的最大值为 $987654321012345$，远大于 int 所能表示的上限，所以我们需要使用 long long 来读入数字。

取末尾四位只需要将 $n$ 对 10000 取余数即可。

AC 代码示例

T550165 新的风暴已经出现

给出 $n$ 个数，求出 $n$ 个数两两相乘的总和。

运用乘法分配律可以将等式转换为

$$A_1 \times A2 + (A_1+A_2)\times A_3 +(A_1+A_2+A_3)\times A_4\cdots\cdots$$

所以只需要设置两个变量，$sum$ 表示之前所有数字的和，$ans$ 表示当前计算的答案，累加之后即可。

注意答案会超过 $2\times10^9$ 的 int 上限，需要使用 long long。

AC 代码示例

T550173 水群高手小hi

数字位数少于 $len(n)$ 的数必然小于 $n$，此时的答案一共有 $9(len(n)-1)+1$ 个，位数等于 $len(n)$ 时，至少有 $x-1$ 个自然数满足答案，其中 $x$ 为 $n$ 的最高位，最后特判 $len(n)$ 位 $x$ 是否满足题意即可。

AC 代码示例

T550171 简单的题目

序列满足如下递推式：

$$a_{n+1}= \begin{cases} \frac{a_n}{2} & \text{if}~a_n \equiv0~(\mathrm{mod}~2)\\ 3a_n+1 & \text{if}~a_n\equiv 1~(\mathrm{mod}~2) \end{cases}$$

输入 $a_0$ 与 $n$，输出 $a_n$。

50% 分数解法

按题目描述正确计算即可，不会爆 int，轻松拿下 50%，核心代码如下：

for (int i = 1; i <= n; ++i) {
    if (a % 2 == 0) {
        a /= 2;
    } else {
        a = a * 3 + 1;
    }
}

100% 分数解法

通过手推可以发现，似乎最终总是会回到 $1\to4\to2\to1$ 的循环上，可以手写代码从 $1$ 到 $10^5$ 验证都能满足这个规律，所以可以先跑 $n$ 次，如果 $n$ 次跑完还没有到 $1$，就使用 $n$ 次后 $a$ 的值，如果在 $n$ 次内先到达了 $1$，就计算 $n$ 与当前次数的差值，对周期 $3$ 取余可以快速得到结果（你是否在找：考拉兹猜想，冰雹猜想）。

注意 $a_0=0$ 时永远为 $0$。

AC 代码示例

数据生成

点击链接查看随机数据生成代码，其中 std.exe 为标程 exe 文件。

T550172 lhx牌碰碰车

给出 $N$ 个数，现在要将 $N$ 个数划分成两个集合，目标是让两个集合的和的最大值最小，输出大的集合的总和。

经典的动态规划问题。

开一个数组 f[i]，f[i] 为 $1$ 时表示总和为 $i$ 的集合存在。我们考虑新放入一个数 $k$，当前所有的方案都能将这个数加入，如果大小为 $i$ 的方案存在，那么加入这个数之后大小为 $i+k$ 的方案也存在。同时还可以不使用这个数，所以原先的方案同样存在，将两种情况合并即为最终答案。

将所有数加入之后，找到总和离 $\frac{sum}{2}$ 最近的 f[i] 即为答案。

AC 代码示例

T550170 数学天才再临

题意：在 $[1,m]$ 的范围内等概率地取 $n$ 个正整数，求 $n$ 个正整数两两互质的方案数。

（比赛无聊的时候，看了题面里链接的视频了吗，非常有意思，强烈推荐！）

$m=1$ 解法

当 $m=1$ 时只有一种填法：每一位都填 $1$，必然满足两两互质，因此直接输出 $1$ 可以得到 $m=1$ 的分数。

$m=2$ 解法

当 $m=2$ 时，其中一种填法是所有位都填 $1$，另一种是从 $n$ 位中选择一个填 $2$（共 $n$ 个可选位置），因此当 $m=2$ 时可以直接输出 $n+1$。

$n=2$ 解法

$n=2$ 时两个 for 循环 $O(n^2)$ 从 $1$ 到 $m$ 枚举两个数字，当最大公约数为 $1$ 时加到答案上，核心代码如下：

int gcd(int a, int b) {
    return b == 0? a: gcd(b, a % b);
}
for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (gcd(i, j) == 1) {
            ++ans;
        }
    }
}

$3\leq n\leq5$ 解法

从 $1$ 到 $n$ 每一位都枚举 $1$ 到 $m$，枚举到第 $i$ 个数字时判断是否与前 $i-1$ 个数字都互质，若都互质则填入，继续枚举第 $i+1$ 个数字。

由于循环层数 $n$ 非固定值，可用递归实现暴力搜索，不会写递归可以通过对 $n$ 值的特判写几个分支，分别对应不同层数的 for 循环，时间复杂度 $O(m^n)$，核心代码如下：

int gcd(int a, int b) {
    return b == 0? a: gcd(b, a % b);
}
void dfs(int depth) {
    if (depth == n + 1) {
        ++ans;
        return ;
    }
    for (int i = 1; i <= m; ++i) {
        bool flag = true;
        for (int j = 1; j < depth; ++j) {
            if (gcd(i, num[j]) != 1) {
                flag = false;
                break;
            }
        }
        if (flag) {
            num[depth] = i;
            dfs(depth + 1);
        }
    }
}

$n\in[3,1000],~m\in[1,30]$ 解法

换一种角度考虑”互质“：一个整数可以分解成多个质因数幂次相乘的形式，当两个整数的质因数没有交集时，这两个数字互质。

用二进制位表示质因数集合，第 $0$ 位为 $1$ 表示包含第 $1$ 个质数 $2$，第 $1$ 位为 $1$ 表示包含第二个质数 $3$，以此类推。

定义状态 $dp(i,j)$ 表示前 $i$ 个已填数字的质因数集合的二进制表示为 $j$，有如下递推式：

$$dp(i,j)=\sum_{k=1}^mdp(i-1,j~\text{xor}~bit(k))\quad (bit(k)~\text{and}~j=bit(k))$$

其中，$\text{xor}$ 表示按位异或，$\text{and}$ 表示按位与， $bit(k)$ 表示整数 $k$ 的质因数集合的二进制位表示，如 $bit(20)=bit(2^2\times5)=(101)_{2}=(5)_{10}$，上式在 $k$ 的质因数集合为 $j$ 所代表集合的子集时（即满足条件 $bit(k)~\text{and}~j=bit(k)$）可以转移。

递推式含义为：前 $i$ 位质因数状态为 $j$ 的方案数，等于往第 $i$ 位填数字 $k~(k\in[1,m])$ 的方案数总和，当第 $i$ 位填入 $k$ 时，前 $i-1$ 位的质因数状态只能为 $j~\text{xor}~bit(k)$ 才能保证前 $i$ 位整数两两互质。初始值为 $dp(0,0)=1$，答案为 $\sum_{j=0}^{2^{cnt}-1} dp(n,j)$，$cnt$ 为小于等于 $m$ 的质数个数。

时间复杂度：递推式时间复杂度为 $O(nm\times2^{\frac{m}{\ln m}})$，$30$ 以内有 $10$ 个质数，最坏情况下计算次数为 $1000\times30\times2^{10}\approx3\times10^7$，可以通过这部分数据，$m=60$ 时最坏情况计算次数为 $1000\times60\times2^{17}\approx7.8\times10^9$，超过 $10^8$ 会导致超时。

点击链接获取对应代码。

满分解法

继续观察发现，当我们找到一组不等于 $1$ 的由 $i$ 个数字组成的互质组合时（如 $3, 7, 10$），我们有 $\text{C}_n^i$ 种方式把它放到一个长度为 $n$ 的数组，其他 $n-i$ 位可以全填 $1$，发现这里面的方案数计算时间复杂度与 $n$ 无关（$\text{C}_n^i$ 可以 $O(n^2)$ 预处理，$O(1)$ 读取）。

因此我们可以定义状态 $dp(i,j)$ 表示由 $i$ 个不包含 $1$ 的已填数字的质因数集合的二进制表示为 $j$，有如下递推式：

$$dp(i,j)=\sum_{k=2}^mdp(i-1,j~\text{xor}~bit(k))\quad (bit(k)~\text{and}~j=bit(k))$$

递推式与上一种解法类似，但 $k$ 从 $2$ 开始，且 $i$ 最大为 $\min(cnt, n)$，最终答案等于：

$$ans=\sum_{i=0}^{\min(cnt, n)}\sum_{j=0}^{2^{cnt}-1}dp(i,j)\times C_n^i$$

其中 $cnt$ 为小于等于 $m$ 的质数的个数，表示最多只需要 $cnt$ 位就能枚举尽所有方案，初始状态 $dp(0,0)=1$。

时间复杂度：$O(\frac{m}{\ln m}\times2^{\frac{m}{\ln m}}\times m+n^2)$，其中 $n^2$ 为预处理 $C_n^k$ 的时间复杂度，当 $n=1000,~m=60$ 时，最多需要执行 $17\times2^{17}\times60\approx1.8\times10^8$，加上一些小优化（见代码）可通过本题 100% 数据。

AC 代码示例

附加题

1. 若 $n=2,~m=100000$，如何求解？（提示：欧拉函数）
2. 若 $n=1000,~m=100$，如何求解？（提示：质数的性质）

数据生成

点击链接获取随机数据生成代码，其中 std.exe 为标程 exe 文件。