2026年7月24日竞赛题解

深圳 -周建政

2026-07-24 20:15:41

发布于：广东

47阅读

0回复

0点赞

使用说明

本题解面向刚开始学习算法的学生，代码统一遵循以下要求：

可以使用 sort、lower_bound 和 upper_bound；
所有代码均采用 C++17。

1. 一无所知的 IKUN

题目分析

题目会输入一个字符串 S，我们只需要按照固定格式输出：

我不知道什么是S，请不要打扰我！

这里的 S 要替换成实际输入的内容。

由于字符串很短，可以直接使用字符数组保存。

解题步骤

读入字符串 S。
输出固定文字。
在中间输出 S。

复杂度分析

设字符串长度为 $L$ 。

时间复杂度： $O(L)$
空间复杂度： $O(L)$

参考代码

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

int main() {
    char s[100];

    cin >> s;

    cout << "我不知道什么是" << s << "，请不要打扰我！";

    return 0;
}

2. 小明爱喝可乐 2

题目分析

第 $1$ 天喝 $1$ 瓶，第 $2$ 天喝 $2$ 瓶，直到第 $n$ 天喝 $n$ 瓶。

因此答案为：

$1+2+3+\cdots+n$

对于刚学习循环的同学，可以使用 for 循环依次累加。

解题步骤

定义变量 sum，初始值为 0。
从 1 枚举到 n。
每次把当前天数加入 sum。
输出 sum。

复杂度分析

时间复杂度： $O(n)$
空间复杂度： $O(1)$

参考代码

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

int main() {
    int n;
    int sum = 0;

    cin >> n;

    for (int i = 1; i <= n; i++) {
        sum += i;
    }

    cout << sum;

    return 0;
}

3. 快递位置查询

题目分析

所有快递编号已经按照升序排列，并且编号互不相同。

对于每次查询，可以使用 lower_bound 找到数组中第一个大于等于 target 的位置。

找到位置后，还要判断该位置上的数字是否真的等于 target：

如果相等，输出位置；
如果不相等，说明数组中没有这个编号，输出 -1。

数组下标从 1 开始，因此数组存储范围使用 a[1] 到 a[n]。

`lower_bound` 的含义

lower_bound(a + 1, a + n + 1, target)

返回数组中第一个大于等于 target 的位置。

解题步骤

对于每次查询：

使用 lower_bound 查找第一个大于等于 target 的位置。
判断该位置是否超过数组范围。
判断该位置上的值是否等于 target。
存在则输出下标，否则输出 -1。

复杂度分析

每次查询时间复杂度： $O(\log n)$
总时间复杂度： $O(n+Q\log n)$
空间复杂度： $O(n)$

参考代码

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

const int N = 200000 + 5;

