第五章数组¶

基础数学知识¶

因数、倍数与质数：理解谁能整除谁，知道 1 不是质数、2 是最小的质数。对应 2036、2040、1109。
完全平方数与因数配对：\(1,4,9,16,\ldots\) 是完全平方数；因数通常成对出现，完全平方数的平方根对应同一对中的两个相同因数。对应 2036 的规律解法。
用字母与下标表示一组数：读懂 \(a_i\) 表示第\(i\)项，\(a_{i,j}\) 表示第\(i\)行第\(j\)列；数学下标与 C++ 数组下标按各题约定对应。贯穿一维、二维数组题。
求和符号与对应项乘积：\(\sum_{i=1}^{n}x_i\) 就是把第 1 项到第\(n\)项依次相加；\(\sum a_i b_i\) 是对应位置相乘后再相加。对应 1104、1108、1125，先会展开，不用急着背符号。
百分数与比例：会用“部分数量除以总数量”求比例，再乘 \(100\%\) 写成百分数。对应 1106、1123、1131，注意各题要求输出比例、百分数值，还是带百分号的结果。
平均值、偏差与绝对值：会在去掉两个样本后重新计算平均值，并用 \(|x_i-\bar x|\) 表示与平均值的距离。对应 1114；绝对值不是把差直接原样输出。
余数与循环编号：理解编号走到末尾后回到开头，余数可以把结果限制在 \(0\) 到 \(n-1\)。对应 2037、1133、1136、1137。
坐标、闭区间与边界：理解 \((x,y)\) 的位置含义，以及 \(a\le x\le b\) 包含左右两个端点。对应 1107、1118；矩阵题的行列编号不等于平面坐标系的横纵轴方向。
矩阵及其基本运算：把矩阵理解为按行列排好的数表，学习对应位置相加、行列互换，以及“一行对一列”的乘法规则。对应 2041、2042、1119、1121～1128。
对角线的下标关系：理解同行列差不变、反向斜线行列和不变，例如 \(i-j=x-y\)、\(i+j=x+y\)。对应 2041、1120。
递推与杨辉三角：由前面已知的数计算后面的数，中间项满足 \(a_{i,j}=a_{i-1,j-1}+a_{i-1,j}\)。对应 2043，不需要先学组合数公式。

第一节一维数组¶

2034：【例5.1】反序输出 ¶

提示 1：先记住读了几个数

输入4 8 2，倒着输出时应该先取哪个下标？

数组a已定义，从下标0存放；让n从0开始，每读到一个数就存入：

int n = 0, x;
while (cin >> x) a[n++] = x;

提示 2：从最后一个有效位置往回走

读完三个数时n是3，但最后一个下标是2。

for (int i = n - 1; i >= 0; i--) cout << a[i] << ' ';

用只有一个数的输入走一遍，检查循环会执行几次。

知识补充：读到输入结束

while (cin >> x) 会持续读取，直到输入结束或读取失败。

a[n++] = x 先把数放到下标 n，再让 n 加一。

回车只是换行，不代表输入结束。

输入完最后一个数，先按回车到新行。

Windows：按 Ctrl+Z，再按回车。

macOS：按 Control+D。

常见错误

别把第一个数当成个数，也别把零当结束标记。

读取失败时，不应再增加有效数据个数。

自测

输入：1 7 3 4 5 → 预期输出：5 4 3 7 1

输入：0 -2 9 → 预期输出：9 -2 0

自己试试：自己造一组数，先在纸上写出反序结果。

只在这组数的中间插入一个零，输出中应该多出什么？

参考代码

#include <bits/stdc++.h>

using namespace std;

int a[110];

int main() {
    int n = 0, x;
    while (cin >> x) a[n++] = x;

    for (int i = n - 1; i >= 0; i--) cout << a[i] << ' ';

    return 0;
}

2035：【例5.2】平移数据 ¶

提示 1：先排输出顺序

把1 2 3 4左移一位，先写出结果。

这里数组从下标1存放，先输出下标2到n，最后该补谁？

提示 2：先不急着搬数组

for (int i = 2; i <= n; i++) cout << a[i] << ' ';

接着补上原来第一个数，就能得到左移结果。

如果真的移动数组，先保存a[1]，否则它会被覆盖。

常见错误

向左移动时，从前向后补位，避免覆盖还没搬走的数据。

只有一个数时，结果不变。

自测

输入：4 1 2 3 4 → 预期输出：2 3 4 1

输入：1 9 → 预期输出：9

自己试试：自己造一组互不相同的数，先写出左移一位的结果。

只把第一个数换掉，输出中的哪个位置应该改变？

方法一：调整输出顺序

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 2; i <= n; i++) cout << a[i] << ' ';
    cout << a[1];

    return 0;
}

方法二：实际移动数组

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int t = a[1];
    for (int i = 1; i < n; i++) a[i] = a[i + 1];
    a[n] = t;

    for (int i = 1; i <= n; i++) cout << a[i] << ' ';

    return 0;
}

2036：【例5.3】开关门 ¶

提示 1：跟着第三位服务员走

只画6扇门，第三位服务员要操作哪几扇？

门号是3、6，下一扇总比前一扇多3。

提示 2：把一次反转写出来

全局bool door[]已定义，先用false对应关门。

door[j] = !door[j];

把它放进for (int j = i; j <= n; j += i)，就模拟了第i位服务员。

外面还需要哪一层循环，才能让所有服务员依次操作？

知识补充：状态与初始化

全局 bool 数组默认是 false，这里让它对应初始的“关”。

! 会把真假反过来，也就对应一次开关操作。

知识补充：完全平方数规律（拓展）

第\(k\)扇门的操作次数，等于\(k\)的正因数个数。

因数通常成对出现，偶数次反转后仍然关着。

完全平方数的平方根只算一个因数，因此总数为奇数。

例如 9 的因数是 1、3、9，反转三次后打开。

常见错误

这里是切换状态，不是每次都开门。

两层循环中，一个表示服务员，一个表示门。

自测

输入：10 → 预期输出：1 4 9

输入：1 → 预期输出：1

方法一：模拟开关

#include <bits/stdc++.h>

using namespace std;

bool door[1010]; // false代表关

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)
            door[j] = !door[j];

    for (int i = 1; i <= n; i++)
        if (door[i]) cout << i << ' ';

    return 0;
}

方法二：完全平方数规律（拓展）

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {
    cin >> n;

    for (int i = 1; i * i <= n; i++) cout << i * i << ' ';

    return 0;
}

2037：【例5.4】约瑟夫问题 ¶

提示 1：把圆圈变成队伍

先用4个人、报到3出局手算一轮。

没出局的人挪到队尾，队头换人，这样能不能接着绕圈？

提示 2：每次只处理队头一人

队列q中已按顺序放好1到n，报数计数k从0开始。

int t = q.front();
q.pop();
k++;

取走队头不等于让他出局：没报到m，还要q.push(t)。

提示 3：出局后从哪里继续

报到m时输出t，并把k清零，不再放回队列。

while (!q.empty()) {
    // 取队头、报数，再决定出局还是回队尾
}

把两个分支补进去，再用m = 1检查是否人人依次出局。

知识补充：队列的操作

queue<int> q 定义整数队列。

q.push(x) 放入队尾，q.front() 查看队头，q.pop() 移除队头。

q.empty() 判断是否为空；非空时才能取队头。

常见错误

出局的人不能重新入队。

输出人的编号，不是报数；m 为 1 时也要能结束。

自测

输入：8 5 → 预期输出：5 2 8 7 1 4 6 3

输入：4 1 → 预期输出：1 2 3 4

方法一：队列模拟

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);

    int k = 0;
    while (!q.empty()) {
        k++;

        int t = q.front(); q.pop();

        if (k == m) {
            k = 0;
            printf("%d ", t);
            continue;
        }

        q.push(t);
    }

    return 0;
}

方法二：数组标记

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

bool vis[N];
int n, m;
int cnt;
vector<int> ans;

int main() {
    cin >> n >> m;

    int i = 0;
    while (cnt < n) {
        int num = 0;
        while (num < m - 1) {
            while (vis[i]) i = (i + 1) % n;
            num++;
            i = (i + 1) % n;
        }

        while (vis[i]) i = (i + 1) % n;
        ans.push_back(i + 1);
        vis[i] = true;
        cnt++;
        i = (i + 1) % n;
    }

    for (auto x : ans) cout << x << ' ';

    return 0;
}

方法三：数组删除与补位

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) a[i] = i + 1;

    int j = 0;
    while (n) {
        j = (j + m - 1) % n;
        printf("%d ", a[j]);
        for (int i = j + 1; i < n; i++) a[i - 1] = a[i];
        n--;
    }

    return 0;
}

方法四：双向链表（拓展）

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m;
int l[N], r[N];

void remove(int k) {
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        r[i] = (i + 1) % n;
        l[i] = (i - 1 + n) % n;
    }

    int k = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) k = r[k];
        printf("%d ", k + 1);
        remove(k);
        k = r[k]; //下一个人
    }

    return 0;
}

2038：【例5.5】最大数位置 ¶

提示 1：留下数，也留下位置

对3 9 9 2，题目要输出2还是3？

先让第一个数当擂主，位置记作1。

提示 2：什么时候换擂主

已读到第i个数x，当前最大值是maxn：

if (x > maxn) {
    maxn = x;
    pos = i;
}

把>换成>=，并列时留下的位置会怎样变化？

常见错误

> 保留第一个最大值，>= 会保留最后一个。

不要用零初始化最大值，否则全负数时可能出错。

自测

输入：5 3 9 9 2 1 → 预期输出：2

输入：3 -8 -2 -5 → 预期输出：2

自己试试：自己造一组数，让最大值只出现在最前面。

在最后再放一个相同的最大值，输出的位置应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int maxn = x, pos = 1;
    for (int i = 2; i <= n; i++) {
        cin >> x;
        if (x > maxn) {
            maxn = x;
            pos = i;
        }
    }

    cout << pos;

    return 0;
}

2039：【例5.6】冒泡排序 ¶

提示 1：先做一轮相邻比较

从大到小排2 5 1，先比较2和5。

if (a[j] < a[j + 1]) swap(a[j], a[j + 1]);

从左往右走完一轮，最小的数去了哪里？

提示 2：末尾排好后少比较一次

数组从下标0存放，第一轮比较到j = n - 2。

第i轮前，末尾已有i个数排好：

for (int j = 0; j + 1 < n - i; j++) {
    // 比较相邻两个数
}

外层该做几轮？用两个数的数组检查一下。

常见错误

访问 a[j + 1] 时，要保证这个位置仍在本轮范围内。

每个结果单独输出一行。

自测

输入：

5
2 5 8 6 12

预期输出：

输入：

3
-3 -1 -2

预期输出：

-1
-2
-3

自己试试：自己造一组数，先写出从大到小的顺序。

只打乱输入顺序，排序后的结果应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

int a[1010];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j + 1 < n - i; j++) {
            if (a[j] < a[j + 1]) swap(a[j], a[j + 1]);
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << '\n';

    return 0;
}

2040：【例5.7】筛选法找质数 ¶

提示 1：先把不可能的数划掉

在2到20中圈出2，再划掉它大于自身的倍数。

下一个没被划掉的是谁？重复这个动作。

提示 2：标记的是合数

全局bool st[]默认全为false，表示暂未筛掉。

确认i未被标记后，可以这样筛：

for (int j = i + i; j <= n; j += i) st[j] = true;

先用i = 3列出会标记的数；为什么不能从j = i开始？

