B3821 题解

· · 题解

这是一道 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 的数量。

如果 $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 字母，即可使代码输出错误。