信息奥赛题单

发布日期: 2023-10-11

文章字数: 5.5k

阅读时长: 24 分

阅读次数:

前缀和与差分

题单 🧑🏻‍💻

题目来源	题目名称	题目链接	备注	难度
AcWing 795	前缀和	链接🔗	「一维前缀和」模版题	🟢
AcWing 796	子矩阵的和	链接🔗	「二维前缀和」模版题	🟢
AcWing 797	差分	链接🔗	「一维差分」模版题	🟢
AcWing 798	差分矩阵	链接🔗	「二维差分」模版题	🟢
ZJNU OJ - 1442	Colar the ball	链接🔗	差分与前缀和	🟢
NOIP2005 普及组	校门外的树	链接🔗	差分 / 区间合并	🟢
NOIP2012 提高组	借教室	链接🔗	差分与前缀和	🟡
ZJNU - 2723	猫猫写题题	链接🔗	前缀和与差分	🟡
AtCoder - ABC 122C	GeT AC	链接🔗	前缀和与子串	🟢
AtCoder - ABC 125C	GCD on Blackboard	链接🔗	前缀/后缀与gcd	🟡

题解 🚀

前缀和

题目信息 📚

【题目名称】AcWing 795 - 前缀和（模版题）

【题目描述】

输入一个长度为 $n$ 的整数序列。

接下来再输入 $m$ 个询问，每个询问输入一对 $l, r$。

对于每个询问，输出原序列中从第 $l$ 个数到第 $r$ 个数的和。

【输入】

第一行包含两个整数 $n$ 和 $m$ 。

第二行包含 $n$ 个整数，表示整数数列。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$ ，表示一个询问的区间范围。

【输出】

共 $m$ 行，每行输出一个询问的结果。

【输入样例】

【输出样例】

3
6
10

【数据范围】

$1 \le l \le r \le n$
$1 \le n,m \le 100000$
$−1000 \le 数列中元素的值 \le 1000$

【原题链接】

https://www.acwing.com/problem/content/797/

题目解析 🍉

【题目分析】

本题是 一维前缀和的模版题，只需在理解 前缀和思想 的基础上手撕代码即可。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int a[N], s[N];
int n, m, l, r;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

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

    //计算一维前缀和
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i];
    }

    while (m--) {
        cin >> l >> r;
        //利用 前缀和数组 输出部分和
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

子矩阵的和

题目信息 📚

【题目名称】AcWing 796 - 子矩阵的和（模版题）

【题目描述】

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入$q$ 个询问，每个询问包含四个整数 $x_1,y_1,x_2,y_2$，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

【输入】

第一行包含三个整数 $m,m,q$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一组询问。

【输出】

共 $q$ 行，每行输出一个询问的结果。

【输入样例】

【输出样例】

17
27
21

【数据范围】

$1 \le n,m \le 1000$
$1 \le q \le 200000$
$1 \le x_1 \le x_2 \le n$
$1 \le y_1 \le y_2 \le m$
$−1000 \le 矩阵内元素的值 \le 1000$

【原题链接】

https://www.acwing.com/problem/content/796/

题目解析 🍉

【题目分析】

本题为 二维前缀和 的模版题，可以通过作图法的方式推出相关公式，也可以在理解模版的基础上应用模版。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;

int a[N][N], s[N][N];
int n, m, q, x_1, x_2, y_1, y_2;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m >> q;
    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) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    while (q--) {
        cin >> x_1 >> y_1 >> x_2 >> y_2;
        //输出子矩阵的和
        int psum = s[x_2][y_2] - s[x_1 - 1][y_2] - s[x_2][y_1 - 1] + s[x_1 - 1][y_1 - 1];
        cout << psum << endl;
    }

    return 0;
}

差分

题目信息 📚

【题目名称】AcWing 797 - 差分（模版题）

【题目描述】

输入一个长度为 $n$ 的整数序列。

接下来输入 $m$ 个操作，每个操作包含三个整数 $l,r,c$，表示将序列中 $l,r$ 之间的每个数加上 $c$。