知识补充：筛的起点

模板从\(2i\)开始，标记质数\(i\)大于自身的倍数，保留\(i\)本身。

以后还可以把起点改成\(i^2\)，因为\(2i, 3i, \ldots, (i-1)i\)都含有小于\(i\)的质因数，前面已经筛过。

线性筛列为拓展，先掌握埃氏筛即可。

常见错误

1 不是质数。

线性筛遍历质数时，下标不能超过已找到的质数个数。

自测

输入：10，预期输出：

输入：2 → 预期输出：2

方法一：埃氏筛法

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int primes[N], cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

int main() {
    int n;
    cin >> n;

    get_primes(n);

    for (int i = 0; i < cnt; i++) cout << primes[i] << '\n';

    return 0;
}

方法二：线性筛法（拓展）

// 线性筛法
#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 510;

int primes[M], idx, n;
bool st[N];

int main() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[idx++] = i;

        for (int j = 0; j < idx && primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }

    for (int i = 0; i < idx; i++) cout << primes[i] << '\n';

    return 0;
}

1102：与指定数字相同的数的个数 ¶

提示 1：目标值最后才读到

输入顺序是个数、这一组数、目标值。

读数组时还不知道要找谁，所以先存下这组数。

提示 2：一次相等算一次

数组a读好、目标值存入k后，让cnt从0开始。

if (a[i] == k) cnt++;

把这句放进遍历前n个元素的循环，重复的目标值会不会都计入？

常见错误

数组容量不等于有效数据个数。

多遍历未输入的位置，可能把默认的零也算进去。

自测

输入：5 0 2 0 3 0 0 → 预期输出：3

输入：3 1 2 3 9 → 预期输出：0

方法一：下标遍历

#include <bits/stdc++.h>

using namespace std;

int a[110];
int n, k;

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    cin >> k;

    int cnt = 0;
    for (int i = 0; i < n; i++)
        if (a[i] == k)
            cnt++;

    cout << cnt;

    return 0;
}

方法二：vector 与范围循环（拓展）

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> k;

    int cnt = 0;
    for (int x : a) {
        if (x == k) cnt++;
    }

    cout << cnt;

    return 0;
}

1103：陶陶摘苹果 ¶

提示 1：刚好够到也能摘

假设身高100，站上30厘米的凳子后，130和131哪个能摘到？

提示 2：把比较写进循环

10个苹果高度已放进a[0]到a[9]，身高存入h。

if (a[i] <= h + 30) cnt++;

cnt从0开始，自己补上循环；别把凳子高度加到苹果上。

常见错误

别漏掉等号。

输入先是十个苹果的高度，再是身高，没有额外的个数。

自测

输入：100 130 131 140 150 160 170 180 190 200 100 → 预期输出：2

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int a[N];
int h, cnt;

int main() {
    for (int i = 0; i < 10; i++) cin >> a[i];
    cin >> h;

    for (int i = 0; i < 10; i++)
        if (h + 30 >= a[i]) cnt++;

    cout << cnt;

    return 0;
}

1104：计算书费 ¶

提示 1：先核对一种书

只买第一种书两本，其余全不买，费用应该是多少？

让单价数组price的顺序和输入顺序一致。

提示 2：把每项费用加进总价

sum用double，初值为0；读到第i种的本数count后：

sum += price[i] * count;

补上10次读入，最后按要求保留一位小数。

常见错误

单价顺序不能错，零本也要读入。

用 %.1f，保证整数金额也显示一位小数。

自测

输入：1 0 0 0 0 0 0 0 0 0 → 预期输出：28.9

输入：0 0 0 0 0 0 0 0 0 0 → 预期输出：0.0

参考代码

#include <bits/stdc++.h>

using namespace std;

const double price[] = {28.9, 32.7, 45.6, 78.0, 35.0,
                        86.2, 27.8, 43.0, 56.0, 65.0};

int main() {
    double sum = 0;
    for (int i = 0; i < 10; i++) {
        int count;
        cin >> count;
        sum += price[i] * count;
    }

    printf("%.1f", sum);

    return 0;
}

1105：数组逆序重存放 ¶

提示 1：这次要改数组本身

把1 2 3 4 5写在纸上，先交换最左和最右。

接着该交换哪两个位置？中间的3需要动吗？

提示 2：两端一起向中间走

数组从0开始，设l = 0、r = n - 1。

swap(a[l], a[r]);
l++;
r--;

用l < r控制重复操作，结束后再从前向后输出。

知识补充：reverse 的范围

reverse(a, a + n) 反转下标0到n - 1的元素。

右端 a + n 不包含在处理范围里。

常见错误

左右下标要同时移动。

只倒着输出，没有完成这题要练的“重存放”。

自测

输入：5 1 2 3 4 5 → 预期输出：5 4 3 2 1

输入：1 7 → 预期输出：7

方法一：首尾交换

#include <bits/stdc++.h>

using namespace std;

int a[110];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int l = 0, r = n - 1; l < r; l++, r--) swap(a[l], a[r]);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}

方法二：reverse 函数

#include <bits/stdc++.h>

using namespace std;

int a[110];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    reverse(a, a + n);

    for (int i = 0; i < n; i++) cout << a[i] << ' ';

    return 0;
}

1106：年龄与疾病 ¶

提示 1：把分界点分清

先给18、19、35、36、60、61各找一个年龄组。

四组人数加起来，应该等于什么？

提示 2：先计数，再算百分比

让a统计第一组人数，初值为0：

if (x >= 0 && x <= 18) a++;

自己补另外三组；算第一组比例时用1.0 * a / n * 100，为什么要乘1.0？

常见错误

区间不能漏人，也不能重复计数。

除法先转浮点数，printf 中的百分号写 %%。

自测

输入：

6
18 19 35 36 60 61

预期输出：

16.67%
33.33%
33.33%
16.67%

参考代码

// 输出0-18, 19-35, 36-60, 61以上，年龄的比例
#include <bits/stdc++.h>

using namespace std;

int a, b, c, d;
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        // 判断这个人的年龄，属于哪个分类的
        if (x >= 0 && x <= 18) a++;
        if (x >= 19 && x <= 35) b++;
        if (x >= 36 && x <= 60) c++;
        if (x >= 61) d++;
    }

    printf("%.2lf%%\n", 1.0 * a / n * 100);
    printf("%.2lf%%\n", 1.0 * b / n * 100);
    printf("%.2lf%%\n", 1.0 * c / n * 100);
    printf("%.2lf%%", 1.0 * d / n * 100);

    return 0;
}

1107：校门外的树 ¶

提示 1：重叠不能重复减

画出0到6的位置，把区间[1,3]和[3,5]涂掉。

位置3虽然被涂两次，树能移走两次吗？

提示 2：涂色对应数组标记

全局tree[]初值为0，对应有树；移走后记为1。

for (int i = l; i <= r; i++) tree[i] = 1;

处理完所有区间，再数0到L中仍为0的位置，别漏掉位置0。

常见错误

总共 \(L+1\) 个位置，区间两端也算。

直接相加区间长度，会重复扣掉重叠部分。

自测

输入：10 2 2 4 4 6 → 预期输出：6

输入：5 1 0 5 → 预期输出：0

自己试试：自己画一条短路，安排两个互不重叠的施工区间。

只移动其中一个区间，让它们重叠，剩下的树会怎样变化？

方法一：数组标记

#include <bits/stdc++.h>

using namespace std;

const int N=10010;

int tree[N];  //tree[i] = 0代表有树
int L, M;
int cnt;

int main() {
    cin >> L >> M;
    while (M--) {
        int l, r;
        cin >> l >> r;
        for (int i = l; i <= r; i++) tree[i] = 1;
    }

    for (int i = 0; i <= L; i++)
        if (tree[i] == 0) cnt++;

    cout << cnt;

    return 0;
}

方法二：map 标记（拓展）

// 用map维护
#include <bits/stdc++.h>

using namespace std;

map<int, int> mp;

int main() {
    int n, m;
    cin >> n >> m;

    while (m--) {
        int l, r;
        cin >> l >> r;

        for (int i = l; i <= r; i++) mp[i] = 1;
    }

    int cnt = 0;
    for (int i = 0; i <= n; i++)
        if (mp.count(i) == 0) cnt++;

    cout << cnt;

    return 0;
}

1108：向量点积计算 ¶

提示 1：上下对齐再乘

对1 2 3和4 5 6，先写出三次乘法。

第二个数应该和另一组的哪个数相乘？

提示 2：每一对加进总和

两组数已读入a、b，sum用long long并从0开始。

sum += 1LL * a[i] * b[i];

自己补遍历；1LL让乘法也按long long计算，不只是最后存入时才转换。

常见错误

不是所有数两两相乘，也不是分别求和再相乘。

乘法前用 1LL 提升类型，别等溢出后再存入 long long。

自测

输入：3 1 2 3 4 5 6 → 预期输出：32

输入：2 -1 2 3 -4 → 预期输出：-11

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int a[N], b[N];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += 1LL * a[i] * b[i];

    cout << sum;

    return 0;
}

1109：开关灯 ¶

提示 1：先和开关门对照

这次灯开始全亮，最后要找灭的灯。

全局bool light[]默认是false，这里人为约定它对应亮。

提示 2：跟着一个人反转

第i个人只碰编号为i的倍数的灯：

for (int j = i; j <= n; j += i) light[j] = !light[j];

外层让i从1走到m，结束后哪个状态表示灭？

提示 3：逗号放在两项之间

已经找到一盏灭灯时，后面再找到的灭灯前才加逗号。

用flag记录是否输出过编号，先设为false。

if (flag) cout << ',';
cout << j;
flag = true;

把这段放在“第j盏灯灭”的分支里。

常见错误

处理的是前 m 个人，不是 n 个人。

编号之间用逗号分隔，末尾不加逗号。

自测

输入：10 3 → 预期输出：1,5,6,7

输入：1 1 → 预期输出：1

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

bool light[N];   // 全局数组默认是 false，这里约定 false 对应亮、true 对应灭
int n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
        for (int j = i; j <= n; j += i)
            light[j] = !light[j];

    bool flag = false;
    for (int j = 1; j <= n; j++)
        if (light[j]) {
            if (flag) cout << ',';
            cout << j;
            flag = true;
        }

    return 0;
}

1110：查找特定的值 ¶

提示 1：两个相同目标要选谁

在8 3 3 9中找3，先写出题目要求的位置。

数组从下标1存放，找不到先让pos = -1。

提示 2：找到后及时停下

if (a[i] == x) {
    pos = i;
    break;
}

把它放进从前往后的循环；去掉break会留下哪个位置？

常见错误

题目位置和数组下标要对应好。

没找到要输出 -1，别让后面的重复值覆盖第一次的位置。

自测

输入：4 8 3 3 9 3 → 预期输出：2

输入：3 1 2 3 7 → 预期输出：-1

自己试试：自己造一组数，让目标值只出现在最后。

只把它移到最前面，输出的位置应该怎样变化？

方法一：记录位置后输出

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int a[N];
int n, x;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cin >> x;

    int pos = -1;
    for (int i = 1; i <= n; i++)
        if (a[i] == x) {
            pos = i;
            break;
        }

    cout << pos;

    return 0;
}

方法二：找到后直接结束

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int a[N], n, m;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;

    int pos = -1;
    for (int i = 1; i <= n; i++)
        if (a[i] == m) {
            cout << i;

            return 0;
        }

    cout << pos;

    return 0;
}

1111：不高兴的津津 ¶

