洛谷B3704 [语言月赛202301] HACK IT! 题解
题目链接:B3704 [语言月赛202301] HACK IT!
题意:
本题是提交答案题。
给你三道题和三个错误的程序,请你构造数据 hack 掉他们。
问题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\) ,请求出 \(b\) 数组。
代码1:
#include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; cout << a + b << endl; }
代码2:
#include <cstring> #include <iostream> using namespace std; char s[1000005]; int main() { cin >> s; int ans = 0; for (int i = 0; i < strlen(s); ++i) { if (s[i] == 'a') ++ans; } cout << ans << endl; return 0; }
代码3:
#include <iostream> using namespace std; const int maxn = 100; int a[maxn], b[maxn]; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) { b[i] = a[i + 1] - a[i]; if (i + 1 == n) b[i] = a[0] - a[i]; } for (int i = 0; i < n; ++i) { cout << b[i] << " \n"[i == (n - 1)]; } }
输入格式:
给定 Task 的 id,只有 1,2,3 三种取值。
输出格式:
你给出的数据必须满足如下要求:
- 不能有多余的输入,但是可以有行末空格和文末回车。
- 对于问题1,\(1 \leq a, b \leq 2 \times 10^9\)。
- 对于问题2,\(s\) 只含小写英文字母,\(s\) 的长度应 \(\geq 1\) 且不超过 \(10 ^ 6\)。
- 对于问题3,\(1 \leq n \leq 100\),\(-10^9 \leq a_i \leq 10^9\)。
判分说明:
本题共三个测试点,分别对应三个问题,每个测试点 10 分。
数据判定
你给出的数据必须完全符合『数据规模要求』,否则将得到 unaccepted 的结果。
超时判定
程序每执行若干条指令,我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量,也即每执行 \(O(1)\) 条指令会进行一次检测。且两次检测之间的指令条数不会太多,一般不超过 \(100\) 条 C++ 语句。
如果程序的运行时间超过 \(500 \text{ms}\),则判定为程序运行超时,返回 accepted 结果。
结果错误判定
如果程序在规定的时间内结束且给出了一个输出,我们会比较这个输出和完全正确的输出,如果二者不同,则判定为 hack 成功,返回 accepted 结果。
未定义行为判定
我们会在每次显式的调用数组元素前判断数组下标是否超过数组范围,如果超过,则判定为 hack 成功,返回 accepted 结果。
这就是说,如果你希望通过未定义行为进行 hack,只能对显式的调用数组元素的行为进行 hack。
第一问的代码在 \(a + b \ge 2147483647\) 时会溢出,构造两个 \(2\times 10^9\) 的数即可。
第二问的代码使用了 strlen(s)
函数,这个函数的原理是从
*s
开始遍历,遍历到 \0
为止。
而每次循环判断时都会调用这个函数,总复杂度为 \(\mathcal{O}(n^2)\) ,构造 \(10^6\) 长的字符串即可。
第三问的代码会访问到 \(n+1\) 的位置,当 \(n=100\) 时属于未定义行为,构造 \(n=100\) 的情况即可。
时间复杂度 \(\mathcal{O}(1)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int _; cin >> _;
if(_ == 1) cout << "2000000000 2000000000\n";
if(_ == 2) { rep(i, 1, 1000000) cout << 'a'; cout << '\n'; }
if(_ == 3) { cout << "100\n"; rep(i, 1, 100) cout << "1000000000\n"; }
return 0;
}