请你输出进行完所有操作后的序列。

【输入】

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示整数序列。

接下来 $m$ 行，每行包含三个整数 $l,r,c$，表示一个操作。

【输出】

共一行，包含 $n$ 个整数，表示最终序列。

【输入样例】

6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1

【输出样例】

3 4 5 3 4 2

【数据范围】

$1 \le n,m \le 100000$

$1 \le l \le r \le n$

$−1000 \le c≤1000$

$−1000 \le 整数序列中元素的值 \le 1000$

【原题链接】

https://www.acwing.com/problem/content/799/

题目解析 🍉

【题目分析】

本题是 一维差分的模版题，只需在理解 差分思想 的基础上手撕代码即可。

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, m, l, r, c, q;
int a[N], b[N];

void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

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

    //跳过b[i] = a[i] - a[i-1]的步骤，直接以差分的思想插入a数组
    for (int i = 1; i <= n; ++i) {
        insert(i, i, a[i]);
    }

    //m次操作
    while (m--) {
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    //输出结果
    for (int i = 1; i <= n; ++i) {
        a[i] = a[i - 1] + b[i];
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

差分矩阵

题目信息 📚

【题目名称】AcWing 798 - 差分矩阵（模版题）

【题目描述】

输入一个 $n$ 行 $m$ 列的整数矩阵，再输入 $q$ 个操作，每个操作包含五个整数 $x_1,y_1,x_2,y_2,c$，其中 $(x_1,y_1)$ 和 $(x_2,y_2)$ 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 $c$。

请你将进行完所有操作后的矩阵输出。

【输入】

第一行包含整数 $n,m,q$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含 $5$ 个整数 $x_1,y_1,x_2,y_2,c$，表示一个操作。

【输出】

共 $n$ 行，每行 $m$ 个整数，表示所有操作进行完毕后的最终矩阵。

【输入样例】

【输出样例】

2 3 4 1
4 3 4 1
2 2 2 2

【数据范围】

$1 \le n,m \le 1000$

$1 \le q \le 100000$

$1 \le x_1 \le x_2 \le n$

$1 \le y_1 \le y_2 \le m$

$−1000 \le c \le 1000$

$−1000 \le 矩阵内元素的值 \le 1000$

【原题链接】

https://www.acwing.com/problem/content/800/

题目解析 🍉

【题目分析】

本题为 二维差分 的模版题，可以通过 作图法 的方式推出相关公式，也可以在理解模版的基础上应用模版。

修改差分数组（左上 $[x_1,y_1]$，右下 $[x_2,y_2]$ ) ：

void update(int x_1, int y_1, int x_2, int y_2, int c) {
    b[x_1][y_1] += c;
    b[x_1][y_2 + 1] -= c;
    b[x_2 + 1][y_1] -= c;
    b[x_2 + 1][y_2 + 1] += c;
}

【C++ 代码】

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;
int a[N][N], b[N][N];
int x_1, y_1, x_2, y_2, c;
int n, m, q;

//更新差分矩阵，通过作图法理解
void update(int x_1, int y_1, int x_2, int y_2, int c) {
    b[x_1][y_1] += c;
    b[x_1][y_2 + 1] -= c;
    b[x_2 + 1][y_1] -= c;
    b[x_2 + 1][y_2 + 1] += c;
}

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

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

    //跳过差分数组初始化，直接用a数组更新差分数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            update(i, j, i, j, a[i][j]);
        }
    }

    //q次更新
    while (q--) {
        cin >> x_1 >> y_1 >> x_2 >> y_2 >> c;
        update(x_1, y_1, x_2, y_2, c);
    }

    //利用更新后的差分矩阵求新的a矩阵，即二维前缀和数组的初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

Color the ball

题目信息 📚

【题目名称】ZJNU 1442 - Color the ball

【题目描述】

$N$ 个气球排成一排，从左到右依次编号为 $1,2,3….N$。

