A 苍穹之下 - 字符与字符串读写

给定一个字符串 ，判断是否为 $\texttt{Starry}$，输出对应的字符串。

$40$ 分解法

• 按题意模拟即可。看我多贴心保底都给了 $40$ 分。
• 读入一个字符串，判断这个字符串是否等于 $\texttt{Starry}$，等于则输出 $\texttt{We are off to see the world}$，否则输出 $\texttt{For none believe in miracles}$。

$60$ 分解法

• 与 $40$ 分解法基本相同，需要加一点小小的魔法，作用是加快 cin / cout，不过不建议在完全了解这两句代码的特性之前使用，有时可能会出一些意想不到的问题。
• 输出只有一行，所以也可以去掉浪费大量时间的 endl。
• 说实话我是没想到会因为这个原因挂掉 $20$ 分的，对不起各位。

cin.tie(nullptr);
ios::sync_with_stdio(false);

$80$ 分解法

• 注意到，$|S| \le 10^8$，这已经远超了题目所给 $2$ MB 可以容纳的范围，说明此时已经不可能存得下一个完整的字符串。
• 可以发现，需要匹配的字符串 $\texttt{Starry}$ 只有 $6$ 个字符，那么只需要依次读入并判断前 $6$ 个字符是否相同即可。

$90$ 分解法

• 我不理解大家为啥连骗分都懒得骗。

cout << "For none believe in miracles" << endl;

正解

• 我也没说输入一定只有 $6$ 个字符啊。
• 如果输入完前 $6$ 个字符后都与 $\texttt{Starry}$ 一样，先别急着输出，考虑是否可以再读一个字符。如果可以的话，那么这同样不是合法的。

const string S = "Starry";
char c;

for (int i = 0; i < 6; ++i) {
    cin >> c;
    if (c != s[i]) return cout << "For none believe in miracles" << endl, 0;
} if (cin >> c) return cout << "For none believe in miracles" << endl, 0;
cout << "We are off to see the world" << endl;

B 超链接 - 二维数组的读写与应用

一共有 $N$ 个网页，编号从 $1$ 到 $N$。

第 $i$ 个网页上有 $T_i$ 个超链接（你可以理解为点一下就跳转到另一个页面的按钮），点击第 $j$ 个可以访问到编号为 $A_{i, j}$ 的网页。

从 $1$ 号网站开始，点击不超过两次超链接，求可以访问到的不同的网页的数量。

• 题目要求，点击不超过两次的页面，那么可以分为点击零次、一次、两次三类。

  • 对于第一类，点击零次，也就是我们的出发页面 $1$。
  • 对于第二类，点击一次，也就是页面 $1$ 上超链接指向的所有页面。
  • 对于第三类，点击两次。点击两次的页面，都是可以从点击一次的页面，再经过一次点击到达。
• 题目已经给出，我们应当开一个二维数组存储超链接的信息，第一维 $i$ 表示这是第 $i$ 个页面上的超链接，第二维 $j$ 表示这是页面 $i$ 上的第 $j$ 个超链接。
• 假如我们开了二维数组 $A[][]$ 用于存储超链接，那么 $A[i][j]$ 存储的就是第 $i$ 个页面上的第 $j$ 个超链接指向的页面编号。
• 考虑这样一种做法：每访问到一个之前没访问过的页面，我们就给答案加上 $1$。
• 因为我们从页面 $1$ 开始，所以无论如何都会访问至少一个页面，因此用于统计答案的变量应初始化为 $1$。
• 对于只点击一次就访问到的页面，我们只需要枚举页面 $1$ 指向的页面即可。
• 接下来考虑点击两次到达的页面。
• 可以想到，点击两次到达的页面一定是由访问一次的页面到达的。因此，我们在每次访问点击一次到达的页面时，继续枚举这个页面可以再点击一次到达的页面即可。

int t[1010], a[1010][110], ans = 1;

for (int i = 1; i <= t[1]; ++i) {
    ++ans;
    for (int j = 1; j <= t[a[1][i]]; ++j) ++ans;
}

• 有没有发现什么问题？
• 在点击一次访问的页面中，可能有超链接是指向页面 $1$ 的，此时如果再访问这个页面，就会对页面 $1$ 重复统计。如何避免这样的问题呢？
• 一个很直接的思路是：如果我们已经访问过某个页面，也就是说这个页面已经给答案加过 $1$ 了，那就跳过这个页面，不再统计。
• 因此，我们需要新建一个 bool 数组，存储当前这个页面是否被访问过，被访问过为 true，否则为 false。
• 假设这个数组为 $vis[]$（vis 即 visited，已访问过的缩写），那么 $vis[i]$ 表示这个页面的状态（即是否被访问过）。
• 我们在每次访问到一个新页面时，判断当前页面的 $vis$，如果为 false，那么给答案加 $1$，然后给将这个页面的 $vis$ 修改为 true，表示已访问过。
• 当然，页面 $1$ 无论如何都是会被访问的，因此还需要手动把 $vis[1]$ 设置为 true。
• 此时，代码就呼之欲出了。