int a[N];

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

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

    while (Q--) {
        int target;
        cin >> target;

        int pos = lower_bound(a + 1, a + n + 1, target) - a;

        if (pos <= n && a[pos] == target) {
            cout << pos << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

4. 查找最后一个小于等于目标的数

题目分析

我们需要找到最后一个满足下面条件的位置：

$a_i\leq target$

upper_bound 可以找到第一个大于 target 的位置。

因此，它的前一个位置就是最后一个小于等于 target 的位置。

例如：

数组：1 3 3 5 8
目标：3

第一个大于 3 的数字是 5，位置为 4。
所以最后一个小于等于 3 的位置是 4-1=3。

特殊情况

如果 upper_bound 返回数组第一个位置，说明所有数字都大于 target。

按照题目要求，此时输出 n+1。

解题步骤

对于每次查询：

使用 upper_bound 找到第一个大于 target 的位置。
将位置减去 1。
如果结果为 0，说明不存在符合要求的数字，输出 n+1。
否则输出这个位置。

复杂度分析

每次查询时间复杂度： $O(\log n)$
总时间复杂度： $O(n+Q\log n)$
空间复杂度： $O(n)$

参考代码

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

const int N = 200000 + 5;

int a[N];

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

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

    while (Q--) {
        int target;
        cin >> target;

        int pos = upper_bound(a + 1, a + n + 1, target) - a - 1;

        if (pos == 0) {
            cout << n + 1 << '\n';
        } else {
            cout << pos << '\n';
        }
    }

    return 0;
}

5. 查找最后一个等于目标的数

题目分析

要找到最后一个等于 target 的位置，可以先使用 upper_bound 找到第一个大于 target 的位置。

这个位置的前一个位置，可能就是最后一个等于 target 的位置。

但是还需要进行判断，因为数组中可能根本没有 target。

例如：

数组：3 8 8 8 15
目标：8

第一个大于 8 的数字是 15，位置为 5。
因此最后一个 8 的位置是 5-1=4。

解题步骤

对于每次查询：

使用 upper_bound 找到第一个大于 target 的位置。
将位置减去 1。
判断该位置是否合法，并且该位置上的数字是否等于 target。
如果相等，输出位置；否则输出 -1。

复杂度分析

每次查询时间复杂度： $O(\log n)$
总时间复杂度： $O(n+Q\log n)$
空间复杂度： $O(n)$

参考代码

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

const int N = 100000 + 5;

int a[N];

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

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

    while (Q--) {
        int target;
        cin >> target;

        int pos = upper_bound(a + 1, a + n + 1, target) - a - 1;

        if (pos >= 1 && a[pos] == target) {
            cout << pos << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

    return 0;
}

6. 不同分的人数

题目分析

每次查询给出一个分数 target，要求统计分数不等于 target 的学生人数。

可以先求出分数等于 target 的人数，再用总人数减去它。

即：

$\text{不同分人数} = n-\text{等于 target 的人数}$

对成绩数组排序后：

lower_bound 找到第一个等于 target 的位置；
upper_bound 找到第一个大于 target 的位置。

两者位置之差，就是 target 出现的次数。

解题步骤

读入所有学生成绩。
对成绩数组排序。
对于每次查询：
- 使用 lower_bound 找左边界；
- 使用 upper_bound 找右边界；
- 计算相等人数；
- 用 n 减去相等人数。

复杂度分析

排序时间复杂度： $O(n\log n)$
每次查询时间复杂度： $O(\log n)$
总时间复杂度： $O(n\log n+Q\log n)$
空间复杂度： $O(n)$

参考代码

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

const int N = 100000 + 5;

long long a[N];

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

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

    sort(a + 1, a + n + 1);

    while (Q--) {
        long long target;
        cin >> target;

        int leftPos = lower_bound(a + 1, a + n + 1, target) - a;
        int rightPos = upper_bound(a + 1, a + n + 1, target) - a;

        int equalCount = rightPos - leftPos;

        cout << n - equalCount << '\n';
    }

    return 0;
}

7. 学生信息查询

题目分析

每名学生包含四项信息：

学号；
姓名；
性别；
年龄。

题目需要根据学号查询学生信息。

学号长度可能达到 $20$ ，并且可能有前导零，例如：

02
000123

因此，学号不能使用整数保存，而应使用字符数组保存。

由于查询次数和学生人数都可能达到 $10^5$ ，逐个查找会超时。可以先按照学号排序，再使用二分查找。

本题不使用 map，而是使用：

普通结构体数组保存学生；
sort 按照学号排序；
手写二分查找查询学号。

为什么不能把学号转成整数

学号 02 如果转成整数，会变成 2，前导零会丢失。

而且学号最多有 $20$ 位，可能超过整数能够保存的范围。

所以学号必须作为字符串处理。本题使用字符数组 char id[25] 保存。

字符数组比较

使用：

strcmp(a, b)

比较两个字符数组：

返回值小于 0：a 排在 b 前面；
返回值等于 0：两个字符串相同；
返回值大于 0：a 排在 b 后面。

解题步骤

使用结构体数组保存所有学生。
使用 sort 按照学号从小到大排序。
每次输入一个待查询学号。
在结构体数组中手写二分查找。
找到则输出完整信息，否则输出 No Answer!。

复杂度分析

排序时间复杂度： $O(N\log N)$
每次查询时间复杂度： $O(\log N)$
总时间复杂度： $O(N\log N+Q\log N)$
空间复杂度： $O(N)$

参考代码

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

const int N = 100000 + 5;

struct Student {
    string id;
    char name[50];
    int gender;
    int age;
};

Student stu[N];

bool cmp(const Student &x, const Student &y) {
    return x.id<y.id;
}

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

    for (int i = 1; i <= n; i++) {
        cin >> stu[i].id
            >> stu[i].name
            >> stu[i].gender
            >> stu[i].age;
    }

    sort(stu + 1, stu + n + 1, cmp);

    int Q;
    cin >> Q;

    while (Q--) {
        char target[25];
        cin >> target;

        int left = 1;
        int right = n;
        int answer = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int result = strcmp(stu[mid].id, target);

            if (stu[mid].id== target) {
                answer = mid;
                break;
            }

            if (stu[mid].id>targe) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        if (answer == -1) {
            cout << "No Answer!\n";
        } else {
            cout << stu[answer].id << ' '
                 << stu[answer].name << ' '
                 << stu[answer].gender << ' '
                 << stu[answer].age << '\n';
        }
    }

    return 0;
}

8. A-B 数对

题目分析

题目要求统计满足下面条件的数对数量：

$A-B=C$

把式子移项，可以得到：

$B=A-C$

因此，对于数组中的每一个数 A，只需要统计数组中有多少个数等于 A-C。

因为相同数值出现在不同位置时，要算作不同数对，所以必须统计 A-C 出现了多少次，而不是只判断它是否存在。