每次给定 $2$个整数 $a,b(a <= b)$，lele 便会骑上他的「小飞鸽」牌电动车从气球 a 开始到气球 b 依次给每个气球涂一次颜色。

但是 $N$ 次以后 lele 已经忘记了第 $i$ 个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

【输入】

每个测试实例第一行为一个整数 $N(N <= 100000)$

接下来的 $N$ 行，每行包括 $2$ 个整数 $a,b(1 <= a <= b <= N)$。

当 $N = 0$，输入结束。

【输出】

每个测试实例输出一行，包括 $N$ 个整数，第 $i$ 个数代表第 $i$ 个气球总共被涂色的次数。

【输入样例】

【输出样例】

1 1 1
3 2 1

【题目链接】

http://10.7.95.2/problem/1442/view

题目解析 🍉

【题目分析】

一维差分数组の模版题

【 C++ 代码】

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int b[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int n, l, r;
    while (cin >> n && n) {
        // 差分数组b初始化
        memset(b, 0, sizeof(b));  // 刚开始每个气球都没有被涂过

        // 维护差分数组b
        for (int i = 0; i < n; i++) {
            cin >> l >> r;
            b[l] += 1;
            b[r + 1] -= 1;
        }

        // 差分数组b求前缀和，还原数组
        for (int i = 1; i <= n; i++) {
            b[i] += b[i - 1];
            cout << b[i] << " ";
        }
        cout << endl;
    }

    return 0;
}

校门外的树

题目信息 📚

【题目名称】NOIP2005 普及组 T2 - 校门外的树

【题目描述】

某校大门外长度为 $l$ 的马路上有一排树，每两棵相邻的树之间的间隔都是 $1$ 米。我们可以把马路看成一个数轴，马路的一端在数轴 $0$ 的位置，另一端在 $l$ 的位置；数轴上的每个整数点，即 $0,1,2,\dots,l$，都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

【输入】

第一行有两个整数，分别表示马路的长度 $l$ 和区域的数目 $m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示一个区域的起始点和终止点的坐标。

【输出】

输出一行一个整数，表示将这些树都移走后，马路上剩余的树木数量。

【输入样例】

【输出样例】

【数据范围】

对于 $20%$ 的数据，保证区域之间没有重合的部分。
对于 $100%$ 的数据，保证 $1 \leq l \leq 10^4$，$1 \leq m \leq 100$，$0 \leq u \leq v \leq l$。

【题目链接】

https://www.luogu.com.cn/problem/P1047

题目解析 🍉

【题目分析】

法1：差分数组

法2：区间合并

【 C++ 代码】

法1：差分数组

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int b[N];

void solve_b(int l, int m) {
    // 初始化差分数组
    memset(b, 0, sizeof(b));
    b[1] = 1;  // 求前缀和后的b[i]代表l = i - 1的树数量

    // m次操作
    int x, y;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        x++, y++;
        b[x]--, b[y + 1]++;
    }

    // 差分数组求前缀和，还原数组
    int cnt = 0;
    for (int i = 1; i <= l + 1; i++) {
        b[i] += b[i - 1];
        if (b[i] == 1) cnt++; // b[i]==0，说明i+1处的树没有被砍
    }
    cout << cnt << endl;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    int l, m;
    cin >> l >> m;

    // 差分法求解
    solve_b(l, m);

    return 0;
}

借教室

题目信息 📚

【题目名称】NOIP2012 提高组 - 借教室

【题目描述】

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

【输入】

第一行包含两个正整数 $n,m$，表示天数和订单的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

【输出】

如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改订单的申请人编号。

【输入样例】

【输出样例】

-1 
2

【输入输出样例说明】

第 $1 $份订单满足后，$4 $天剩余的教室数分别为 $0,3,2,3$。第 $2$ 份订单要求第 $2 $天到第 $4$ 天每天提供$ 3 $个教室，而第 $3$ 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第$2$ 个申请人修改订单。

【数据范围】

对于10%的数据，有$1≤ n,m≤ 10$；

对于30%的数据，有$1≤ n,m≤1000$；

