语言月赛 202408 于抑郁中支持
题目分析
- 给定 $n$ 个整数 $a_i$ 和一个数字 $t$，需要根据每个 $a_i$ 的后 $t$ 位（即 $a_i \bmod 10^t$）区分事件；
- 统计不同事件的数量，也就是不同后缀值的个数。
解题思路
- 由于 $t \leq 4$，后 $t$ 位的最大取值为 $10^t - 1 \leq 9999$，范围较小；
- 因此可以开一个大小为 $10^t$ （建议略大一点，如 $10005$）的布尔数组
vis 来标记每个后缀值是否出现过；
- 定义 $p=10^t$。
- 遍历所有 $a_i$，计算
x = a[i] % p，将 vis[x] 标记为 1；
- 统计
vis 中 1 的数量即为不同事件数。
实现步骤
- 计算 $p = 10^t$，用
pow 函数即可实现；
- 开一个大小为 $10005$ 的布尔数组
vis，全部数组自动初始化都为 0；
- 遍历 $a$ 数组，计算
x = a[i] % p，标记 vis[x] = 1；
- 遍历
vis，统计为 1 的个数并输出。
复杂度分析
- 时间复杂度：$O(n + p)$，$n$ 为输入长度，$p$ 为标记数组大小（最多 10000）；
- 空间复杂度：$O(p)$，布尔数组大小为 $10^t$，符合题目数据范围。
总结
- 充分利用 $t$ 最大为 $4$，导致后缀取值范围有限，适合用数组标记；
- 实现方便且节省内存，适合大数据量输入。