提示 1：先判断有没有不高兴

一天两项时间为4和4，恰好8小时，要记录这一天吗？

再比较总时长为9的两天，题目要求选哪一天？

提示 2：符合条件才打擂台

按周一到周日读入x、y；最高时长maxn = -1，答案ret = 0。

if (x + y > 8 && x + y > maxn) {
    maxn = x + y;
    ret = i;
}

如果七天都不超过8小时，ret会保持多少？

常见错误

刚好 8 小时不算超过。

并列时不能用 >= 覆盖，否则会留下后一天。

自测

输入：5 3 4 4 6 3 5 4 4 4 3 4 2 2 → 预期输出：3

输入：4 4 4 4 4 4 4 4 4 4 4 4 4 4 → 预期输出：0

参考代码

#include <bits/stdc++.h>

using namespace std;

int maxn = -1;
int ret = 0;

int main() {
    for (int i = 1; i <= 7; i++) {
        int x, y;
        cin >> x >> y;

        if (x + y > 8) {
            if (x + y > maxn) {
                maxn = x + y;
                ret = i;
            }
        }
    }

    cout << ret;

    return 0;
}

1112：最大值和最小值的差 ¶

提示 1：先把两个擂主放到两端

对-5 -2 -8，最大值和最小值分别是多少？

每个数的绝对值不超过10000，先让maxn足够小、minn足够大：

int maxn = -2e9, minn = 2e9;

这样第一个数一定能更新两份纪录，后面继续比较。

提示 2：每个数都参加比较

每读入一个新的x：

maxn = max(maxn, x);
minn = min(minn, x);

共读n个数，最后用maxn - minn求差。

常见错误

最小值初始化为零，会影响全正数的结果。

最大值也别从0开始，全是负数时，0并不是读入的数。

自测

输入：4 -5 2 9 -1 → 预期输出：14

输入：1 7 → 预期输出：0

方法一：用极小值、极大值初始化

本题最大差不超过20000，读入、比较和求差都用int即可。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int maxn = -2e9, minn = 2e9;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        maxn = max(maxn, x);
        minn = min(minn, x);
    }

    cout << maxn - minn;

    return 0;
}

方法二：用第一个数初始化

先自己读一遍：第一个数在哪里读入，为什么循环只读n - 1次？

用n = 1走一下，看看不进循环时为什么也能得到正确答案。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    int x;
    cin >> n >> x;
    int maxn = x, minn = x;
    for (int i = 1; i < n; i++) {
        cin >> x;
        maxn = max(maxn, x);
        minn = min(minn, x);
    }

    cout << maxn - minn;

    return 0;
}

1113：不与最大数相同的数字之和 ¶

提示 1：先分清删的是哪些数

对2 5 5 1，两个5都不参与求和，结果是多少？

提示 2：分两遍，别边猜边加

先把数存入a并找出maxn，再让long long sum = 0;。

if (a[i] != maxn) sum += a[i];

把这句放进第二遍循环；全部数相同，为什么会得到0？

常见错误

不是从总和里只减掉一个最大值。

全部相同时，答案为零。

自测

输入：5 2 5 5 1 3 → 预期输出：6

输入：3 4 4 4 → 预期输出：0

自己试试：自己造一组数，先算出不与最大值相同的数字之和。

只在末尾再加一个相同的最大值，答案应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N];
int n;
int maxn;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i == 0 || a[i] > maxn) maxn = a[i];
    }

    long long sum = 0;
    for (int i = 0; i < n; i++)
        if (a[i] != maxn) sum += a[i];

    cout << sum;

    return 0;
}

1114：白细胞计数 ¶

提示 1：先划掉，再算

拿6 2 11 3 3这五次结果试一下。

划掉一次最大值11、一次最小值2，剩下6 3 3。

先求这三个数的平均数，再看它们各自离平均数有多远。

提示 2：数组不搬动，记住跳过哪两格

沿方法一写，数组下标从0开始：刚才的11在a[2]，2在a[1]。

用hi记最大值的位置，lo记最小值的位置，注意存的是下标。

初始hi = lo = 0，遍历到a[i]时：

if (a[i] > a[hi]) hi = i;
if (a[i] < a[lo]) lo = i;

循环前先设double sum = 0;，遍历时把a[i]加进去。

提示 3：平均数只算留下来的

刚才五个数的总和是25，减掉11和2，剩下12，一共留下3个数。

对应代码：

double ave = (sum - a[hi] - a[lo]) / (n - 2);

这里ave是平均数，n - 2是留下的次数；数组里的数不用真的删掉。

提示 4：偏差就是离平均数多远

剩下6 3 3，平均数为4，距离分别是2、1、1，所以最大偏差是2。

abs(a[i] - ave)取差的绝对值，3减4得到-1，取绝对值后距离是1。

maxn从0开始，只让留下的数参加比较：

if (i != hi && i != lo)
    maxn = max(maxn, abs(a[i] - ave));

11已经被划掉了，别再拿它和平均数比。

知识补充：所有数都一样怎么办

例如6 6 6 6，没有谁更大、更小，hi、lo会一直都是0。

但题目仍要去掉两次结果，所以代码用if (hi == lo) lo = 1;，让两个位置不同。

这句在计算平均数之前执行；只减掉两次6，其余的6仍要保留。

题目保证n > 2，所以另选下标1有位置可用，n - 2也不会是0。

常见错误

重复的最大、最小值，不能全部删掉。

全部相同时，也要删两个不同位置，分母是 \(n-2\)。

自测

输入：5 1 2 3 4 5 → 预期输出：3.00 1.00

输入：4 6 6 6 6 → 预期输出：6.00 0.00

输入：5 6 2 11 3 3 → 预期输出：4.00 2.00

输入：3 1 2 3 → 预期输出：2.00 0.00

输入：5 10.1 10.1 10.2 10.5 10.8 → 预期输出：10.27 0.23

方法一：记录被删样本下标

先读入数组，再求总和、找两个位置，最后只遍历留下的数求最大偏差。

#include <bits/stdc++.h>

using namespace std;

double a[310];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int hi = 0, lo = 0;
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (a[i] > a[hi]) hi = i;
        if (a[i] < a[lo]) lo = i;
    }

    // 全部相同时，也要删除两个不同的样本
    if (hi == lo) lo = 1;

    double ave = (sum - a[hi] - a[lo]) / (n - 2);

    double maxn = 0;
    for (int i = 0; i < n; i++)
        if (i != hi && i != lo) maxn = max(maxn, abs(a[i] - ave));

    printf("%.2lf %.2lf", ave, maxn);

    return 0;
}

方法二：排序后处理中间样本

从小到大排序后，最小值在a[0]，最大值在a[n - 1]。

后面两遍循环都只处理下标1到n - 2，分别求平均数、最大偏差。

#include <bits/stdc++.h>

using namespace std;

double a[310];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);

    double sum = 0.0;
    for (int i = 1; i <= n - 2; i++) sum += a[i];
    double ave = sum / (n - 2);

    double maxn = 0;
    for (int i = 1; i <= n - 2; i++)
        maxn = max(maxn, fabs(a[i] - ave));

    printf("%.2lf %.2lf", ave, maxn);

    return 0;
}

1115：直方图 ¶

提示 1：给每个数准备一个计数格

输入0 2 2，0、1、2分别出现几次？

没有出现的1也要有一行输出。

提示 2：数值用来当下标

全局cnt[]初值为0，读到数值x：

cnt[x]++;

同时记住最大数maxn，输出下标0到maxn的计数；循环要不要包含右端点？

常见错误

计数数组的下标是数值，不是输入顺序。

未出现的数也要输出零。

自测

输入：

5
0 2 2 4 0

预期输出：

参考代码

#include <bits/stdc++.h>

using namespace std;

int cnt[10010];

int main() {
    int n, maxn = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
        maxn = max(maxn, x);
    }

    for (int i = 0; i <= maxn; i++) cout << cnt[i] << '\n';

    return 0;
}

1116：最长平台 ¶

提示 1：沿着平台走

给1 1 2 2 2 3划段，最长的是哪一段？

用last记前一个数，cnt记当前长度，maxn记见过的最长长度。

提示 2：换数时从1重新数

第一个数已读入last，让cnt = maxn = 1；再读入x后：

if (x == last) cnt++;
else cnt = 1;

为什么不能把cnt清成0？

提示 3：每读一个就更新擂主

last = x;
maxn = max(maxn, cnt);

放在上面分支之后，用1 2 2 2跟踪，检查最后一个平台有没有算进去。

常见错误

不是统计一个值在全串中的总次数。

最后一段也要参与最大值比较。

自测

输入：8 1 1 2 2 2 3 3 3 → 预期输出：3

输入：4 -1 -1 -1 -1 → 预期输出：4

自己试试：自己造一个非降序序列，让最长平台出现在最后。

只在末尾再添一个相同的数，答案应该增加多少？

方法一：维护连续长度

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, last;
    cin >> n >> last;

    int cnt = 1;
    int maxn = 1;

    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;

        if (x == last) {
            cnt++;
        } else {
            cnt = 1;
        }

        last = x;
        maxn = max(maxn, cnt);
    }

    cout << maxn;

    return 0;
}

方法二：按段扫描

// 先找到这一段的末尾，再跳到下一段
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N], n;
int maxn;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && a[j] == a[i]) j++;

        maxn = max(maxn, j - i);

        i = j - 1;
    }

    cout << maxn;

    return 0;
}

1117：整数去重 ¶

提示 1：第一次见才留下

按顺序看30 10 30 20，第二次遇到30时需要再输出吗？

提示 2：输出后做个记号

全局bool st[]默认是false，表示还没见过这个值。

if (!st[x]) {
    cout << x << ' ';
    st[x] = true;
}

每读到一个数就执行这段，为什么能保留第一次出现的顺序？

常见错误

先排序会改变原顺序。

数值当下标时，先确认范围放得进标记数组。

自测

输入：7 30 10 30 20 10 20 40 → 预期输出：30 10 20 40

自己试试：自己造一组数，让同一个数出现两次，中间隔着别的数。

只把后一次出现的这个数移到末尾，去重结果应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

bool st[N];
int n;

int main() {
    cin >> n;
    while (n--) {
        int x;
        cin >> x;

        if (!st[x]) {
            cout << x << ' ';
            st[x] = true;
        }
    }

    return 0;
}

1118：铺地毯 ¶

提示 1：从最上面那张找起

两张地毯都盖住目标点，后铺的在上还是先铺的在上？

按铺设顺序存好后，试着从编号n往回找。

提示 2：先只检查横坐标

第i张左下角为(a[i], b[i])，宽高为g[i]、k[i]。

a[i] <= x && x <= a[i] + g[i]

这是横向覆盖条件；仿照它写纵向条件，再用&&连接。

第一次覆盖就记录编号并停止，始终没找到则输出-1。

常见错误

边界也算覆盖，找不到输出 -1。

覆盖条件是 \(a\le x\le a+g\) 且 \(b\le y\le b+k\)。

自测

输入：2 0 0 3 3 1 1 2 2 2 2 → 预期输出：2

输入：1 0 0 1 1 2 2 → 预期输出：-1

参考代码

#include <bits/stdc++.h>

using namespace std;

int a[10010], b[10010], g[10010], k[10010];

int main() {
    int n, x, y;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> g[i] >> k[i];
    cin >> x >> y;

    int ans = -1;
    for (int i = n; i >= 1; i--) {
        if (a[i] <= x && x <= a[i] + g[i] && b[i] <= y && y <= b[i] + k[i]) {
            ans = i;
            break;
        }
    }

    cout << ans;

    return 0;
}