对于 70%的数据，有$1 ≤ n,m ≤ 10^5$；

对于 100%的数据，有$1 ≤ n,m ≤ 10^6,0 ≤ r_i,d_j≤ 10^9,1 ≤ s_j≤ t_j≤ n$。

题目解析 🍉

【题目分析】

差分 + 二分答案（二分优化的过程非常巧妙）

思路1
- 对于每一个订单，使用「差分」可以把 减区间内教室数量 这个过程优化至 $O(1)$
- 但是如果直接判断当前订单能否满足要求，还需要求一遍前缀和 $O(n)$
- 一共有 $m$ 个订单，则时间复杂度为 $O(m * n)$，显然会 TLE
思路2
- 同样使用「差分」，把 减区间内教室数量 这个过程优化至 $O(1)$
- 但是不立即判断当前订单是否满足，而是等所有订单完成后，求一遍前缀和判断是否能满足所有订单
- 若不能满足，倒回去查找是哪个订单不能满足
  - 当第 i 个订单不能满足时，后面的订单也一定不能满足，符合「二段性」，因此可以使用「二分」进行优化
  - 时间复杂度被优化为 $O(m) + O(m * log(n))$

【 C++ 代码】

单独使用「差分」→ TLE ❌

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int b[N], a[N];
int n, m, tmp, d, s, t;

// 判断当前订单能否被满足
bool judge() {
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] + b[i];
        if (a[i] < 0)
            return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
    // 初始化差分数组
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        b[i] += tmp, b[i + 1] -= tmp;
    }

    // 读入m个订单，维护差分数组
    for (int i = 1; i <= m; i++) {
        cin >> d >> s >> t;
        b[s] -= d, b[t + 1] += d;
        // 判断当前订单能否被满足
        if (!judge()) {
            cout << -1 << endl;
            cout << i << endl;
            return 0;
        }
    }
    cout << 0 << endl;

    return 0;
}

「差分」 + 「二分答案」 → AC ✅

#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int b[N], a[N], d[N], s[N], t[N];
int n, m, tmp;

// 检查1～x个订单能否被满足
// 不能被满足，返回true
bool check(int x) {
    // 初始化差分数组，拷贝原始差分数组b至a, a用于后续计算
    for (int i = 1; i <= n; i++) a[i] = b[i]; // 拷贝b至a, a用于后续计算

    // 读取1～x号订单，维护差分数组a
    for (int i = 1; i <= x; i++) a[s[i]] -= d[i], a[t[i] + 1] += d[i];

    // 求一次前缀和，判断1~x号订单能否被满足
    bool flag = false;
    for (int i = 1; i <= n; i++) {
        a[i] += a[i - 1];
        if (a[i] < 0) flag = true;
    }
    return flag;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n >> m;
//     初始化差分数组
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        b[i] += tmp, b[i + 1] -= tmp;  // b存储原始状态
    }
    
    //读入m个订单，维护差分数组
    for (int i = 1; i <= m; i++) cin >> d[i] >> s[i] >> t[i];
    
    // 判断1～m个订单能否被满足（利用差分，可以做到O(m + n))
    bool flag = !check(m);  // 由于定义check时，1～m不能被满足时返回true，所以需要取反
    
    if (flag)  // 若1~m号订单可以被满足 
        cout << 0 << endl;
    else {  // 若有订单不能被满足
        cout << -1 << endl;
        
        // 二分查找哪一个订单不能被满足
        int l = 1, r = m;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }

    return 0;
}

猫猫写题题

题目信息 📚

【题目名称】ZJNU - 猫猫写题题

【题目描述】

奇怪的事情发生了！高数老师决定进行随堂测验。

老师给出了一个二元函数，如下所示：

$$
F(x,y)=2xy+x+y
$$

问对于所有整数 $i\in [L,R]$，有多少个 $i$ 满足：存在正整数 $x,y$，使得 $F(x,y)=i$？

【输入】

第一行包含一个整数 $T\ (1\le T\le 1000)$，表示测试数据组数。