可以先对数组排序，然后使用：

upper_bound - lower_bound

计算一个数字出现的次数。

举例说明

数组为：

1 1 2 3

并且 $C=1$ 。

当 $A=2$ 时，需要找 $B=1$ ，数组中有两个 1，贡献 $2$ 对；
当 $A=3$ 时，需要找 $B=2$ ，数组中有一个 2，贡献 $1$ 对。

总答案为 $3$ 。

解题步骤

读入数组并排序。
枚举每一个位置上的数字，将它作为 A。
计算目标值 A-C。
使用 lower_bound 和 upper_bound 统计目标值出现的次数。
将次数累加到答案中。

答案可能很大，必须使用 long long。

复杂度分析

排序时间复杂度： $O(N\log N)$
枚举和查询时间复杂度： $O(N\log N)$
总时间复杂度： $O(N\log N)$
空间复杂度： $O(N)$

参考代码

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

const int N = 100000 + 5;

long long a[N];

int main() {
    int n;
    long long C;

    cin >> n >> C;

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

    sort(a + 1, a + n + 1);

    long long answer = 0;

    for (int i = 1; i <= n; i++) {
        long long target = a[i] - C;

        int leftPos = lower_bound(a + 1, a + n + 1, target) - a;
        int rightPos = upper_bound(a + 1, a + n + 1, target) - a;

        answer += rightPos - leftPos;
    }

    cout << answer;

    return 0;
}

最大性能

题目思路

每件商品包含两个属性：

a：商品价格
b：商品性能

每次询问给出一个预算 val，要求在所有价格不超过 val 的商品中，找到最大的性能值。

解题方法

1. 按价格排序

先将所有商品按照价格从小到大排序。

排序后，价格不超过某个值的商品一定集中在数组前面。

2. 计算前缀最大值

定义：

pre_max[i]

表示前 i 件商品中的最大性能值。

转移公式为：

pre_max[i] = max(pre_max[i - 1], node[i].b);

3. 二分查找

对于每次询问的预算 val，使用二分查找找到最后一个满足：

node[i].a <= val

的位置 inx。

此时，价格不超过 val 的商品范围为 1 到 inx，答案就是：

pre_max[inx]

如果没有任何商品的价格不超过预算，inx 保持为 0，答案为 pre_max[0] = 0。

复杂度分析

排序时间复杂度： $O(n\log n)$
预处理时间复杂度： $O(n)$
每次查询时间复杂度： $O(\log n)$
总时间复杂度： $O(n\log n+q\log n)$
空间复杂度： $O(n)$

参考代码

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

const int N = 2e5 + 10;

struct Node {
    int a, b; // 价格、性能
} node[N];

int pre_max[N];

