有基础班_day01课上题目

zxcvbnm

2025-07-02 16:20:02

发布于：上海

6阅读

0回复

0点赞

题目
小蚂蚁吃米
连续自然数和
差分
语文成绩
买凤梨

小蚂蚁吃米

题目大意

有一个长度为 $n$ 的数组，表示小蚂蚁每天吃的白大米数量。现在有 $q$ 次查询，每次查询给出区间 $[L, R]$ ，要求输出小蚂蚁这段时间内吃的大米总数。

题意分析

需要多次快速求数组区间和。
由于 $n, q$ 可以较大，使用前缀和数组预处理。
查询复杂度可以降到 $O(1)$ 。

解题思路

预处理前缀和数组 $pre$ ，其中

$pre[i] = a_1 + a_2 + \cdots + a_i$

对于查询 $[L, R]$ ，结果为

$pre[R] - pre[L-1]$

代码实现

#include <iostream>
using namespace std;

const int MAXN = 100000 + 10;
int n, q;
int a[MAXN];
long long pre[MAXN];

int main() {

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

    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        cout << pre[R] - pre[L - 1] << "\n";
    }

    return 0;
}

连续自然数和

题目描述

给定一个正整数 $M$ ，找出所有连续正整数区间，区间长度至少为2，且区间内所有数之和等于 $M$ 。

输入格式

一个整数 $M$ 。

输出格式

按起始数字从小到大，输出所有满足条件的区间，每行两个整数，表示起始数和结束数。

题意分析

利用前缀和数组快速计算区间和；
枚举左端点 $l$ ，对每个 $l$ 从 $l+1$ 开始枚举右端点 $r$ ；
当区间和等于 $M$ 输出结果；
当区间和超过 $M$ 立即跳出该轮循环（剪枝）。

代码实现

#include <iostream>
using namespace std;

const int N = 2e6 + 10;
int pre[N];

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

    // 计算前缀和数组
    for (int i = 1; i <= m; i++) {
        pre[i] = pre[i - 1] + i;
    }

    // 枚举区间左端点
    for (int l = 1; l <= m; l++) {
        // 枚举右端点，至少2个数，因此r从l+1开始
        for (int r = l + 1; r <= m; r++) {
            int sum = pre[r] - pre[l - 1]; // 区间[l, r]的和
            if (sum == m) {
                cout << l << " " << r << "\n";
                break; // 继续枚举下一个左端点
            }
            if (sum > m) {
                break; // 当前区间和已超，跳出枚举右端点
            }
        }
    }

    return 0;
}

差分

题目描述

给定一个长度为 $n$ 的整数序列，进行 $m$ 次区间加法操作，每次操作给区间 $[l, r]$ 上的所有元素加上一个整数 $c$ 。最后输出操作后的序列。

解题思路

利用差分数组可以将区间加法的操作转化为两端点的加减操作，从而实现 $O(1)$ 时间内完成区间修改，最后再根据差分数组恢复出最终序列。

具体步骤：

初始化差分数组 $d$ ，长度为 $n$ ：

$d[1] = a_1, \quad d[i] = a_i - a_{i-1} \quad (2 \le i \le n)$
对于每个操作 $[l, r, c]$ ：

$d[l] += c$

如果 $r+1 \le n$ ，则：

$d[r+1] -= c$
对差分数组做前缀和还原序列：

$a_i = \sum_{k=1}^i d[k]$

