10 · 回顾二：数组与字符串综合

cnt[26]，cnt[s[i] - 'a']++ 数出每个字母的出现次数。

扫一遍 26 个桶，跳过 cnt == 0 的，同时维护 mx 和 mn。

d = mx − mn。d < 2 直接判死；否则试除 2 到 √d，有因子就不是质数。

为什么这么写就对：桶把“谁出现最多”变成一次线性遍历；试除是判质数的标准 O(√d) 做法，d ≤ 100。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;                        // 单词只含小写字母、无空格，cin 一次读完

    int cnt[26] = {0};               // 局部数组必须清零，否则是随机值
    for (int i = 0; i < (int)s.size(); ++i)
        ++cnt[s[i] - 'a'];           // 字母 → 0~25 的下标，桶 +1

    int mx = 0, mn = 1000;           // mn 初值要大于任何可能的出现次数
    for (int i = 0; i < 26; ++i) {
        if (cnt[i] == 0) continue;   // 没出现过的字母不参与 min
        mx = max(mx, cnt[i]);
        mn = min(mn, cnt[i]);
    }

    int d = mx - mn;
    bool prime = (d >= 2);           // 0 和 1 都不是质数，先一刀切死
    for (int i = 2; i * i <= d; ++i) // 试除到 √d 就够
        if (d % i == 0) { prime = false; break; }

    if (prime) cout << "Lucky Word\n" << d << "\n";
    else       cout << "No Answer\n0\n";   // 不是 Lucky Word 时第二行必须是 0
    return 0;
}

a[105][105] 全 0，a[i][j] == 1 表示格子 (i,j) 已经被照亮。

火把：dx、dy 各从 −2 枚举到 2（25 个偏移），|dx| + |dy| > 2 的跳过（正好 12 个），剩下的在界内就置 1。

萤石：同样 25 个偏移，一个都不跳，在界内就置 1。

最后数 a[i][j] == 0 的个数。复杂度 O((m+k)×25 + n²)：最坏 25×25 + 100² ≈ 1.1×10⁴ 次操作，瞬间完成。

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

int a[105][105];                      // 全局数组：默认全 0，不用手动清零

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, x, y;
    cin >> n >> m >> k;

    for (int t = 0; t < m; ++t) {     // 先把 m 个火把全部读完
        cin >> x >> y;
        for (int dx = -2; dx <= 2; ++dx)
            for (int dy = -2; dy <= 2; ++dy) {
                if (abs(dx) + abs(dy) > 2) continue;   // 十字形：这 12 个偏移照不到
                int nx = x + dx, ny = y + dy;
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue;  // 出界的偏移直接丢
                a[nx][ny] = 1;
            }
    }

    for (int t = 0; t < k; ++t) {     // 再读 k 个萤石
        cin >> x >> y;
        for (int dx = -2; dx <= 2; ++dx)
            for (int dy = -2; dy <= 2; ++dy) {
                int nx = x + dx, ny = y + dy;
                if (nx < 1 || nx > n || ny < 1 || ny > n) continue;
                a[nx][ny] = 1;            // 萤石是整块 5×5，不判距离
            }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (a[i][j] == 0) ++ans;      // 还是 0 的格子就是没被照亮
    cout << ans << "\n";
    return 0;
}

从 1 枚举到 n，每拿到一个数就把它复制到临时变量 t。

循环：if (t % 10 == x) ++ans; t /= 10; 直到 t == 0。

因为 t == 0 就停，数字 5 只会拆出 5 这一位，不会凭空多出前导零，x = 0 也自然正确。

总操作数约 n × 位数 ≈ 6×10⁶，一秒内轻松跑完。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;

    long long ans = 0;                  // 答案类变量一律 long long，零成本
    for (int i = 1; i <= n; ++i) {
        int t = i;                      // 复制一份再拆，不要拆坏循环变量
        while (t > 0) {
            if (t % 10 == x) ++ans;     // 末位是不是 x
            t /= 10;                    // 丢掉末位
        }
    }
    cout << ans << "\n";
    return 0;
}

两次 getline 读入单词 w 和文章 s，彻底避开 cin 与换行残留的坑。

逐字符 tolower，两边都变成小写。

枚举起点 i（0 ≤ i ≤ n−m）：若 s[i−1] 是字母，说明 i 落在某个单词中间，跳过；若 s[i+m] 是字母，说明只是某个单词的前缀，也跳过。

通过了边界检查再逐字符比较，全等就 ans++，第一次成功时记下 i。

最后按 ans 是否为 0 分别输出。复杂度 O(n·m)，m ≤ 10 时约 10⁷ 次比较，稳过。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string w, s;
    getline(cin, w);                 // 第一行：单词
    getline(cin, s);                 // 第二行：文章，可能含空格，必须整行读

    for (int i = 0; i < (int)w.size(); ++i) w[i] = tolower(w[i]);   // 统一小写
    for (int i = 0; i < (int)s.size(); ++i) s[i] = tolower(s[i]);

    int n = (int)s.size(), m = (int)w.size();
    int ans = 0, first = -1;         // first = -1 表示还没找到过
    for (int i = 0; i + m <= n; ++i) {
        if (i > 0 && s[i - 1] >= 'a' && s[i - 1] <= 'z') continue;   // 左边还是字母 → 不在词首
        if (i + m < n && s[i + m] >= 'a' && s[i + m] <= 'z') continue; // 右边还是字母 → 只是前缀

        int k = 0;
        while (k < m && s[i + k] == w[k]) ++k;
        if (k == m) {
            ++ans;
            if (first < 0) first = i;    // 只记第一次，后面不再覆盖
        }
    }

    if (ans == 0) cout << -1 << "\n";
    else          cout << ans << " " << first << "\n";
    return 0;
}

key[26] = {1,2,3, 1,2,3, ...}，下标 s[i] - 'a' 直接查表得到按键次数。

getline 读整行；遇到空格 ans += 1；遇到小写字母 ans += key[s[i] - 'a']。

为什么手写表比推公式好：pqrs 和 wxyz 是 4 个一组，前面都是 3 个一组，公式要分情况，表不用。

复杂度 O(n)，n ≤ 200，怎么读都不会慢。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // key[i] = 打完第 i 个小写字母要按几下：a→1, b→2, ... z→4
    int key[26] = {1, 2, 3,  1, 2, 3,  1, 2, 3,  1, 2, 3,  1, 2, 3,
                   1, 2, 3, 4,  1, 2, 3,  1, 2, 3, 4};

    string s;
    getline(cin, s);                 // 含空格，必须整行读

    int ans = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        if (s[i] == ' ') ++ans;      // 空格在 0 键上，按一次
        else if (s[i] >= 'a' && s[i] <= 'z') ans += key[s[i] - 'a'];
    }
    cout << ans << "\n";
    return 0;
}