202301I HACK IT! 题解

· · 题解

[语言月赛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 即可，剩下的内容可以自由构造。