第二节二维数组¶

2041：【例5.9】新矩阵 ¶

提示 1：在格子上写下行列号

画三阶矩阵，两条对角线上的格子分别满足什么关系？

这里行列都从1编号，副对角线上两编号的和是多少？

提示 2：交点只能加一次

if (i == j || i + j == n + 1) a[i][j] += 10;

把它放进遍历矩阵的两层循环，中心格同时满足两条件，会加几次？

常见错误

两个独立的加法，会让中心格加两次。

用 || 合并条件。

自测

输入：

预期输出：

11 2 13
4 15 6
17 8 19

自己试试：自己造一个奇数阶矩阵，先标出中心格。

只把中心格的数增加 \(1\)，输出中的这个数应该增加多少？

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int a[N][N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j || (i + j) == (1 + n)) a[i][j] += 10;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

2042：【例5.10】稀疏矩阵 ¶

提示 1：先按读入顺序找非零数

用一个两行三列的矩阵，把每个非零数的行号、列号写在旁边。

只输出这些位置，需要保存已经处理过的零吗？

提示 2：读到一个就决定是否输出

外层循环行i、内层循环列j，都从1开始，当前读入值为x：

if (x != 0) cout << i << ' ' << j << ' ' << x << '\n';

补上读入与两层循环，顺序是否正好和题目要求一致？

常见错误

行、列都从 1 编号，别写反。

非零不等于大于零，负数也要输出。

自测

输入：

2 3
0 5 0
-2 0 7

预期输出：

1 2 5
2 1 -2
2 3 7

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            if (x != 0) cout << i << ' ' << j << ' ' << x << '\n';
        }
    }

    return 0;
}

2043：【例5.11】杨辉三角形 ¶

提示 1：先从上一行找来源

写下1 2 1，下一行中间的3来自哪两个数？

第i行只有i个数，两端先填1。

提示 2：中间格子用上一行

数组行列从1开始，对1 < j < i的位置：

a[i][j] = a[i - 1][j - 1] + a[i - 1][j];

先填完上一行再填下一行；输出每行时，列循环该到n还是i？

常见错误

第 i 行只输出 i 项。

两端先处理，别把数组里多开的格子当成三角形的一部分。

自测

输入：4，预期输出：

输入：1 → 预期输出：1

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int a[N][N];
int n;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            if (j == 1 || j == i) a[i][j] = 1;
            else a[i][j] = a[i-1][j] + a[i-1][j-1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

2044：【例5.12】回文字串 ¶

提示 1：结束句点不参加比较

abba.中的点用来结束输入，去掉它后再找首尾。

已用getline读入s，可以先写s.pop_back();删掉题目给定的末尾句点。

提示 2：从两端各走一步

设l = 0、r = (int)s.size() - 1。

if (s[l] != s[r]) break;
l++;
r--;

把它放在while (l < r)里；停下时，怎样分辨是遇到不同字符，还是已经比较完？

常见错误

这题输出 Yes、No，与 1146 的大小写不同。

不要把结束句点参与比较。

自测

输入：abba. → 预期输出：Yes

输入：abc. → 预期输出：No

方法一：双下标比较

#include <bits/stdc++.h>

using namespace std;

string s;

// abcdcba.
// l     r

int main() {
    getline(cin, s);

    if (!s.empty() && s.back() == '.') s.pop_back();

    int l = 0, r = (int)s.size() - 1;
    while (l < r) {
        if (s[l] != s[r]) break;
        l++, r--;
    }

    if (l < r) cout << "No";
    else cout << "Yes";

    return 0;
}

方法二：反转后比较

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '.') s.pop_back();
    string t = s;
    reverse(t.begin(), t.end());

    if (s == t) cout << "Yes";
    else cout << "No";

    return 0;
}

2045：【例5.13】蛇形填数 ¶

提示 1：先画出怎么走

先画一个三阶方阵，从右上角写1，按下、左、上、右的顺序填数。

7 8 1
6 9 2
5 4 3

下面的提示对应方法一：一个while填一个方向，四个方向走完，再往里填。

提示 2：这一行代码，拆开看

i是行号，j是列号，下标从1开始；往下走，行号加一，列号不变。

全局数组a默认全为0，这里用0表示空格；idx从0开始，记录已经填了几个数。

从i = 1, j = n出发，向下填数的这一行：

while (i <= n && !a[i][j]) a[i++][j] = ++idx;

先别急，这里可以拆成下面几步来理解：

while (i <= n && a[i][j] == 0) {
    idx++;
    a[i][j] = idx;
    i++;
}

++idx先加一，再拿新编号填数；i++用当前行号填好这一格，再移到下一行。

循环条件同时检查：没走出下边界，而且这一格还空着。

提示 3：为什么要退一步，再转弯

看三阶方阵，向下填完1、2、3后，i = 4, j = 3，已经走过头了。

接着执行：

i--, j--;

这句就是先执行i--;，再执行j--;。

先退回第3行，再向左到第2列，下一个数4就填在a[3][2]。

向左时，列号越来越小，这一段可以接着写：

while (j >= 1 && !a[i][j]) a[i][j--] = ++idx;
j++, i--;

你跟着走一下：填完4、5后，停在第几行、第几列？

再照这个办法，补向上、向右的两段。

提示 4：第二圈，靠什么停下来

第一圈填完8后，下一格是a[2][2]，填上9。

再往下，a[3][2]已经有4了，!a[i][j]不成立，这一段就停下，不会覆盖原来的数。

所以每段既要判断边界，也要判断这一格有没有填过。

外层用while (idx < n * n)控制，只要还没填满，就继续按四个方向走。

常见错误

一阶矩阵也要填上 1。

四个方向的边界不同：向下看i <= n，向左看j >= 1，另两方向自己对照。

一段结束后，要先退回最后填的格子，再向新方向走一步。

自测

输入：3，预期输出：

7 8 1
6 9 2
5 4 3

输入：1 → 预期输出：1

方法一：四个方向逐段填数

#include <bits/stdc++.h>

using namespace std;

const int N = 25;

int a[N][N], n;
int idx;

int main() {
    cin >> n;
    int i = 1, j = n;

    while (idx < n * n) {
        while (i <= n && !a[i][j]) a[i++][j] = ++idx;
        i--, j--;
        while (j >= 1 && !a[i][j]) a[i][j--] = ++idx;
        j++, i--;
        while (i >= 1 && !a[i][j]) a[i--][j] = ++idx;
        i++, j++;
        while (j <= n && !a[i][j]) a[i][j++] = ++idx;
        j--;
        i++;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

方法二：方向数组模拟

这个方法每次只填一格，用d记录方向：0向下、1向左、2向上、3向右。

dr[d]是行号的变化量，dc[d]是列号的变化量，例如向下就是行号加1、列号不变。

nr、nc先试探下一格，不能走时，用d = (d + 1) % 4换到下一个方向，再重新算下一格。

#include <bits/stdc++.h>

using namespace std;

int a[25][25];
int dr[] = {1, 0, -1, 0}, dc[] = {0, -1, 0, 1};

int main() {
    int n;
    cin >> n;
    int row = 1, col = n, d = 0;
    for (int idx = 1; idx <= n * n; idx++) {
        a[row][col] = idx;
        if (idx == n * n) break;
        int nr = row + dr[d], nc = col + dc[d];
        if (nr < 1 || nr > n || nc < 1 || nc > n || a[nr][nc] != 0) {
            d = (d + 1) % 4;
            nr = row + dr[d];
            nc = col + dc[d];
        }
        row = nr;
        col = nc;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

1119：矩阵交换行 ¶

提示 1：列不动，只换两行

把两行上下对齐，同一列的两个数应该互换。

这里固定读入5行5列，待交换行号存入n、m。

提示 2：一次只交换一列

for (int j = 1; j <= 5; j++) swap(a[n][j], a[m][j]);

自己补读入和按行输出；如果n == m，交换后会发生什么？

常见错误

别额外读矩阵规模。

交换同一行时，结果应不变。

自测

输入：

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
1 5

预期输出：

21 22 23 24 25
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
1 2 3 4 5

参考代码

#include <bits/stdc++.h>

using namespace std;

int a[10][10], n, m;

int main() {
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            cin >> a[i][j];

    cin >> n >> m;

    for (int j = 1; j <= 5; j++)
        swap(a[m][j], a[n][j]);

    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

1120：同行列对角线的格 ¶

提示 1：先分开画四条线

在方格纸上标出(x, y)，先画同行和同列。

同行只改变列号，同列只改变行号，不必枚举所有格子。

提示 2：沿斜线看编号关系

行列从1开始，向右下走一步，行列都加1，差会不会变？

if (i - j == x - y) printf("(%d,%d) ", i, j);

另一条斜线用行列和判断；按题目要求，最后一条从下往上输出，行循环应从哪里开始？

常见错误

最后一条斜线按左下到右上输出，行号递减。

找的是经过给定格子的线，不只是方阵自身的两条对角线。

自测

输入：3 2 2，预期输出：

(2,1) (2,2) (2,3)
(1,2) (2,2) (3,2)
(1,1) (2,2) (3,3)
(3,1) (2,2) (1,3)

参考代码

#include <bits/stdc++.h>

using namespace std;

int n, x, y;

int main() {
    cin >> n >> x >> y;

    for (int j = 1; j <= n; j++) printf("(%d,%d) ", x, j);
    cout << '\n';

    for (int i = 1; i <= n; i++) printf("(%d,%d) ", i, y);
    cout << '\n';

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i - j == x - y) printf("(%d,%d) ", i, j);
    cout << '\n';

    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= n; j++)
            if (i + j == x + y) printf("(%d,%d) ", i, j);

    return 0;
}

1121：计算矩阵边缘元素之和 ¶

提示 1：别把角重复加两次

给三行三列矩阵描边，四个角各只能加一次。

只有一行时，所有格子是不是都在边缘？

提示 2：每个格子只判断一次

行号i从1到n，列号j从1到m，当前数为x，sum初值为0。

if (i == 1 || i == n || j == 1 || j == m) sum += x;

这一个if和四个分别累加的if，在角点处有什么不同？

常见错误

一行或一列的矩阵，每个元素仍只算一次。

别把四条边分别相加后，又忘了处理重复位置。

自测

输入：

预期输出：40

输入：

1 3
1 2 3

预期输出：6

自己试试：自己造一个三行三列的矩阵，先算出边缘元素之和。

只改变中心格，答案应不应该变？

参考代码

// 第1行，第n行
// 第1列，第m列
#include <bits/stdc++.h>

using namespace std;

int n, m;

int main() {
    cin >> n >> m;

    int sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;

            if (i == 1 || j == 1 || i == n || j == m) sum += x;
        }

    cout << sum;

    return 0;
}

1122：计算鞍点 ¶

提示 1：一个格子要过两关

先挑一格，看它是否为本行最大；再看它是否为本列最小。

只通过其中一关，能称为鞍点吗？

提示 2：先给每行每列做记录

数组从1编号，让row[i]记第i行最大值，col[j]记第j列最小值。

从各行、各列第一个元素初始化，再分别向后比较。

row[i] = max(row[i], a[i][j]);

这是更新行最大值的一步，列最小值该怎样改？

提示 3：用两份记录检查交点

a[i][j] == row[i] && a[i][j] == col[j]

把条件放入遍历，找到时输出位置和值，并做标记；全部查完还没找到时，再输出not found。

常见错误

行最大、列最小，别记反。

没有鞍点时输出 not found。

自测

输入：

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

预期输出：1 5 5

参考代码

#include <bits/stdc++.h>

using namespace std;

int a[6][6], row[6], col[6];

int main() {
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++) cin >> a[i][j];

    for (int i = 1; i <= 5; i++) {
        row[i] = a[i][1];
        for (int j = 2; j <= 5; j++) row[i] = max(row[i], a[i][j]);
    }
    for (int j = 1; j <= 5; j++) {
        col[j] = a[1][j];
        for (int i = 2; i <= 5; i++) col[j] = min(col[j], a[i][j]);
    }

    bool found = false;
    for (int i = 1; i <= 5 && !found; i++) {
        for (int j = 1; j <= 5; j++) {
            if (a[i][j] == row[i] && a[i][j] == col[j]) {
                cout << i << ' ' << j << ' ' << a[i][j];
                found = true;
                break;
            }
        }
    }
    if (!found) cout << "not found";

    return 0;
}

1123：图像相似度 ¶

提示 1：相同也要在同一位置

两张图都有一个5，但一个在左上、一个在右下，能算对应位置相同吗？

提示 2：只对齐同一个格子比较

第一张存入a，读第二张的第i行第j列数值x时：

if (x == a[i][j]) cnt++;

cnt从0开始；总格数是n * m，用1.0 * cnt / (n * m) * 100计算百分数，再按题目格式输出。

常见错误

总格数是 \(nm\)，不是 n 或 m。

用浮点除法，保留两位小数，不加百分号。

自测

输入：

预期输出：50.00

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;

            if (x == a[i][j]) cnt++;
        }

    double res = cnt * 1.0 / (n * m);
    printf("%.2lf", res * 100);

    return 0;
}