代码示范

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n, m;
long long a[N], d[N];

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

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

    // 构造差分数组
    d[1] = a[1];
    for (int i = 2; i <= n; i++) {
        d[i] = a[i] - a[i - 1];
    }

    // 处理m个区间加法操作
    for (int i = 0; i < m; i++) {
        int l, r; 
        long long c;
        cin >> l >> r >> c;
        d[l] += c;
        if (r + 1 <= n) d[r + 1] -= c;
    }

    // 根据差分数组还原结果
    for (int i = 2; i <= n; i++) {
        d[i] += d[i - 1];
    }

    // 输出最终序列
    for (int i = 1; i <= n; i++) {
        cout << d[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}

语文成绩

题目大意

有 $n$ 个学生，给出每个学生的初始语文成绩。老师将对多个区间进行加分操作，每次给第 $x$ 到第 $y$ 个学生的成绩都加上 $z$ 分。你需要输出所有操作完成后，全班学生的最低分。

题意分析

这是一个典型的 区间加法操作 问题，使用朴素做法每次遍历 $[x, y]$ 区间将会导致 $O(pn)$ 的复杂度，显然超时。可以使用 差分数组 优化为 $O(n + p)$ 时间。

解题思路

设数组 $a$ 表示成绩数组，差分数组 $d$ 定义为：

$d[1] = a[1]$
$d[i] = a[i] - a[i - 1] \quad (2 \le i \le n)$

对于区间加法 $[x, y]$ 加 $z$ ，只需：

$d[x] += z$
$d[y + 1] -= z$

操作完后，再通过前缀和还原原数组。

时间复杂度分析

构造差分数组： $O(n)$
处理 $p$ 次加法操作： $O(p)$
还原数组并找最小值： $O(n)$

总时间复杂度为： $O(n + p)$ ，完全可以应对 $n, p \leq 5 \times 10^5$ 的数据范围。

代码实现

#include <iostream>
using namespace std;

const int N = 5e5 + 10; // 注意：5e5 = 500000，不是 5*10e5

int a[N], diff[N];

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

    // 读入初始成绩并构造差分数组
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        diff[i] = a[i] - a[i - 1]; // 差分数组初始化
    }

    // 区间加操作
    for (int i = 1; i <= m; i++) {
        int l, r, c;
        cin >> l >> r >> c;
        diff[l] += c;
        diff[r + 1] -= c;
    }

    // 还原原数组
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + diff[i];
    }

    // 找最小成绩
    int min_score = 201; // 初始最大为200
    for (int i = 1; i <= n; i++) {
        if (a[i] < min_score) {
            min_score = a[i];
        }
    }

    cout << min_score << endl;
    return 0;
}

买凤梨

题目大意

你有 $n$ 本美食书，每本书推荐了一个甜度区间 $[l, r]$ 。
如果一个甜度被 不少于 $k$ 本书推荐，则这个甜度是“合适”的。

现在有 $q$ 次询问，每次询问一个区间 $[l, r]$ ，你需要回答这个区间中有多少个“合适”的甜度。

题意分析

本质上是区间统计问题。
每本书推荐了一个甜度区间 → 相当于这个区间里的每一个甜度值 $x$ 被推荐了一次。
若一个甜度值 $x$ 被推荐的次数 $\ge k$ ，则称它是合适甜度。

我们需要支持：

快速判断一个甜度是否合适；
快速查询某一甜度区间中有多少个甜度是合适的。

解题思路

使用 差分数组 + 前缀和优化：

使用差分数组 a[i]，对每个推荐区间 $[l, r]$ $[l, r]$ ：
- $a[l] += 1$
- $a[r+1] -= 1$
遍历一遍求前缀和 $a[i]$ ，得到每个甜度值被推荐了多少次。
另设一个数组 ok[i]，如果 $a[i] \ge k$ ，则令 ok[i] = 1，否则为 $0$ 。
再对 ok[i] 求前缀和。
对于每次询问 $[l, r]$ ，答案就是 ok[r] - ok[l-1]。

时间复杂度分析

差分与前缀和： $O(\text{MAX})$ ，其中 $\text{MAX} = 2 \times 10^5$
每次询问时间复杂度： $O(1)$ ，共 $q$ 次，总代价 $O(q)$
总时间复杂度： $O(n + \text{MAX} + q) = O(2 \times 10^5)$ 级别

可以应对所有数据范围。

代码实现

#include <iostream>
using namespace std;

const int N = 2e5 + 10; // 最大甜度范围
int a[N], ok[N]; // a[i] 表示甜度 i 被推荐了多少次；ok[i] 是否是合适甜度的前缀和

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

    // 差分处理
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        a[l]++;       // 区间起点 +1
        a[r + 1]--;   // 区间终点后 -1
    }

    // 还原前缀和，得到每个甜度被推荐的次数
    for (int i = 1; i < N; i++) {
        a[i] += a[i - 1];
        if (a[i] >= k) ok[i] = 1; // 判断是否是合适甜度
    }

    // 对 ok 数组做前缀和，支持快速区间查询
    for (int i = 1; i < N; i++) {
        ok[i] += ok[i - 1];
    }

    // 处理每个询问
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << ok[r] - ok[l - 1] << endl;
    }

    return 0;
}