自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:31，当前版本为作者最后更新于2023-01-05 22:33:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛202301] HACK IT! 题解

Source & Knowledge

2023 年 1 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

你将得到若干个问题和若干个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于每个问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

问题 1

给定两个整数 $a, b$，求出 $a + b$ 的值。

问题 2

给定一个仅包含小写字母的字符串 $s$，求 $s$ 中有多少个小写 a 字母。

问题 3

给定一个长度为 $n$ 的数组 $a$（下标从 $0$ 开始），对所有的 $i$ 满足 $0 \leq i < n$，设 $b_i = a_{i + 1 \bmod n} - a_i$，这里 $i + 1 \bmod n$ 表示 $i + 1$ 对 $n$ 取模的结果。请求出 $b$ 数组。

解析

原题题干中对 hack 题的运作机制做了详细介绍，这里不再赘述。

问题 1

容易发现，原代码使用了 int 变量存储运算结果。当 $a = b = 2 \times 10 ^ 9$ 时，$a + b = 4 \times 10 ^ 9$，超过了 int 类型所能存储的最大范围，符合「输出错误的结果」这一条要求。

故直接输出 2000000000 2000000000 即可。

问题 2

注意到被 hack 的代码中使用了 strlen() 函数。

strlen() 是用于统计 C 风格字符串（char 数组）长度的函数，但是需要注意其时间复杂度为 $O(n)$。

因此，每调用一次 strlen()，其会花费 $O(n)$ 的时间统计一次对应字符串的长度。

我们设字符串长度为 $l$，容易知道我们的循环中会调用 $l$ 次 strlen() 函数，容易发现总复杂度为 $O(l ^ 2)$。在 $l = 10 ^ 6$ 的情况下，这样的操作显然会超时。

因此，我们给出一个长度为 $10 ^ 6$ 的字符串即可。

问题 3

注意到原代码在 for (int i = 0; i < n; ++i) 循环中访问了 a[i + 1]。

容易知道，当 $n = 100, i = 99$ 时，访问 a[i + 1] 会访问 a[100]，访问的下标超过了 0 ~ maxn - 1，产生了数组越界。

因此我们使 $n = 100$ 即可，剩下的内容可以自由构造。