1124：矩阵加法 ¶

提示 1：先算左上角一格

两张矩阵上下对齐，左上角的结果需要用到别的行或列吗？

提示 2：第二张边读边加

第一张已存入a，第二张同位置的值读到x：

a[i][j] += x;

把这步放进两层读入循环，最后按原来的行列数输出。

常见错误

不是把整张表求成一个总和。

行数、列数在循环中别混用。

自测

输入：

预期输出：

7 7 7
7 7 7

参考代码

#include <bits/stdc++.h>

using namespace std;

int a[110][110];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;

            a[i][j] += x;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

1125：矩阵乘法 ¶

提示 1：先不写三层循环

先算一格：一行1 2 3，配上一列4 5 6，得到\(1\times4+2\times5+3\times6\)。

算出这个和，再看代码里三个数是怎样配对的。

结果的一格来自第一张的一行、第二张的一列，不是只乘同位置。

提示 2：固定结果的一格

第一张是\(n\times k\)矩阵，第二张是\(k\times m\)矩阵，相乘得到\(n\times m\)矩阵。

这里把共同的长度记作k，输入的三个数依次读到n、k、m。

固定第i行第j列，沿共同长度k累加：

for (int p = 1; p <= k; p++)
    c[i][j] += a[i][p] * b[p][j];

c是全局int数组，初值为0；为什么一个下标固定i，另一个固定j？

提示 3：再把这一格扩成整张表

外面两层循环分别枚举结果的行i、列j，边界是n和m。

先用两行三列乘三行四列试一遍，结果应该有几行几列？

常见错误

不是对应位置直接相乘。

累加前结果应为0；本题用全局int数组c，默认已初始化为0。

自测

输入：

预期输出：

38 44 50 56
83 98 113 128

自己试试：自己造两个能相乘的小矩阵，先手算结果中的一格。

只改第一个矩阵中的一个数，结果中哪些格子可能改变？

参考代码

共同长度k小于100，每个元素绝对值不超过1000，一格累加结果的绝对值小于\(10^8\)，int足够。

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N], b[N][N], c[N][N];
int n, k, m;

int main() {
    cin >> n >> k >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++) cin >> a[i][j];

    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= m; j++) cin >> b[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int p = 1; p <= k; p++)
                c[i][j] += a[i][p] * b[p][j];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << c[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

1126：矩阵转置 ¶

提示 1：把第一列横过来

给两行三列矩阵填上1到6，转置后第一行是哪两个数？

一共要输出几行？

提示 2：先固定列，再走行

读入数组a后，固定原矩阵列号j：

for (int i = 1; i <= n; i++) cout << a[i][j] << ' ';

在外面补上j从1到m的循环；一列读完后换行，别在每个数后换行。

常见错误

转置不等于旋转。

拿非方阵检查，更容易看出方向是否正确。

自测

输入：

2 3
1 2 3
4 5 6

预期输出：

1 4
2 5
3 6

自己试试：自己造一个两行三列的矩阵，先写出转置结果。

把这个结果再转置一次，会不会回到原来的矩阵？

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N];
int n, m;

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

1127：图像旋转 ¶

提示 1：先看四个角去了哪里

画一个两行三列的表，顺时针转90度。

原来的左下角会成为新图的哪个角？

提示 2：每列从下往上读

第j列变成结果的一行：

for (int i = n; i >= 1; i--) cout << a[i][j] << ' ';

外层从左到右枚举j，每列结束换行；和转置那题相比，哪一层循环反过来了？

常见错误

结果从 \(n\times m\) 变成 \(m\times n\)。

别照搬转置时从上到下的方向。

自测

输入：

2 3
1 2 3
4 5 6

预期输出：

4 1
5 2
6 3

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N];
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    for (int j = 1; j <= m; j++) {
        for (int i = n; i >= 1; i--)
            cout << a[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

1128：图像模糊处理 ¶

提示 1：先只算一个内部像素

在三行三列的图里，中心格需要读取哪五个旧值？

如果刚算完就改原图，下一个格子读到的还是旧值吗？

提示 2：原图和结果分开存

原图是a，新图存入b；边缘直接复制。

b[i][j] = a[i][j];

只在内部格子计算五项和，除以5.0后用round四舍五入；自己写出上下左右的四组下标。

提示 3：用一行图检查边界

若图只有一行，还有内部格子吗？

把边缘判断放在前面，再进入计算分支，能避免访问不存在的上下邻居。

常见错误

除法写 / 5.0，再用 round 四舍五入。

不能边算边覆盖原图，也不能只平均四个邻居。

自测

输入：

预期输出：

0 0 0
0 2 0
0 0 0

输入：

1 3
10 20 30

预期输出：10 20 30

自己试试：自己造一张像素值全部相同的合法图像，先预测模糊结果。

只改变一个内部像素，哪些位置的结果可能改变？

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N], b[N][N], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i == 1 || i == n || j == 1 || j == m) b[i][j] = a[i][j];
            else b[i][j] = round((a[i][j] + a[i-1][j] + a[i+1][j] + a[i][j-1] + a[i][j+1]) / 5.0);
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << b[i][j] << ' ';
        cout << '\n';
    }

    return 0;
}

第三节字符类型和字符数组¶

2046：【例5.15】替换字母 ¶

提示 1：整句话先保留下来

句子里有空格，cin >> s能读完整句吗？

先用getline(cin, s)读句子，再读要替换的字符a和新字符b。

提示 2：只改匹配的位置

if (s[i] == a) s[i] = b;

放进逐字符循环；遇到空格或别的字符，应不应该改？

常见错误

有空格的文本用 getline，别只读到第一个词。

每个位置只替换一次。

自测

输入：

a cat and a cap
a o

预期输出：o cot ond o cop

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
char a, b;

int main() {
    getline(cin, s);
    cin >> a >> b;

    for (int i = 0, len = s.size(); i < len; i++)
        if (s[i] == a) s[i] = b;

    cout << s;

    return 0;
}

2047：【例5.16】过滤空格 ¶

提示 1：三个空格只留第一个

在纸上写a b，把第二、第三个空格划掉。

决定当前空格要不要输出时，只看前一个原字符够不够？

提示 2：别在开头访问前一个位置

已读入整行s，从下标0遍历：

if (i > 0 && s[i] == ' ' && s[i - 1] == ' ') continue;

其余字符照常输出；用行首两个空格试一遍，会留下几个？

常见错误

逐词读取会丢掉原行首尾的空格。

不要把“压成一个”做成“全部删除”。

自测

输入：a b c → 预期输出：a b c

输入： a b → 预期输出： a b

第二组输入和输出都有行首、行尾空格，复制时留意。

自己试试：自己写一句带连续空格的话，先写出过滤后的结果。

只把其中一段连续空格加长，输出应不应该变？

方法一：比较相邻字符

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    for (int i = 0, len = s.size(); i < len; i++) {
        if (i && s[i] == ' ' && s[i - 1] == ' ') continue;
        cout << s[i];
    }

    return 0;
}

方法二：记录上一字符状态

preSpace表示前一个原字符是不是空格，开头还没有前一个字符，所以初值为false。

for (char c : s)依次取出字符串里的字符，每处理一个都要更新preSpace。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    bool preSpace = false;
    for (char c : s) {
        if (c != ' ' || !preSpace) cout << c;
        preSpace = (c == ' ');
    }

    return 0;
}

2048：【例5.18】串排序 ¶

提示 1：字典序不是按长短排

先排b、ab、a、aa，从左往右比较第一个不同字符。

a是ab的前缀，这时谁在前？

提示 2：排序前先把字符串存好

前n个串存入s[0]到s[n - 1]后：

sort(s, s + n);

按顺序逐行输出，自己把手排结果与程序对照。

知识补充：字典序与 sort

从左往右看，第一个不同的字符决定顺序。

sort(s, s + n) 默认按这个顺序排列前n个字符串。

常见错误

不忽略大小写，也不按长度排序。

相同字符串仍要保留原来的份数。

自测

输入：

4
b
ab
a
aa

预期输出：

a
aa
ab
b

参考代码

#include <bits/stdc++.h>

using namespace std;

string s[25];
int n;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];

    sort(s, s + n);

    for (int i = 0; i < n; i++) cout << s[i] << '\n';

    return 0;
}

2049：【例5.19】字符串判等 ¶

提示 1：先看处理后剩下什么

A b C和aB c直接比较，当然不一样。

但这道题不区分大小写，还要忽略空格，可以先把两行都整理一下：

A b C → AbC → abc
aB c  → aBc → abc

整理后都是abc，所以输出YES。

字符顺序不能变，ab和ba仍然不同，不要排序。

提示 2：先读完整的两行

cin >> s1遇到空格就停，第一行的A b C只能读到A。

这里用getline，一次读一整行：

string s1, s2, a, b;
getline(cin, s1);
getline(cin, s2);

s1、s2保存原来的两行，a、b是两个空字符串，用来存整理后的内容。

提示 3：一个字符一个字符地整理

先只处理s1，每次取一个字符，暂时放在c里：

for (char c : s1) {
    if (c == ' ') continue;
    if (c >= 'A' && c <= 'Z') c += 'a' - 'A';
    a += c;
}

遇到空格，continue就跳过本轮，空格不会加进a。

遇到大写字母，先转成小写；其他字符保持原样，再用a += c接到新串末尾。

拿A b C跟一下：读到A，a变成a；读到空格，仍是a；读到b，变成ab。

最后一个C处理完，a应该是什么？

提示 4：第二行，你来处理

仿照上一段循环，遍历s2，把整理后的字符接到b末尾。

最后用a == b比较两个完整字符串，相同输出YES，否则输出NO。

只比较长度够不够？拿abc和abd试一下。

知识补充：为什么加上这个差值

'a' - 'A'是大小写字母编码的差值，其他英文字母也有同样的差值。