int t[1010], a[1010][110], ans = 1;
bool vis[1010];

vis[1] = true;
for (int i = 1; i <= t[1]; ++i) {
    if (!vis[a[1][i]]) ++ans, vis[a[1][i]] = true;
    for (int j = 1; j <= t[a[1][i]]; ++j)
        if (!vis[a[a[1][i][j]]) ++ans, vis[a[a[1][i][j]] = true;
}

C 笨小猴 - 字符与 ASCII

• 这题没上一道题那么抽象，应该不存在读不懂题的问题了吧。

给定一个小写字母组成的字符串，求出现次数最多的字母的出现次数、 出现次数最少的字母的出现次数。

作差，判断是否为质数。

$50$ 分解法

• 注意到，如果这个差值不是质数，那么输出的第一行总是 $\texttt{No Answer}$，第二行总是 $1$，直接骗分输出即可。

正解

• 很显然地，直接统计所有字符出现的次数即可，因此本题的瓶颈在于存储各个字符出现的次数。
• 还记得我们之前学过的 char 的本质吗？ASCII 码，也就是整数，因此 char 变量可以直接作为数组下标使用。理解到这里后，统计字符的出现次数就变得十分简单了。
• 假设我们使用 $cnt[]$ （cnt 即 count，数量的缩写）统计字符的出现数量，那么 $cnt[i]$ 可以表示 ASCII 码为 $i$ 的字符的出现次数。
• 接下来考虑如何统计最大值和最小值。我们可以采用“打擂台”的想法：对于一个值，如果它比当前记录的最大值更大，那么就把最大值更新为当前这个值，最小值亦然。
• 然而，可以发现，如果我们将最小值也初始化为 $0$ 的话，那么就没有比它更小的值了，也就无法更新得到答案了。因此，最小值应该初始化为一个极大值。
• 我们还可以发现，ASCII 码表示的 $128$ 种字符中，只会出现 $26$ 种，如果我们统计到了那些没有出现的字符，最小值会更新为 $0$，也就无法继续更新答案了。因此，我们需要加一个特判，如果出现次数为 $0$，那么就不更新答案。
• 加上我们之前讲过的质数判断即可。

string s;
int cnt[130], maxn, minn = 1e9;

for (int i = 0; i < s.size(); ++i) ++cnt[s[i]];
for (int i = 0; i < 128; ++i) {
    if (cnt[i] > maxn) maxn = cnt[i];
    if (cnt[i] && cnt[i] < minn) minn = cnt[i];
} if (maxn - minn < 2) return cout << "No Answer" << endl << 0 << endl, 0;
for (int i = 2; i * i <= maxn - minn; ++i)
    if ((maxn - minn) % i == 0) return cout << "No Answer" << endl << 0 << endl, 0;
cout << "Lucky Word" << endl << maxn - minn << endl;

更优的正解

• 我们只需要这 $26$ 种字符，那是不是意味着，只要排除掉其他字符的干扰，就可以省去更新最小值时候的特判呢？
• 答案是肯定的。既然 char 本质上也是一种整数，它当然是可以进行运算的。我们知道，$26$ 个小写字母在 ASCII 码中是连续的，由 $a$ 到 $z$ 递增。
• 因此，只需要在计算数组下标的时候，将原本的字符减去字符 ，即可获得范围在 $0$ 到 $25$ 之间的下标。例如，字符 $c$ 减去字符 $a$ 等于 $2$。
• 这样的操作被称为映射。通过上述的映射操作，我们将 $0$ 到 $127$ 的范围压缩到了 $0$ 到 $25$，统计答案的数组可以开得更小，很大程度上减小了空间占用。
• 另外，这里介绍两个新函数：max(a, b) 表示获取 $a$ 和 $b$ 中较大一个的值，min(a, b) 表示获取 $a$ 和 $b$ 中较小一个的值。我们每次获取最大值和某个字符出现次数之间较大的值，并将它重新赋值给最大值，即可完成更新操作；最小值亦然。
• 代码如下。

string s;
int cnt[30], maxn, minn = 1e9;

for (int i = 0; i < s.size(); ++i) ++cnt[s[i] - 'a'];
for (int i = 0; i < 26; ++i) maxn = max(maxn, cnt[i]), minn = min(minn, cnt[i]);
if (maxn - minn < 2) return cout << "No Answer" << endl << 0 << endl, 0;
for (int i = 2; i * i <= maxn - minn; ++i)
    if ((maxn - minn) % i == 0) return cout << "No Answer" << endl << 0 << endl, 0;
cout << "Lucky Word" << endl << maxn - minn << endl;