其后 $T$ 行，每行包含两个整数 $L,R\ (1\le L\le R\le 10^7)$。

【输出】

输出 $T$ 行，每行一个整数，表示每组测试数据的答案。

【输入样例】

2
1 10
2160798 7551610

【输出样例】

3
4718113

【提示】

$F(1,1)=4$

$F(1,2)=7$

$F(1,3)=10$

因此在区间 $[1,10]$ 内，只有 $4,7,10$ 这三个整数满足题意。

【题目链接】

http://10.7.95.2/problem/2723/view

题目解析 🍉

【题目分析】

本题利用「桶思想」，开一个长度约为 1e7 的桶数组，将自然数 $1～1e7$ 以索引的形式存入其中。

初始状态下，所有桶中均没有东西，即 a[k] = 0。

通过暴力枚举 (i, j) 给桶数组赋值，即对于每一组 (i, j)，令 a[f(i, j)] = 1。

如 a[10] = 1，表示存在 (i, j)，使得 f(i, j) = 10；如 a[12] = 0，表示不存在 (i, j)，使得 f(i, j) = 12。

因此统计 [l ,r] 中出现的 f(i, j)，只需要统计 a[l] ~ a[r] 之和即可，故使用前缀和。

本题桶思想的下标映射对于初学者来说可能有些难理解，初期可以跳过此题。

【 C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int a[N];

LL f(LL x, LL y) {
    return 2 * x * y + x + y;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 预处理
    // 对于每一组(i, j)，将a[f(i, j)]标记为1
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j++) {
            if (f(i, j) < N) a[f(i, j)] = 1;
            else break;
        }
    }

    // 经过预处理后，所有1e7范围内的f(i ,j)，均被统计在a中（类似于桶思想）
    // 如a[10] = 1，表示存在(i, j)，使得f(i, j) = 10
    // 如a[12] = 0，表示不存在(i, j)，使得f(i, j) = 12;
    // 因此假设需要统计[l ,r]中出现的f(i, j)，只需要统计a[l] ~ a[r]之和即可
    // 故使用前缀和
    for (int i = 1; i < N; i++)
        a[i] += a[i - 1];

    int T, l, r;
    cin >> T;
    while (T--) {
        cin >> l >> r;
        cout << a[r] - a[l - 1] << endl;
    }

    return 0;
}

参考资料 📚

Acwing算法基础课 - https://www.acwing.com/activity/content/11/
洛谷 - https://www.luogu.com.cn/
ZJNU OJ - acm.zjnu.edu

Rickyの水果摊

https://ricky2333.github.io/2023/10/11/xin-xi-ao-sai-ti-dan-qian-zhui-he-yu-chai-fen/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Rickyの水果摊 !

信息奥赛 C++ 前缀和差分

信息奥赛｜二分

2023-10-12 信息奥赛知识点

信息奥赛 C++ 二分

信息奥赛｜前缀和与差分

2023-10-10 信息奥赛知识点

信息奥赛 C++ 前缀和差分

信息奥赛题单｜前缀和差分

前缀和与差分

题单 🧑🏻‍💻

题解 🚀

前缀和

题目信息 📚

【题目名称】AcWing 795 - 前缀和（模版题）

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

子矩阵的和

题目信息 📚

【题目名称】AcWing 796 - 子矩阵的和（模版题）

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

差分

题目信息 📚

【题目名称】AcWing 797 - 差分（模版题）

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

差分矩阵

题目信息 📚

【题目名称】AcWing 798 - 差分矩阵（模版题）

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【原题链接】

题目解析 🍉

【题目分析】

【C++ 代码】

Color the ball

题目信息 📚

【题目名称】ZJNU 1442 - Color the ball

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【题目链接】

题目解析 🍉

【题目分析】

【 C++ 代码】

校门外的树

题目信息 📚

【题目名称】NOIP2005 普及组 T2 - 校门外的树

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【数据范围】

【题目链接】

题目解析 🍉

【题目分析】