所以c += 'a' - 'A';能把大写字母转成对应的小写字母。

前面的判断不能省：已经是小写的b，不需要再加一次。

for (char c : s1)中的c是取出的字符副本，修改它不会改掉原串s1，整理结果要接到a中。

常见错误

第二段循环要遍历s2，并写b += c，别复制代码后忘了改名字。

空格要跳过，不能让它进入新串；大小写转换只处理大写字母。

最后比较整理后的a、b，结果输出大写YES、NO。

自测

输入：

A b C
aB c

预期输出：YES

输入：

abc
abd

预期输出：NO

自己试试：自己写两行相同的文字。

只改其中一行的字母大小写，再插入普通空格，判等结果应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s1, s2, a, b;
    getline(cin, s1);
    getline(cin, s2);

    for (char c : s1) {
        if (c == ' ') continue;
        if (c >= 'A' && c <= 'Z') c += 'a' - 'A';
        a += c;
    }

    for (char c : s2) {
        if (c == ' ') continue;
        if (c >= 'A' && c <= 'Z') c += 'a' - 'A';
        b += c;
    }

    if (a == b) cout << "YES";
    else cout << "NO";

    return 0;
}

2050：【例5.20】字串包含 ¶

提示 1：让跨首尾的部分连起来

把AABCD写两遍：AABCDAABCD。

原本绕过末尾的CDAA，现在能在纸上连续圈出来吗？

提示 2：先确定谁是长串

读入a、b，让a保存较长的串：

if (a.size() < b.size()) swap(a, b);
string t = a + a;

在t中查找b，用find与string::npos判断；为什么两份就够，见下面的知识补充。

知识补充：为什么拼接两份就够了

成环以后，走过末尾，就会回到开头。

把原串再接一份，第二份的开头，就接在第一份的末尾后面。

例如 AABCD 拼成 AABCDAABCD，跨过首尾的 CDAA 就连续出现了。

设长串长度为 \(n\)，短串长度不超过 \(n\)。

从第一份的任意位置出发，最多再读 \(n\) 个字符，两份的长度就足够了。

所以，环上跨过首尾的匹配，可以变成拼接串里的普通子串匹配。

常见错误

循环移动不等于任意打乱字符。

普通查找失败，不代表跨过首尾也找不到。

自测

输入：AABCD CDAA → 预期输出：true

输入：abc d → 预期输出：false

自己试试：自己选一个长串，从末尾取几个字符，再接上开头的几个字符，组成短串。

只把长串循环移动一位，包含关系应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    if (a.size() < b.size()) swap(a, b);
    string t = a + a;

    if (t.find(b) != string::npos) cout << "true";
    else cout << "false";

    return 0;
}

1839：【05NOIP提高组】谁拿了最多奖学金 ¶

提示 1：先只给一个人算钱

一个人同时满足两条条件，奖金是二选一，还是都能拿？

先让个人奖金now = 0，不要急着找全班最高。

提示 2：五项奖励分别判断

期末均分存入pingjun、论文数存入lunwen，其中一项是：

if (pingjun > 80 && lunwen >= 1) now += 8000;

照题面补其余四项，用独立的if；平均分恰好80能拿这一项吗？

提示 3：个人算完再比较

maxn初值为-1，top记录姓名；当前姓名为s：

if (now > maxn) {
    maxn = now;
    top = s;
}

另用sum累加每个人的奖金；同奖金额时为什么不写>=？

常见错误

不能用 else if 把奖项变成只能选一种。

最高奖金并列时，保留先输入的人。

自测

输入：

2
Alice 90 81 Y N 1
Bob 91 81 N Y 1

预期输出：

Bob
15000
27850

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
string top;
int maxn = -1;
int sum;

int main() {
    cin >> n;
    while (n--) {
        string s;
        int pingjun, pingyi;
        char ganbu, xibu;
        int lunwen;
        cin >> s >> pingjun >> pingyi >> ganbu >> xibu >> lunwen;

        int now = 0;
        if (pingjun > 80 && lunwen >= 1) now += 8000;
        if (pingjun > 85 && pingyi > 80) now += 4000;
        if (pingjun > 90) now += 2000;
        if (pingjun > 85 && xibu == 'Y') now += 1000;
        if (pingyi > 80 && ganbu == 'Y') now += 850;

        if (now > maxn) {
            maxn = now;
            top = s;
        }

        sum += now;
    }

    cout << top << '\n' << maxn << '\n' << sum;

    return 0;
}

1129：统计数字字符个数 ¶

提示 1：数的是字符，不是整数

在A12 3!里，把数字字符逐个圈出，一共几个？

整行读入s，计数cnt从0开始。

提示 2：用字符范围判断

if (s[i] >= '0' && s[i] <= '9') cnt++;

补上遍历；为什么这里比较的是'0'，不是整数0？

常见错误

字符界限要带单引号。

读整行，别漏掉空格后面的数字。

自测

输入：A0 b12! 9 → 预期输出：4

输入：abc ! → 预期输出：0

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    int cnt = 0;
    for (int i = 0, len = (int)s.size(); i < len; i++)
        if (s[i] >= '0' && s[i] <= '9')
            cnt++;

    cout << cnt;

    return 0;
}

1130：找第一个只出现一次的字符 ¶

提示 1：先别见到一次就输出

读abac到第二个字符时，能确定b以后不会再出现吗？

先统计完整个串，再决定答案。

提示 2：把字母放进26个计数格

全局cnt[]初值为0，小写字母用s[i] - 'a'变成0到25：

cnt[s[i] - 'a']++;

第二遍按原字符串顺序找计数为1的字符，为什么不能按字母表顺序找？

提示 3：找到第一个就结束

输出答案后可以直接return 0;。

只有整串找完仍没找到，才输出no；想想它应放在循环内还是外。

常见错误

不能边统计边认定只出现一次，后面可能还有。

没有符合项时输出 no。

自测

输入：abac → 预期输出：b

输入：aabb → 预期输出：no

自己试试：自己造一个字符串，让第一个字符只出现一次。

只在末尾再添一个相同字符，原来的答案还能保留吗？

方法一：先计数再按原序查找

#include <bits/stdc++.h>

using namespace std;

const int N = 30, M = 1e5 + 10;

int cnt[N]; //0...25
char s[M];

int main() {
    scanf("%s", s);
    int len = strlen(s);

    for (int i = 0; i < len; i++)
        cnt[s[i] - 'a']++;

    for (int i = 0; i < len; i++)
        if (cnt[s[i] - 'a'] == 1) {
            cout << s[i];

            return 0;
        }

    cout << "no";

    return 0;
}

方法二：双层循环比较（拓展）

只用于短串练习，最坏需要\(O(n^2)\)次比较，不作为长串的提交版本。

例如前半段全是a、后半段全是b，检查后半段时会反复扫过前面的a。

方法一只扫描两遍，长串也应优先用它。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;

    for (int i = 0, len = s.size(); i < len; i++) {
        bool flag = false;
        for (int j = 0; j < len; j++)
            if (s[j] == s[i] && i != j) {
                flag = true;
                break;
            }

        if (!flag) {
            cout << s[i];

            return 0;
        }
    }

    cout << "no";

    return 0;
}

1131：基因相关性 ¶

提示 1：先算匹配比例

AC和AT对应位置相同几个，比例是多少？

阈值恰好为0.5时，应输出什么？

提示 2：逐位计数再比较

两串存入s1、s2，长度为len，cnt从0开始：

if (s1[i] == s2[i]) cnt++;

补循环后用1.0 * cnt / len >= limit判断，其中limit表示阈值，也就是匹配比例需要达到的下限。

常见错误

第一个输入是小数阈值，limit要定义成double，不能用int。

例如输入0.8，cin >> limit若读入的是int，只会读走0，留下.8，后面的字符串也会读错。

用浮点除法，不乘 100。

比较对应位置，不是每种字母的总数量。

自测

输入：0.5 AC AT → 预期输出：yes

输入：0.8 AC AT → 预期输出：no

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    double limit;
    cin >> limit;

    string s1, s2;
    cin >> s1 >> s2;

    int len = (int)s1.size(), cnt = 0;
    for (int i = 0; i < len; i++)
        if (s1[i] == s2[i]) cnt++;

    if (1.0 * cnt / len >= limit) cout << "yes";
    else cout << "no";

    return 0;
}

1132：石头剪子布 ¶

提示 1：先划掉平局

把玩家一可能出的三种手势写成三行，每行写出它能赢谁。

平局先判断，剩下只需列玩家一获胜的三种组合。

提示 2：先写一种获胜组合

当前手势存入字符串a、b：

a == "Rock" && b == "Scissors"

仿照它写另两种，用||连接；既不平局、玩家一也没赢，剩下是谁赢？

提示 3：方法二，把手势排成一个圈

给石头Rock编号0，剪刀Scissors编号1，布Paper编号2。

0赢1，1赢2，2又赢0，正好绕一圈。

如果玩家一的编号是x，它能赢的编号就是(x + 1) % 3。

代入0、1算一下，再试试2：(2 + 1) % 3是不是回到了0？

提示 4：先把字符串换成编号

方法二中，仍用a、b读入手势，下面先转换玩家一的手势：

int x;
if (a == "Rock") x = 0;
else if (a == "Scissors") x = 1;
else x = 2;

玩家二的编号存入y，你来补同样的转换。

先判断x == y是平局，再用(x + 1) % 3 == y判断玩家一获胜，剩下就是玩家二获胜。

常见错误

单词和输出的大小写按题目写。

每轮独立判断，不能沿用上一轮状态。

方法二的编号顺序要和公式对应，不能换了编号，还照搬原来的判断。

自测

输入：

4
Rock Scissors
Paper Paper
Scissors Rock
Paper Rock

预期输出：

Player1
Tie
Player2
Player1

方法一：直接判断胜负组合

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;

        string ret;
        if (a == b) ret = "Tie";
        else if ((a == "Rock" && b == "Scissors") ||
                 (a == "Scissors" && b == "Paper") ||
                 (a == "Paper" && b == "Rock")) ret = "Player1";
        else ret = "Player2";

        cout << ret << '\n';
    }

    return 0;
}

方法二：整数编码与循环关系

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string a, b;
        cin >> a >> b;

        int x, y;
        if (a == "Rock") x = 0;
        else if (a == "Scissors") x = 1;
        else x = 2;

        if (b == "Rock") y = 0;
        else if (b == "Scissors") y = 1;
        else y = 2;

        string ret;
        if (x == y) ret = "Tie";
        else if ((x + 1) % 3 == y) ret = "Player1";
        else ret = "Player2";

        cout << ret << '\n';
    }

    return 0;
}

方法三：按首字母分类判断

#include <bits/stdc++.h>

using namespace std;

string s1, s2;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a = 0, b = 0;
        cin >> s1 >> s2;
        if (s1[0] == 'R') {
            if (s2[0] == 'S') a++;
            else if (s2[0] == 'P') b++;
        }

        if (s1[0] == 'P') {
            if (s2[0] == 'R') a++;
            else if (s2[0] == 'S') b++;
        }

        if (s1[0] == 'S') {
            if (s2[0] == 'P') a++;
            else if (s2[0] == 'R') b++;
        }

        if (a == b) cout << "Tie";
        if (a > b) cout << "Player1";
        if (a < b) cout << "Player2";
        cout << '\n';
    }

    return 0;
}

1133：输出亲朋字符串 ¶

提示 1：先确定最后一位的邻居

对012，依次配对0和1、1和2，最后2该和谁配？

提示 2：旧字符别提前改掉

