自动搬运

查看原文

来自洛谷，原作者为

	Brain_Huger florr zorr 玩家 ｜ 不活跃 ｜ P+O2=POO

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

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

以下是正文

这是一道 Hack 题，我们先来看看第一问：

给定 $n$ 个元素，标号为 $1, 2, \cdots, n$，你需要标记其中 $k$ 个元素。如果两个元素标号相差 $1$ 则称二者相邻。

请计算出「自身未被标记且有至少一个相邻元素被标记」的元素的可能的最小数量和可能的最大数量。

$1\le n\le 10^{9},0\le k\le n$

Hack 代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
	if (k == n || k == 0) {
		cout << "0 0" << endl;
		return 0;
	}
	cout << "1 ";
	if (k * 3 <= n)
        cout << 2 * k << endl;
	else
        cout << n - k << endl;
	return 0;
}

不难发现，$k$ 和 $n$ 都是用 int 存储的，但是if (k * 3 <= n)这里将 $k$ 乘上了 $3$，会爆 int，所以我们把 $n$ 取最大值，$k$ 取比 $n$ 小的最大值（注意这里 $k$ 不能取最大值，要不然 $n$ 就和 $k$ 相等了，第一个 if 判断就会判掉，不会爆 int）。

接着来看第二问：

给定一个仅包含小写字母 a、b、c 的字符串，判断这个字符串是否符合以下所有特征：

1. 字符串中至少有一个 a 字母和一个 b 字母，且所有的 a 在 b 之前。

2. 如果字符串中有 c，所有的 a 在 b、c 之前，所有的 b 在 c 之前。

3. c 的数量等于 a 的数量或 b 的数量。

$1 \leq \left | S \right | \leq 5000$（$\left | S \right |$ 代表字符串 $S$ 的长度），$S$ 中仅包含小写字母 a, b, c。

如果 $S$ 符合要求，则输出 YES，否则输出 NO。

Hack 代码：

#include <bits/stdc++.h>
using namespace std;

char str[5005];
int i, n, A, B, C;

int main() {
	cin >> str;
	n = strlen(str);
	if (str[0] != 'a') {
		cout << "NO" << endl;
		return 0;
	}
	for (i = 0; i < n; ++i) 
        if (str[i] != 'a') break;
	A = i;
	for (; i < n; ++i)
		if (str[i] != 'b') break;
	if (i == n || str[i] != 'c') {
		cout << "NO" << endl;
		return 0;
	}
	B = i - A;
	for (; i < n; ++i)
		if (str[i] != 'c') break;
	if (i != n) {
		cout << "NO" << endl;
		return 0;
	}
	C = n - B - A;
	if (C != A && C != B) 
        cout << "NO" << endl;
	else 
        cout << "YES" << endl;
	return 0;
}

很好发现，这个代码并没有判断字符串特征的这个条件：

至少有一个 a 字母和一个 b 字母。

我们只需满足字符串的其他特征，并且没有 b 字母，即可使代码输出错误。