bool cmp(Node n1, Node n2) {
    return n1.a < n2.a;
}

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

    for (int i = 1; i <= n; i++) {
        cin >> node[i].a >> node[i].b;
    }

    // 按价格从小到大排序
    sort(node + 1, node + n + 1, cmp);

    // 计算前缀最大性能
    for (int i = 1; i <= n; i++) {
        pre_max[i] = max(pre_max[i - 1], node[i].b);
    }

    while (q--) {
        int val;
        cin >> val;

        // 查找最后一个价格小于等于 val 的位置
        int l = 1, r = n;
        int inx = 0;

        while (l <= r) {
            int mid = (l + r) / 2;

            if (node[mid].a <= val) {
                inx = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        cout << pre_max[inx] << '\n';
    }

    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 9

马启腾--坐牢的第8天

/**

```
               _ooOoo_
```
```
              o8888888o
```
```
              88" . "88
```
```
              (| -_- |)
```
```
               O\ = /O
```
```
           ____/`---'\____
```
```
         .   ' \\| |// `.
```
```
          / \\||| : |||// \
```
```
        / _||||| -:- |||||- \
```
```
          | | \\\ - /// | |
```
```
        | \_| ''\---/'' | |
```
```
         \ .-\__ `-` ___/-. /
```
```
      ___`. .' /--.--\ `. . __
```
```
   ."" '< `.___\_<|>_/___.' >'"".
```
```
  | | : `- \`.;`\ _ /`;.`/ - ` : | |
```
```
    \ \ `-. \_ __\ /__ _/ .-` / /
```
-.____-._/.-`__.-'
```
               `=---='
```
```
                拜佛处
```
.............................................

     佛祖保佑             永无BUG

 祝大家考试考好            天天向上

2026-07-24 来自广东

Minecraft（互关）
老师你人真好

2026-07-24 来自广东
1
Minecraft（互关）

2026-07-24 来自广东
0
- Minecraft（互关）
  回复
  Minecraft（互关）
  这是进入集训后的成绩
  
  2026-07-24 来自广东
  0

白宇辰

/**

```
               _ooOoo_
```
```
              o8888888o
```
```
              88" . "88
```
```
              (| -_- |)
```
```
               O\ = /O
```
```
           ____/`---'\____
```
```
         .   ' \\| |// `.
```
```
          / \\||| : |||// \
```
```
        / _||||| -:- |||||- \
```
```
          | | \\\ - /// | |
```
```
        | \_| ''\---/'' | |
```
```
         \ .-\__ `-` ___/-. /
```
```
      ___`. .' /--.--\ `. . __
```
```
   ."" '< `.___\_<|>_/___.' >'"".
```
```
  | | : `- \`.;`\ _ /`;.`/ - ` : | |
```
```
    \ \ `-. \_ __\ /__ _/ .-` / /
```
-.____-._/.-`__.-'
```
               `=---='
```
```
                拜佛处
```
.............................................

     佛祖保佑             永无BUG

 祝大家考试考好            天天向上

2026-07-24 来自广东

碗豆涩搜(饿就吃豌豆)

/**

```
               _ooOoo_
```
```
              o8888888o
```
```
              88" . "88
```
```
              (| -_- |)
```
```
               O\ = /O
```
```
           ____/`---'\____
```
```
         .   ' \\| |// `.
```
```
          / \\||| : |||// \
```
```
        / _||||| -:- |||||- \
```
```
          | | \\\ - /// | |
```
```
        | \_| ''\---/'' | |
```
```
         \ .-\__ `-` ___/-. /
```
```
      ___`. .' /--.--\ `. . __
```
```
   ."" '< `.___\_<|>_/___.' >'"".
```
```
  | | : `- \`.;`\ _ /`;.`/ - ` : | |
```
```
    \ \ `-. \_ __\ /__ _/ .-` / /
```
-.____-._/.-`__.-'
```
               `=---='
```
```
                拜佛处
```
.............................................

     佛祖保佑             永无BUG

 祝大家考试考好            天天向上

2026-07-24 来自广东

Minecraft（互关）

/**
 * _ooOoo_
 * o8888888o
 * 88" . "88
 * (| -_- |)
 *  O\ = /O
 * ___/`---'\____
 * .   ' \\| |// `.
 * / \\||| : |||// \
 * / _||||| -:- |||||- \
 * | | \\\ - /// | |
 * | \_| ''\---/'' | |
 * \ .-\__ `-` ___/-. /
 * ___`. .' /--.--\ `. . __
 * ."" '< `.___\_<|>_/___.' >'"".
 * | | : `- \`.;`\ _ /`;.`/ - ` : | |
 * \ \ `-. \_ __\ /__ _/ .-` / /
 * ======`-.____`-.___\_____/___.-`____.-'======
 * `=---='
 *          .............................................
 *           佛曰：bug泛滥，我已瘫痪！
 *
 *      在有些时候佛祖是帮不了你们的哈哈哈！
 */

2026-07-24 来自广东

碗豆涩搜(饿就吃豌豆)

Minecraft（互关）

/**

```
               _ooOoo_
```
```
              o8888888o
```
```
              88" . "88
```
```
              (| -_- |)
```
```
               O\ = /O
```
```
           ____/`---'\____
```
```
         .   ' \\| |// `.
```
```
          / \\||| : |||// \
```
```
        / _||||| -:- |||||- \
```
```
          | | \\\ - /// | |
```
```
        | \_| ''\---/'' | |
```
```
         \ .-\__ `-` ___/-. /
```
```
      ___`. .' /--.--\ `. . __
```
```
   ."" '< `.___\_<|>_/___.' >'"".
```
```
  | | : `- \`.;`\ _ /`;.`/ - ` : | |
```
```
    \ \ `-. \_ __\ /__ _/ .-` / /
```
-.____-._/.-`__.-'
```
               `=---='
```
```
                拜佛处
```
.............................................

     佛祖保佑             永无BUG

 祝大家考试考好            天天向上

2026-07-24 来自广东

Minecraft（互关）

/**
 *                    _ooOoo_
 *                   o8888888o
 *                   88" . "88
 *                   (| -_- |)
 *                    O\ = /O
 *                ____/`---'\____
 *              .   ' \\| |// `.
 *               / \\||| : |||// \
 *             / _||||| -:- |||||- \
 *               | | \\\ - /// | |
 *             | \_| ''\---/'' | |
 *              \ .-\__ `-` ___/-. /
 *           ___`. .' /--.--\ `. . __
 *        ."" '< `.___\_<|>_/___.' >'"".
 *       | | : `- \`.;`\ _ /`;.`/ - ` : | |
 *         \ \ `-. \_ __\ /__ _/ .-` / /
 * ======`-.____`-.___\_____/___.-`____.-'======
 *                    `=---='
 *                     拜佛处
 * .............................................
 *          佛祖保佑             永无BUG
 *
 *      祝大家考试考好            天天向上

2026-07-24 来自广东