先用getline(cin, s)读完整行，长度记为len，另用空串ans存结果：

int sum = s[i] + s[(i + 1) % len];
ans += (char)sum;

自己算一下最后一个下标(i + 1) % len；如果直接改s[i]，最后一对还取得到原来的首字符吗？

常见错误

直接输出编码和，会显示整数。

空格也参与编码，不能用cin >> s只读一个单词。

相加得到的字符不一定是字母，不要自行修改结果。

自测

输入：012 → 预期输出：acb

输入：11 → 预期输出：bb

输入：0 1 → 预期输出：PQa

自己试试：自己造一个两位字符串，先算出两个输出字符。

只交换输入中的两个字符，输出应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s, ans;
    getline(cin, s);
    int len = (int)s.size();
    for (int i = 0; i < len; i++) {
        int sum = s[i] + s[(i + 1) % len];
        ans += (char)sum;
    }

    cout << ans;

    return 0;
}

1134：合法C标识符查 ¶

提示 1：先把首位单独看

a1和1a都只含字母、数字，为什么只有一个合法？

写下首位允许的字符，再给后续位置补上数字。

提示 2：一个非法字符就够判错

读入整行s，逐位取char c = s[i]，分别判断letter是否英文字母、digit是否数字。

letter || c == '_' || (i > 0 && digit)

这是当前位置合法的条件；若不满足，就把合法标记改为false，后面的字符能把它改回来吗？

常见错误

空格也不合法，要检查整行。

本题只按题面给出的字符规则检查，不另加关键字判断。

自测

输入：_a1 → 预期输出：yes

输入：1abc → 预期输出：no

输入：ab cd → 预期输出：no

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    bool valid = !s.empty();
    for (int i = 0; i < (int)s.size(); i++) {
        char c = s[i];
        bool letter = (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
        bool digit = (c >= '0' && c <= '9');
        if (!(letter || c == '_' || (i > 0 && digit))) valid = false;
    }

    if (valid) cout << "yes";
    else cout << "no";

    return 0;
}

1135：配对碱基链 ¶

提示 1：先写配对表

A配T，C配G，反过来各配什么？

拿ATCG逐位写出结果。

提示 2：一位只能替换一次

if (s[i] == 'A') s[i] = 'T';
else if (s[i] == 'T') s[i] = 'A';

自己补C、G两个分支；如果用两个独立的if，刚改成的T会不会又被改回去？

常见错误

用互斥的分支。

独立 if 连续修改，可能把刚换好的字符又换回去。

自测

输入：ATCG → 预期输出：TAGC

输入：AAAA → 预期输出：TTTT

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == 'A') s[i] = 'T';
        else if (s[i] == 'T') s[i] = 'A';
        else if (s[i] == 'C') s[i] = 'G';
        else if (s[i] == 'G') s[i] = 'C';
    }

    cout << s;

    return 0;
}

1136：密码翻译 ¶

提示 1：先留出两个特殊字母

a后移一位是b，z后移应该回到哪里？

把Z也写出来，再决定普通字母的处理范围。

提示 2：普通字母和末尾分开处理

if (s[i] == 'z') s[i] = 'a';
else if (s[i] == 'Z') s[i] = 'A';

再补普通大小写字母的后移分支，空格、数字、标点保持原样。

常见错误

只改字母，其他字符不动。

不能让 z、Z 直接加一变成标点。

自测

输入：aZ z9! → 预期输出：bA a9!

方法一：处理普通字母与边界字母

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    getline(cin, s);

    for (int i = 0, len = s.size(); i < len; i++) {
        if ((s[i] >= 'a' && s[i] <= 'y') || (s[i] >= 'A' && s[i] <= 'Y'))
            s[i]++;
        else if (s[i] == 'z') s[i] = 'a';
        else if (s[i] == 'Z') s[i] = 'A';
    }

    cout << s;

    return 0;
}

方法二：字母编号取余

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);

    for (int i = 0, len = (int)s.size(); i < len; i++) {
        if (s[i] >= 'a' && s[i] <= 'z') s[i] = 'a' + ((s[i] - 'a') + 1) % 26;
        if (s[i] >= 'A' && s[i] <= 'Z') s[i] = 'A' + ((s[i] - 'A') + 1) % 26;
    }

    cout << s;

    return 0;
}

1137：加密的病历单 ¶

提示 1：拆成三次手算

用aZ依次做后移三位、反转、大小写互换，先写出最终结果。

不要一次心算三件事，先核对每一步。

提示 2：让后移能绕回开头

当前小写字符记为c：

s[i] = 'a' + (c - 'a' + 3) % 26;

先变成0到25的编号，再后移、取余；仿照它补大写字符。

提示 3：字符处理和整串处理分开

每个字符还要互换大小写，整串最后调用reverse(s.begin(), s.end());。

逐字符变换可以先做，反转可以后做；用刚才的aZ检查是否与手算一致。

常见错误

大小写各自在自己的范围内循环。

反转的是整个串，不是单独一组字母。

自测

输入：abcXYZ → 预期输出：cbaFED

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    cin >> s;

    int len = s.size();
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (c >= 'a' && c <= 'z') {
            s[i] = 'a' + (c - 'a' + 3) % 26;
            s[i] -= 'a' - 'A';
        }
        else {
            s[i] = 'A' + (c - 'A' + 3) % 26;
            s[i] += 'a' - 'A';
        }
    }

    reverse(s.begin(), s.end());
    cout << s;

    return 0;
}

1138：将字符串中的小写字母转换成大写字母 ¶

提示 1：只圈出要改变的字符

对a B z9!，先圈小写字母，其余字符都要保留。

提示 2：先判断再换算

if (s[i] >= 'a' && s[i] <= 'z') s[i] -= 'a' - 'A';

读入整行并补遍历；如果去掉条件，大写字母和数字会怎样？

常见错误

不能对所有字符统一减编码差。

空格、数字和标点应保持原样。

自测

输入：a B z9! → 预期输出：A B Z9!

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;

    getline(cin, s);

    for (int i = 0, len = s.size(); i < len; i++)
        if (s[i] >= 'a' && s[i] <= 'z') s[i] -= 'a' - 'A';

    cout << s;

    return 0;
}

1139：整理药名 ¶

提示 1：首位和其余位置分开

把iBUPROFEN整理成首字母大写、其余小写。

首位已经大写时，需要再改变吗？

提示 2：第二段循环从哪里开始

单个药名已读入s，先把s[0]中的小写转大写。

后续位置只改大写字母：

if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 'a' - 'A';

这段循环要从下标1开始；在外面再套读取n个药名的循环。

常见错误

只有一个字母也要处理。

已经符合要求的字母，不必再加减编码差。

自测

输入：

2
aspirin
IbUPROfen

预期输出：

Aspirin
Ibuprofen

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
string s;

int main() {
    cin >> n;
    while (n--) {
        cin >> s;

        if (s[0] >= 'a' && s[0] <= 'z') s[0] -= 'a' - 'A';
        for (int i = 1, len = s.size(); i < len; i++)
            if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 'a' - 'A';

        cout << s;
        cout << '\n';
    }

    return 0;
}

1140：验证子串 ¶

提示 1：包含要求连续

ac的字母都在abc里，它是abc的子串吗？

再试两串完全相同的情况，也算包含。

提示 2：先只判断一个方向

对已读入的两个字符串s、s2：

s.find(s2) != string::npos

它表示在s里找到s2；这个方向没找到，还要不要试另一个方向？

输出时分清谁是子串、谁包含它，别把两者写反。

知识补充：find 的返回值

a.find(b) 查找b在a中第一次出现的位置。

找不到时返回 string::npos，因此用 != string::npos 判断找到。

常见错误

只匹配到长串末尾、不够短串全长，不算成功。

两个串相等也算包含。

自测

输入：abc bc → 预期输出：bc is substring of abc

输入：abc bcd → 预期输出：No substring

输入：abc abc → 预期输出：abc is substring of abc

方法一：find 函数

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s, s2;
    cin >> s >> s2;

    if (s2.size() < s.size()) {
        if(s.find(s2) != string::npos) cout << s2 << ' ' << "is substring of" << ' ' << s;
        else cout << "No substring";
    }
    else {
        if(s2.find(s) != string::npos) cout << s << ' ' << "is substring of" << ' ' << s2;
        else cout << "No substring";
    }

    return 0;
}

方法二：逐个起点手动匹配

#include <bits/stdc++.h>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    if (a.size() < b.size()) swap(a, b);
    int n = (int)a.size(), m = (int)b.size();
    bool found = false;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && a[i + j] == b[j]) j++;
        if (j == m) {
            found = true;
            break;
        }
    }

    if (found) cout << b << " is substring of " << a;
    else cout << "No substring";

    return 0;
}

1141：删除单词后缀 ¶

提示 1：只检查单词末尾

flower的er在末尾，error的er在开头，哪一个能删？

若单词只有一个字母，访问倒数第三位会怎样？

提示 2：先保护长度，再比较

长度记为len，检查三字母后缀ing：

len >= 3 && s[len - 3] == 'i' && s[len - 2] == 'n' && s[len - 1] == 'g'

匹配后用s.erase(len - 3);；仿照它补er和ly，只删除一次。

知识补充：compare 与 erase

s.compare(pos, count, text) 比较指定片段与 text，相等时返回 0。

s.erase(pos) 删除从 pos 开始到末尾的部分。

常见错误

先检查长度，再访问倒数位置。

删除后别再用旧长度继续访问，也别重复删除。

自测

输入：singing → 预期输出：sing

输入：fly → 预期输出：f

输入：a → 预期输出：a

输入：flower → 预期输出：flow

自己试试：自己选一个带指定后缀的单词，先写出删除结果。

只在单词末尾再添一个字母，让它不再带指定后缀，还应该删除吗？

方法一：下标比较后缀

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int len = (int)s.size();
    if (len >= 3 && s[len - 3] == 'i' && s[len - 2] == 'n' && s[len - 1] == 'g') {
        s.erase(len - 3);
    } else if (len >= 2 && ((s[len - 2] == 'e' && s[len - 1] == 'r') ||
                            (s[len - 2] == 'l' && s[len - 1] == 'y'))) {
        s.erase(len - 2);
    }

    cout << s;

    return 0;
}

方法二：compare 函数

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int len = (int)s.size();
    if (len >= 3 && s.compare(len - 3, 3, "ing") == 0) s.erase(len - 3);
    else if (len >= 2 && (s.compare(len - 2, 2, "er") == 0 ||
                          s.compare(len - 2, 2, "ly") == 0)) s.erase(len - 2);

    cout << s;

    return 0;
}

1142：单词的长度 ¶

提示 1：先跨过空格再数单词

给I love Cpp划出三个单词，连续空格要不要算空单词？

提示 2：用两个下标夹住一词

整行s长为len，i指向未处理位置，先写：

while (i < len && s[i] == ' ') i++;

若已到末尾就停止；否则令j = i，让j走到空格或末尾。

提示 3：长度和下一次起点

单词占下标i到j - 1，长度是j - i。

i = j;

输出长度后移到这里再继续；逗号只加在第二个及以后的长度前。

常见错误

跳过空格时也要检查下标。

逗号只放在两项之间，首尾都不多加。

自测

输入： I love Cpp → 预期输出：1,4,3

输入：word → 预期输出：4

方法一：整行扫描

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    getline(cin, s);
    int len = (int)s.size(), i = 0;
    bool first = true;
    while (i < len) {
        while (i < len && s[i] == ' ') i++;
        if (i == len) break;
        int j = i;
        while (j < len && s[j] != ' ') j++;

        if (!first) cout << ',';
        cout << j - i;
        first = false;
        i = j;
    }

    return 0;
}

方法二：逐词读取

cin >> s会跳过连续空白，每次读到一个单词。

终端里回车不代表输入结束，结束输入的操作见本章2034。

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s;
    bool flag = false;
    while (cin >> s) {
        if (flag) cout << ',';
        flag = true;

        int len = s.size();
        cout << len;
    }

    return 0;
}

1143：最长最短单词 ¶

提示 1：先圈出完整单词

对aa, bbb c,dddd，空格和逗号都能分开单词。

最长、最短各是哪一个？同长度时保留先出现的。

提示 2：从起点走到分隔处

整行长为len，i已经指向单词首字符，先令j = i。

while (j < len && s[j] != ' ' && s[j] != ',') j++;
string word = s.substr(i, j - i);

下次从j接着处理，遇到分隔符先跳过。

提示 3：两场擂台分开打

longest、shortest初始为空，取出word后：

if (shortest.empty() || word.size() < shortest.size()) shortest = word;

仿照它更新最长词；相同长度不更新，才能留下先出现的词。

常见错误

逗号不属于单词。

相同长度若继续更新，会留下后出现的词。

自测

输入：aa, bbb c,dddd，预期输出：

dddd
c

输入：aa bb ccc，预期输出：

ccc
aa

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s, longest, shortest;
    getline(cin, s);
    int len = (int)s.size();
    for (int i = 0; i < len; ) {
        if (s[i] == ' ' || s[i] == ',') {
            i++;
            continue;
        }
        int j = i;
        while (j < len && s[j] != ' ' && s[j] != ',') j++;
        string word = s.substr(i, j - i);
        if (longest.empty() || word.size() > longest.size()) longest = word;
        if (shortest.empty() || word.size() < shortest.size()) shortest = word;
        i = j;
    }

    cout << longest << '\n' << shortest;

    return 0;
}

1144：单词翻转 ¶

提示 1：空格留在原地

把I love Cpp中的单词各自倒过来，两个连续空格应该还在吗？

提示 2：遇到单词才收集

整行s长为len，i指向一个非空格字符；令j = i，空串temp接住这个词：

while (j < len && s[j] != ' ') temp += s[j++];
reverse(temp.begin(), temp.end());

输出temp；遇到空格则直接原样输出，不放入单词。

提示 3：不要重复处理同一词

收集后j指向空格或末尾；若外层for还有i++，这里应先写i = j - 1;。

用没有尾部空格的word走一遍，检查最后一个词能否输出。

常见错误

别反转整句话，也别把连续空格重新拼成一个。

末尾没有空格时，也要处理最后一个单词。

自测

输入：I love Cpp → 预期输出：I evol ppC

输入： word → 预期输出： drow

自己试试：自己写一句带连续空格的话，最后一个单词后不留空格。

只在句末补一个空格，最后一个单词的翻转结果应不应该变？

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    getline(cin, s);
    for (int i = 0, len = s.size(); i < len; i++) {
        if (s[i] == ' ') {
            cout << s[i];
            continue;
        }

        int j = i;
        string temp;
        while (j < len && s[j] != ' ') temp += s[j++];
        reverse(temp.begin(), temp.end());
        cout << temp;
        i = j - 1;
    }

    return 0;
}

1145：字符串p型编码 ¶

提示 1：先在纸上分组

先把111221中连续相同的字符圈成一组。

三个1编码成31，你能接着写出后面两组的编码吗？

最后一个1能和开头的三个1合并吗？

提示 2：这一段，要记住什么

下面沿着last、cnt的写法试一遍。

读入非空字符串s后，先把第一个字符算进当前段：

char last = s[0];
int cnt = 1;

last记这一段的字符，cnt记这一段已经有几个字符。

接下来从下标1往后看，遇到相同字符时：

if (s[i] == last) {
    cnt++;
}

用111221手算到第三个1，此时last和cnt各是多少？

提示 3：读到不同字符，先做什么

接着读到2，上一段结束了，可以输出：

cout << cnt << last;

如果先把last改成'2'，这一句会把上一段错编码成什么？

输出后，新的一段从眼前这个字符开始：

last = s[i];
cnt = 1;

把这些语句放进else，自己接着处理剩下的字符。

提示 4：最后一段，谁来提醒它结束

走到111221末尾时，最后一段后面还有不同字符吗？

再单独试一下输入7：循环一次也不执行，还应该输出17。

想想这句该放在循环里面，还是循环结束后：

cout << cnt << last;

关上提示，把初始化、循环和最后一次输出连起来写一遍。

常见错误

换段时先输出旧段，再修改last，新段的cnt从1开始。

如果少了最后一段，先用7检查循环结束后的输出。

寻找段尾的写法，要先判断j < len再访问s[j]。

自测

输入：1112231 → 预期输出：31221311

输入：7 → 预期输出：17

输入：111 → 预期输出：31

输入：1121 → 预期输出：211211

自己试试：自己造一串相同的数字，先写出编码。

只把中间一个数字换成别的数字，会分成几段？

方法一：寻找每段的末尾

#include <bits/stdc++.h>

using namespace std;

string s;

int main() {
    cin >> s;
    for (int i = 0, len = s.size(); i < len; i++) {
        int cnt = 0, j = i;
        while (j < len && s[j] == s[i]) cnt++, j++;

        cout << cnt << s[i];
        i = j - 1;
    }

    return 0;
}

方法二：用last和cnt记录连续段

last记录当前这一段的字符，cnt记录已经连续出现了多少次。

遇到不同字符，先输出上一段，再开始新的一段。

循环结束后，别漏掉最后一段。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;

    char last = s[0];
    int cnt = 1;
    for (int i = 1, len = s.size(); i < len; i++) {
        if (s[i] == last) {
            cnt++;
        } else {
            cout << cnt << last;
            last = s[i];
            cnt = 1;
        }
    }

    cout << cnt << last;

    return 0;
}

1146：判断字符串是否为回文 ¶

提示 1：先找一对不同的字符

对abca，第一对首尾相同，能立刻判断是回文吗？

这题没有末尾句点，不要删字符。

提示 2：一对通过才继续往里走

非空字符串读入s，设l = 0、r = (int)s.size() - 1。

if (s[l] != s[r]) break;
l++;
r--;

放进while (l < r)；退出后若l < r，说明在哪一步停住了？

常见错误

一个字符也是回文。

不要删掉最后一位正文，输出小写 yes、no。

自测

输入：abba → 预期输出：yes

输入：abca → 预期输出：no

输入：a → 预期输出：yes

方法一：双下标比较

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (s[l] == s[r]) l++, r--;
        else break;
    }

    if (l < r) cout << "no";
    else cout << "yes";

    return 0;
}

方法二：反转后比较

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;

    string s2 = s;
    reverse(s.begin(), s.end());

    if (s == s2) cout << "yes";
    else cout << "no";

    return 0;
}

1147：最高分数的学生姓名 ¶

提示 1：姓名跟着分数走

先看80 Li、95 Wang，第二个人分数更高，要改哪两项记录？

提示 2：相同最高分先别换人

成绩非负，先设maxn = -1；每次读入分数x和姓名s：

if (x > maxn) {
    maxn = x;
    ans = s;
}

补上读入循环，最后只输出姓名；再添一名95分学生，谁应该留下？

常见错误

输入是分数在前、姓名在后。

用 >= 会覆盖并列时先输入的学生。

自测

输入：3 90 Amy 95 Bob 95 Cara → 预期输出：Bob

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;

    int maxn = -1;
    string ans;

    while (n--) {
        int x;
        string s;
        cin >> x >> s;

        if (x > maxn) {
            maxn = x;
            ans = s;
        }
    }

    cout << ans;

    return 0;
}

1148：连续出现的字符 ¶

提示 1：一段够长就符合

对abbbcc，设k = 3，先圈出符合条件的连续段。

若这一段有4个b，是否也包含连续3个b？

提示 2：先量出这一段的长度

i指向一段开头，len是字符串长度，令j = i：

while (j < len && s[j] == s[i]) j++;
int cnt = j - i;

当cnt >= k时输出s[i]并停止；没有达到就跳过整段，别重复从段中间数。

提示 3：别在中途宣布找不到

用标记记录是否找到，所有段都检查完后，才决定要不要输出No。

用k = 1试一下，第一段应该怎样处理？

常见错误

末尾一段也要检查。

处理完一段要跳过，k 为 1 时第一个字符就符合。

自测

输入：3 abbbcc → 预期输出：b

输入：4 aaabb → 预期输出：No

输入：1 abc → 预期输出：a

自己试试：自己造一个字符串，让某段字符恰好连续出现 \(k\) 次。

只把这一段中的一个字符换掉，它还一定能满足要求吗？

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int k;
    string s;

    cin >> k >> s;

    bool flag = false;
    for (int i = 0, len = (int)s.size(); i < len; i++) {
        int j = i;
        while (j < len && s[j] == s[i]) j++;

        int cnt = j - i;
        if (cnt >= k) {
            flag = true;
            cout << s[i];
            break;
        }
        i = j - 1;
    }

    if (!flag) cout << "No";

    return 0;
}

1149：最长单词2 ¶

提示 1：末尾句点不是单词

对I love coding.，先把三个单词圈出，句点不要圈进去。

两个最长词一样长时，要留下先出现的。

提示 2：找到边界再取出单词

i指向单词开头，j从i向后走，遇到空格、句点或字符串末尾停下。

string word = s.substr(i, j - i);

处理完令i = j，下一轮跳过分隔符。

提示 3：只在严格更长时替换

ans初始为空：

if (word.size() > ans.size()) ans = word;

试着把>改成>=，用aa bb c.检查答案会变成谁。

常见错误

只删句末的点，别把每个单词的末位都删掉。

最后一个单词也要参与比较。

自测

输入：I love coding. → 预期输出：coding

输入：aa bb c. → 预期输出：aa

方法一：扫描单词边界

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s, ans;
    getline(cin, s);
    int len = (int)s.size();
    for (int i = 0; i < len; ) {
        if (s[i] == ' ' || s[i] == '.') {
            i++;
            continue;
        }
        int j = i;
        while (j < len && s[j] != ' ' && s[j] != '.') j++;
        string word = s.substr(i, j - i);
        if (word.size() > ans.size()) ans = word;
        i = j;
    }

    cout << ans;

    return 0;
}

方法二：逐词读取

#include <bits/stdc++.h>

using namespace std;

int main() {
    string word, ans;
    while (cin >> word) {
        bool last = !word.empty() && word.back() == '.';
        if (last) word.pop_back();
        if (word.size() > ans.size()) ans = word;
        if (last) break;
    }

    cout << ans;

    return 0;
}

方法三：逐字符累积

#include <bits/stdc++.h>

using namespace std;

string ret, t;

int main() {
    string s;
    getline(cin, s);

    for (int i = 0, len = s.size(); i < len; i++) {
        if (s[i] != ' ' && s[i] != '.') t += s[i];
        else {
            if (t.size() > ret.size()) ret = t;
            t.clear();
        }
    }

    if (t.size() > ret.size()) ret = t;

    cout << ret;

    return 0;
}

第五章 数组¶

基础数学知识¶

第一节 一维数组¶

第二节 二维数组¶

第三节 字符类型和字符数组¶

第五章数组¶

第一节一维数组¶

第二节二维数组¶

第三节字符类型和字符数组¶