MoreRSS

site iconDevTang | 唐巧修改

博客 iOS 作者 编程 北京
iOS开发，孵化了 小猿搜题 和 小猿口算。斑马智能硬件业务负责人，带领团队研发的产品累计出货量超过 400 万台。著有《iOS 开发进阶》。
RSS: https://blog.devtang.com/atom.xml
请复制 RSS 到你的阅读器，或快速订阅到 :

Inoreader Feedly Follow Feedbin Local Reader

DevTang | 唐巧的 RSS 预览

GESP 大题核心考点

2025-06-06 22:12:03

GESP 1 级

1 级主要考查分支和循环结构，所以大题的解法一般都是一个 for 循环，然后循环里面用 if 之类的条件判断做一些事情，最后再输出结果。其代码框架为：

1
2
3
 
// 循环结构, 例如 for ...
    // 判断条件
// 输出结果

拿 GESP202309 一级题目：小明的幸运数 来说，其核心代码是：

1
2
3
4
5
6
7
8
9
10
 
// 循环
for (int i = l; i <= r; ++i) {
    // 判断条件
    if (isLucky(i)) {
        // 累加
        ans += i;
    }
}
// 输出结果
cout << ans << endl;

另外一个例子，GESP202503 一级题目：四舍五入，核心代码：

1
2
3
4
5
6
7
8
9
10
11
 
// 循环
for (int i = 1; i <= n; ++i) {
    cin >> a;
    b = a%10;
    a = a/10;
    // 判断条件
    if (b <= 4) a = a*10;
    else a = a*10 + 10;
    // 输出结果
    cout << a << endl;
}

GESP 2 级

考点一：双重循环

GESP 2 级相对 1 级，对循环结构的考查进行了加强，一般需要用双层嵌套的循环才能完成大题。有一类双层嵌套循环需要特别关注，就是模拟输出类，这一类题过去考过多次，包括：

以等差矩阵为例，其关键代码为嵌套的 for 循环，参考如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, m;
int tu[55][55];
int main() {
    cin >> n >> m;
    // 嵌套的 for 循环
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << i*j << " ";
        }
        cout << endl;
    }
    return 0;
}

如果学生还是不熟悉，可以考虑如下更多的练习：

  • 模仿 小杨的 X 字矩阵，输出 “又” 字，倒 “N” 字，“工” 字矩阵，“口”字矩阵
  • 模仿 画三角形，输出 左对齐、右对齐的正三角形，倒三角形
  • 模仿 等差矩阵，输出求和的矩阵，输出只有偶数的等差矩阵（奇数位填 *）

考点二：常用函数

2 级还会考一些我们经常会实现的函数。包括：

求素质函数

参考题目：GESP202306 找素数

1
2
3
4
5
6
7
8
 
bool isPrime(int a) {
    for (int i = 2; i*i <=a; i++) {
        if (a%i == 0) {
            return false;
        }
    }
    return true;
}

求闰年函数

参考题目：GESP202503 时间跨越

关键代码：

1
2
3
4
 

bool isLeapYear(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

把一个数的每一位数字拆分的写法

参考题目：GESP202406 计数

关键代码：

1
2
3
4
5
6
7
8
 
int count(int a, int k) {
    int ret = 0;
    while (a) {
        if (a%10 == k) ret++;
        a/=10;
    }
    return ret;
}

练习题目：GESP202409 数位之和

GESP 3 级

考点一：字符串操作

3 级对字符串的操作要求非常高，需要考生灵活掌握字符串的变换、拼接、求子串、判断回文等操作。

求子串可以用 string 类的 substr(int pos, int len) 函数。需要注意该函数的两个参数分别是起始下标和长度。

其中，判断回文的写法如下：

1
2
3
4
5
6
7
8
9
 
bool isReverse(string &s) {
    int len = s.length();
    for (int i = 0; i < len/2; ++i) {
        if (s[i] != s[len-i-1]) {
            return false;
        }
    }
    return true;
}

以真题 GESP202409 回文拼接 为例，考生需要对字符串进行切分，然后分别判断是否是回文串。

参考代码如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
string s;

bool isReverse(string &s) {
    int len = s.length();
    for (int i = 0; i < len/2; ++i) {
        if (s[i] != s[len-i-1]) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    while (n--) {
        cin >> s;
        bool ans = false;
        if (s.length() >= 4) {
            for (int i = 2; i < s.length() - 1; i++) {
                string s1 = s.substr(0, i);
                string s2 = s.substr(i);
                if (isReverse(s1) && isReverse(s2)) {
                    ans = true;
                    break;
                }
            }
        }
        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

该考点的相关真题：

其中 GESP202309 进制判断 看起来是考进制的规则，实际上也是考字符串的查找。参考代码如下：

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
26
27
28
29
30
31
32
33
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int isRange(string s, string range) {
    for (int i = 0; i < s.length(); ++i) {
        char ch = s[i];
        int j = 0;
        for (j=0; j<range.length(); ++j) {
            if (ch == range[j]) {
                break;
            }
        }
        if (j == range.length()) return 0;
    } 
    return 1;
}

int main() {
    int n;
    string s;
    cin >> n;
    while (n--) {
        cin >> s;
        cout << isRange(s, "01") << " " 
             << isRange(s, "01234567") << " " 
             << isRange(s, "0123456789") << " " 
             << isRange(s, "0123456789ABCDEF") << endl;
    }
    return 0;
}

考点二：前缀和

前缀和的计算技巧是：用一个累加变量来不停地更新前 N 个数的和，这样我们只需要用 O（N）的时间复杂度，就可以把所有的前缀和求出来。

参考题目：GESP202409 平衡序列

此题解法是：暴力测试，先计算出总和 tot ，然后看前缀和的两倍有没有可能等于 tot。

参考代码：

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
26
27
28
29
30
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int t, n, v[10010], tot;
int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        tot = 0;
        for (int i = 0; i < n; ++i) {
            cin >> v[i];
            tot += v[i];
        }
        int cnt = 0;
        bool ans = false;
        for (int i = 0; i < n && cnt*2<tot; ++i) {
            cnt += v[i];
            if (cnt*2 == tot) {
                ans = true;
            }
        }
        if (ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

考点三：位运算

考生需要熟悉二进制，以及数的位运算操作。

典型考题为：GESP202503 2025

此题的思路如下：因为 x 最大是 2025，而如果 y 需要影响 x 的运算，只能与 x 的 bit 位是 1 的位进行操作。所以 y 如果存在，则必定小于 2048。因为 2048 的二进制 1 的 bit 位已经超过 2025 的最高位了。所以直接枚举 1～2048 之间的答案即可。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <bits/stdc++.h>
using namespace std;

int ans = -1;
int x;
int main() {
    cin >> x;
    for (int i = 1; i < 2048; ++i) {
        if ((x & i) + (x | i) == 2025) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

GESP 4 级

考点比较散，以下是历次考题的考点。

  • GESP-202306 幸运数：模拟
  • GESP-202309 进制转换：进制转换
  • GESP-202309 变长编码：位操作
  • GESP-202312 小杨的字典：字符串操作
  • GESP-202312 田忌赛马：排序，模拟
  • GESP-202403 相似字符串：字符串操作
  • GESP-202403 做题：贪心
  • GESP-202406 黑白方块：枚举
  • GESP-202406 宝箱：枚举，二分
  • GESP-202409 黑白方块：枚举
  • GESP-202409 区间排序：排序
  • GESP-202412 Recamán：枚举
  • GESP-202412 字符排序：排序
  • GESP-202503 荒地开垦：枚举
  • GESP-202503 二阶矩阵：枚举

其中，比较常考的考点：

  • 枚举：考了 6 次。
  • 排序：考了 3 次。
  • 字符串操作：考了 2 次。

CSPJ 教学总结：树状数组

2025-04-26 20:12:23

引言

树状数组是挺不好教学的一个知识点。它需要以下前置知识：

  • 二进制表示法及熟练的位操作
  • 前缀和的知识
  • 树的基础知识
  • 时间复杂度的估算

在教学的时候，我们的教学顺序如下：

  • 先引入问题
  • lowbit 函数讲解
  • 树状数组的结构特点
  • 利用树状数组求前缀和的方法
  • 怎么修改树状数组的值
  • 如何初始化树状数组
  • 增加值或替换值
  • 二维的树状数组

那么让我们来开始。

问题的引入

P3374 树状数组 1 是一道标准的树状数组问题：该题目给我们了一个数列，我们需要解决以下两个问题：

  • 数列的区间求和
  • 更新某一个数（加上 x）

我们很容易想到用暴力的方法来做此题。于是我们可以估计一下暴力的时间复杂度：

  • 数列的区间求和，时间复杂度 O（N）
  • 更新某一个数，时间复杂度 O（1）

题目中提到，求和的次数最多为 M 次，所以最坏情况下，时间复杂度为 O(M*N)。而由于 M 和 N 的最大范围为 5*10^5，所以最大运算次数高达 (5*10^5) * (5*10^5) = 2500亿次，而竞赛中估算 1000 万次的运算时间就接近 1 秒了，这个时间肯定会超时。

数列的区间求和有一个 O（1）的办法，就是提前求出前缀和。假如 Sum(i) 表示前 i 个数的和，那么区间 (i,j] 的和就可以通过 Sum(j) - Sum(i) 来得出。可惜的是，本题还有一个操作是更新某一个数。如果更新的是第一个数，那么整个前缀和数组 Sum 都需要更新，这样更新的时间复杂度会变成 O（N），最坏情况下会有 O(M*N)次更新，造成运算同样超时。

由此，我们需要一个更优秀的数据结构来解决这类问题，这就是树状数组。

lowbit 函数

在讲解树状数组前，我们先学习一下 lowbit 函数。

lowbit 函数实现的功能是：求 x 的二进制最低位 1 以及后面的 0 组成的数。例如：

  • 8 (10 进制) = 1000 (2 进制) ，则 lowbit(8) = 8
  • 9 (10进制）= 1001（2 进制），则 lowbit(9) = 1
  • 10（10 进制）= 1010（2 进制），则 lowbit(10) = 2

所以，我们需要找到目标数的二进制中的最后那个 1 的位置。有两种实现方式：

方法一：x^(x-1) & x

方法一相对比较好理解，我拿二进制数 1100 举例解释如下：

  • (x-1)的效果，相当于把二进制的最后一个1变成 0，比如某数 1100 减 1之后，就变成了 1011
  • 这个时候，如果我用 x^(x-1),就会得到 1100^1011=0111
  • 最后，用 x& 刚刚的 x^(x-1)，就相当于把x的最后一个1留下来了，前面的1都抹掉了：1100 & 0111 = 0100

方法二：x&-x

我们还是拿二进制数 1100 举例，由于负数是用补码表示，所以对于 1100，它的负数：

  • 原码为：11100(最高为 1 为符号位)
  • 反码为：10011(反码符号位不变，其余位取反)
  • 补码为：10100（补码=反码+1）

这样一操作，x&-x 就等于 01100 & 10100 = 0100，同样把最后的 1 取出来了。

在实现中，我们用方法二的更多，因为更短。参考代码如下：

1
2
3
 
int lowbit(int x) {
    return x & -x;
}

树状数组的定义

对于一个长度为 N 的序列，为了满足上面提到的更快的区间求和和更新的需求，我们可以构造一个树状数组。

树状数组（Binary Index Tree，简称 BIT）通过构造另一个长度为 N 的数组，来做到：

  • 区间求和，时间复杂度 O(log N)
  • 更新某一个数，时间复杂度 O(log N)

因为树状数组需要另外创建一个长度为 N 的数组，所以它的空间复杂度为O(N)。

我们先创建出这个数组 b ，然后再引入它的元素间的树状逻辑关系。

我们有了数组 b，我们让数组 b 相对于原始序列 a，按如下的关系来保存范围和：

  • b[1] 保存 a[1]的值
  • b[2] 保存区间 [a[1], a[2]] 的和
  • b[3] 保存 a[3]的值
  • ….省略若干行
  • b[8] 保存区间 [a[1], a[8]] 的和

我们先不管如何做到的，先假设我们按上面的逻辑，初始化好了这个数组，那么它怎么能快速求出前缀和呢？

树状数组求和

我们假设要求 a[1] ~ a[7]的和，如下图所示，我们知道这段和满足：Sum(7) = b[4] + b[6] + b[7]

那么，我们观察一下 b[4],b[6],b[7] 这几个下标有什么特点：

  • 4 的二进制：0100
  • 6 的二进制：0110
  • 7 的二进制：0111

如果结合上我们刚刚教的 lowbit 函数，我们就可以发现如下规律：

  • 4 的二进制：0100，4 = 6 - lowbit(6)
  • 6 的二进制：0110，6 = 7 - lowbit(7)
  • 7 的二进制：0111

于是，如果我们要求 Sum(7)，就可以用 b[7] 开始累加，然后用 7 - lowbit(7) 得到 6，再用 6 - lowbit(6) 得到 4，最后 4 - lowbit(4) = 0，就结束整个求和累加过程。

把以上逻辑转换成代码，是这样的：

1
2
3
4
5
6
7
8
 
int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

有人可能要问了，这个求和都是从序列开头开始的，如果我们想求序列中间一段，比如从 x 到 y 的区间和，应该怎么办呢？这种情况，我们可以：

  • 用 query(y) 把从头到 y 位置的和求出来
  • 用 query(x-1) 把从头到 x-1 位置的和求出来
  • 然后相减 query(y) - query(x-1) 得到区间 [x,y] 的和

更新数据

树状数组也支持更新数据，像P3374 树状数组 1题目中要求的那样，我们可以将某个数加上 x，这种情况应该如何更新数组呢？

我们以更新 a[1]为例，通过观察，我们发现涉及 a[1] 的数组有：b[1],b[2],b[4],b[8]，如下图所示：

你有观察出来规律吗？这刚好是我们构建的这个树从叶子结点到根结点的一条路径。

那同样的问题来了，我们如何求解出b[1],b[2],b[4],b[8]这个路径呢？我们来观察一下：

  • 1 的二进制是：0001
  • 2 的二进制是：0010, 2 = 1 + lowbit(1)
  • 4 的二进制是：0100, 4 = 2 + lowbit(2)
  • 8 的二进制是：1000, 8 = 4 + lowbit(4)

我们再验证一个中间结点的更新，比如更新 a[5]，如下图所示：

我们看看规则是不是一样：

  • 5 的二进制是 0101，
  • 6 的二进制是 0110，6 = 5 + lowbit(5)
  • 8 的二进制是 1000，8 = 6 + lowbit(6)

至此，我们总结出更新方法：从数列的下标 idx 开始，不停地更新，并且用 idx += lowbit(idx) 获得下一个更新的下标，直到更新到下标超过上界（N）为止。

1
2
3
4
5
6
 
void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

初始化

最暴力的初始化方法是：我们假设原序列全是 0，这样树状数组的初始状态也全是 0 即可正常表达上面的树型关系。然后，我们把每一个 a 序列中的数用更新的方式来放入树状数组中。

至此，我们完成了例题P3374 树状数组 1中的所有细节讨论，完整的代码如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

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

int lowbit(int x) {
    return x & -x;
}

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x-1) << endl;
        }
    }
    return 0;
}

但是，以上的这种初使化方法，时间复杂度为 O(N*logN)，如果数据刚好卡在初始化中，我们可以用以下这种方法来将初始化时间复杂度优化到 O(N)。

初始化（优化）

为了讲明白这种初始化，我们需要观察树状数组 b 中的每个元素代表的数据范围有什么规律。为什么 b[5] 只代表 a[5] 一个元素，但是 b[8]代表的是[a[1],a[8]] 区间的 8 个元素的和 ？

最终我们可以发现，一个数组元素代表的区间范围大小就是它的 lowbit 函数求出来的值。

例如：

  • lowbit(5) = 1，所以它只代表 a[5] 一个元素
  • lowbit(8) = 8，所以它代表 [a[1],a[8]] 共 8 个元素
  • 一个十进制数 88，其二进制为 01011000，lowbit(88)=8，所以它代表的区间为 8 个元素。

进一步的，我们可以观察出，对于一个 b[x]，它代表的区间为[x-lowbit(x)+1, x]。

这对初始化有什么用呢？

  • 我们如果构建了数组 a 的前缀和数组 s，s[i]表示前 i 个数的和。
  • 那么，我们就可以用前缀和数组 s 来初始化 b[x]。

因为 b[x] 代表的区间和是[x-lowbit(x)+1, x],所以：b[i] = s[i] - s[i-lowbit(i)]

至此，我们可以将例题P3374 树状数组 1的代码更新如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], b[MAXN], s[MAXN];

int lowbit(int x) {
    return x & -x;
}

void add(int idx, int val) {
    while (idx <= n) {
        b[idx] += val;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range > 0) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    // 初始化
    for (int i = 1; i<=n; ++i) {
        b[i] = s[i] - s[i-lowbit(i)];
    }
    for (int i = 1; i <= m; ++i) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x-1) << endl;
        }
    }
    return 0;
}

管辖区间

上面讲到，树状数组中的元素 b[x] 管辖的区间和是[x-lowbit(x)+1, x]，因此，我们更能理解树状数组的更新逻辑：

  • 所谓的更新a[x]，就是把管辖区间涵盖 a[x] 的所有 b[x]都更新一遍。
  • 那哪些 b[x]的管辖区间涵盖 a[x]呢？就是从二进制看，就是范围中有 lowbit(x) 的数。

举例来说，如果我们要更新 a[2] 的值，lowbit(2) 的值是 0010，所以，我们要更新：

  • b[2], 因为 2 的二进制是 0010，管辖区间是 [1, 2]
  • b[4], 因为 4 的二进制是 0100，管辖区间是 [1, 4]
  • b[8], 因为 8 的二进制是 1000，管辖区间是 [1, 8]

再举一个例子，如果我们要更新 a[5] 的值，lowbit(5) 的值是 0001，所以我们要更新：

  • b[5]，因为 5 的二进制是 0101，管辖区间是 [5, 5]
  • b[6]，因为 6 的二进制是 0110，管辖区间是 [5, 6]
  • b[8]，因为 8 的二进制是 1000，管辖区间是 [1, 6]

可以看到，对于每一个 b[x]，它代表的范围右边界始终是 x，而它的左边界，则随着更新的节点往上移动，在不停扩大。

差分数组

有些时候，题目会让我们一次更新一段区间，这个时候，我们可以引入差分数组来替代原数组。

差分数组中的每一个元素，是原数组相邻两个数的差。

例如：

  • 原数组： 1,2,3,4,5,6
  • 差分数组：1,1,1,1,1,1

我们对差分数组求前缀和，就可以还原出原数组。

这个时候，如果我们把原数组的第 3 个数到第 5 个数都加上 2，我们看看效果：

  • 原数组： 1,2,5,6,7,6
  • 差分数组：1,1,3,1,1,-1

我们观察到，原数组的一个区间都加上 2 之后，在差分数组那里，只有第 3 个数和第 6 个数有变化，其它都没有变化。所以，如果我们用差分数组来代替原数组，就可以只更新两个数值来代表原来的范围更新。

P3368 【模板】树状数组 2此题可以很好地练习差分数组与数状数组的结合运用，相关代码如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
/**
 * 差分：
 *  - 假设 A 序列为原序列
 *  - 差分数列 C 为原序列每两个数之间的差
 *    - 即：c[i] = a[i] - a[i-1]
 *         c[1] = a[1]
 *         c[2] = a[2] - a[1]
 *         c[3] = a[3] - a[2]
 *  - 所以：
 *    - a[i] = sum(c[1]+c[2]+...c[i])
 * 
 * 对于本题，如果把数组变成差分数组：
 *  - [x,y] 每个数加上 k，等价于:
 *    - c[x] += k
 *    - c[y+1] -= k
 *  - 求第 a[x] 的值，等价于：
 *    - sum(c[1]+c[2]+...c[x])
 *    - 即求前缀和
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MAXN (int)(500000+10)

int n, m;
int a[MAXN], c[MAXN], b[MAXN];

int lowbit(int x) {
    return x&-x;
}

void add(int idx, int v) {
    while (idx <= n) {
        b[idx] += v;
        idx += lowbit(idx);
    }
}

int query(int range) {
    int ret = 0;
    while (range) {
        ret += b[range];
        range -= lowbit(range);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        c[i] = a[i] - a[i-1];
        add(i, c[i]);
    }
    while (m--) {
        int op, x, y, k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y+1, -k);
        } else {
            cin >> x;
            cout << query(x) << endl;
        }
    }
    return 0;
}

二维的树状数组

刚刚讲到，对于一个 b[x]，它代表的区间为[x-lowbit(x)+1, x]

那么对于一个二维的树状数组 b[x, y]，它代表的区间就是 a(x-lowbit(x)+1, y-lowbit(y)+1) - a(x, y) 形成的矩阵的总和。如下图所示：

对于二维的树状数组，更新就需要用两层的循环了。示例代码如下：

1
2
3
4
5
6
7
 
void add(int x, int y, int v) {
  for (int i = x; i <= n; i += lowbit(i)) {
    for (int j = y; j <= m; j += lowbit(j)) {
      c[i][j] += v;
    }
  }
}

查询前缀和同样需要用循环，示例代码如下：

1
2
3
4
5
6
7
8
9
 
int query(int x, int y) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    for (int j = y; j > 0; j -= lowbit(j)) {
      res += c[i][j];
    }
  }
  return res;
}

如果题目要求区间和，则需要用容斥原理来求解，这里不再展开介绍。

用树状数组求逆序对

什么是逆序对？逆序对是指一个序列中，a[i] > a[j] 且 i < j 的有序对。

比如一个序列是 3 2 1，它的逆序对就有：3 2,3 1,2 1 三组。

树状数组如何和逆序对的数量扯上关系呢？

拿序列 3 2 1 举例，我们知道，树状数组是可以用前缀和的。如果我们：

  • 假设序列初始情况下为全 0
  • 当处理第一个数 3 的时候，我们让树状数组的下标 3 加 1：update(3, 1)，同时记录插入了 1 个数
  • 当处理第二个数 2 的时候，我们统计小于等于 2 的前缀和：query(2)，然后拿总数减 query(2)，得到大于 2 的数字数量
  • 这个数量，就是当 2 被处理的时候，前面有一共多少个数大于 2，即与 2 能够组成逆序对的数量

例题：P1908 逆序对

在此题中，我们先要解决两个问题，才能借用上面的思想：

问题1、题中的数据范围太大，我们如何解决?

答案：我们可以用离散化的思想，把 2 10000 1 变成 2 3 1，因为逆序对是统计相对大小，所以这样更改之后，逆序对的数量是不变的。

具体如何离散化呢？我们可以将数据依次标记上编号，然后排序。例如：

  • 原始序列为 100 200 50, 我们把它分别标上编号 (100,1), (200,2), (50,3)
  • 然后我们将数值排序，得到：(50,3), (100,1), (200,2)
  • 然后，我们再将新的序列赋上从 1 开始的编号：(50,3,1), (100,1,2), (200,2,3)
  • 然后，我们再将序列按原来的编号(第 2 个数字）排序，得到 (100,1,2), (200,2,3), (50, 3, 1)
  • 至此，我们转换得到了新的编号 2,3,1

因为 N 最多是 5*10^5，所以离散化之后，树状数组的大小也缩减到了 5*10^5

在实现的时候，我们可以用结构体来保存上面的三元组。

1
2
3
4
5
 
struct Node {
    int v;
    int origin_idx;
    int next_idx;
};

问题2、如果有两个相等的元素，会不会计算错误？

我们假设元素是 200 300 200,按我们刚刚的操作：

  • 先标号，得到 (200,1) (300,2) (200,3)
  • 再排序，得到 (200,1) (200,3) (300,2)
  • 再标号，得到 (200,1,1) (200,3,2) (300,2,3)
  • 再排序，得到 (200,1,1) (300,2,3) (200,3,2)
  • 最后序列是 1,3,2

这种是没问题的，但是，如果我们排序的时候不是用的稳定排序，把第二个 200 排到了前面，就会得到 2,3,1，这样逆序对就会多一个 2 1，而这本来是不存在的。

所以，为了解决这个问题，我们可以用稳定排序stable_sort，或者保证排序的时候，值相同的情况下，标号大的在后面。

以下是完整的参考程序：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

#define MAXN (int)(5*1e5+10)

struct Node {
    int v;
    int origin_idx;
    int next_idx;
};
Node a[MAXN];
int n,c[MAXN];
long long ans;

bool comp1(const Node &a, const Node &b) {
    return a.v < b.v;
}

bool comp2(const Node &a, const Node &b) {
    return a.origin_idx < b.origin_idx;
}

int lowbit(int x) { return x&-x; }

void add(int a, int v) {
    while (a<=n) {
        c[a]+=v;
        a+=lowbit(a);
    }
}

int query(int a) {
    int ret = 0;
    while(a) {
        ret += c[a];
        a -= lowbit(a);
    }
    return ret;
}


int main() {
    cin >> n;
    for (int i = 1; i <=n; ++i) {
        cin >> a[i].v;
        a[i].origin_idx = i;
    }
    stable_sort(a+1, a+1+n, comp1);
    for (int i = 1; i<=n; ++i) 
        a[i].next_idx = i;
    stable_sort(a+1, a+1+n, comp2);

    for (int i = 1; i <=n; ++i) {
        add(a[i].next_idx, 1);
        ans += i - query(a[i].next_idx);
    }
    cout << ans << endl;

    return 0;
}

相关练习题目

CSPJ 教学总结：深度优先搜索（DFS）

2025-04-13 15:27:30

深度优先搜索（DFS）是学生学习算法的第一道门槛，因为它的主要形式是递归。而递归中需要将搜索的相关信息通过参数传递，这一点需要学生深刻理解 DFS。

模版

DFS 有比较标准的模版，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void dfs(int pt) // pt 表示层数
{
    if (终止条件) {
        // 处理
        return;
    }
    for (枚举这个层的所有可选项) {
        if（这个选项是合法的）{
            标记这个选项（保存现场）
            dfs(pt+1); 
            取消标记（恢复现场）
        }
    }
}

我们将运用该模版，完成后面的题目。

递归的深度

递归的时候，程序会占用栈空间来保存函数的环境变量。根据编译器以及编辑参数的不同，栈空间的大小也不同。通常情况下，竞赛中的编译器设定的栈空间为 8M 或者 16M。

假如，我们在一个递归函数中使用了 10 个 int 变量，那么每个递归函数就需要 4*10=40字节的栈空间。8M 一共可以支持 8*1000*1000/40=200000层调用。考虑到栈空间还需要保存当前函数执行的地址等变量，可供支持的调用层数会更小一点。

同学们也可以做如下的递归函数栈空间的测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int dfs(int x) {
    int test[9] = {0};
    cout << x << endl;
    dfs(x + 1);
    return 0;
}

int main() {
    dfs(0);
    return 0;
}

在我的本地，以上程序调用了约 13 万次后栈溢出。为了保险，我们在比赛中如果调用深度小于 1 万层，那应该是稳妥的；否则我们需要考虑是否用别的解法来解题。

教学和练习题目

题目名 说明
P1036 选数 NOIP 2002 普及组
P1219 八皇后 Checker Challenge USACO 1.5
P1596 Lake Counting S USACO10OCT
P2036 PERKET COCI 2008/2009 #2
P12139 黑白棋 蓝桥杯 2025 省 A，写起来较繁琐
P1605 迷宫 标准的 DFS
P2404 自然数的拆分问题
P1019 单词接龙 NOIP 2000 提高组

P7200
P10483

P1219 八皇后 Checker Challenge

这是八皇后的变种，N 皇后问题。可以作为基础练习。具体解法是：

  • 我们用变量 v[15] 表示每个皇后的列值。
  • 对于新放入的皇后，我们依次检查它与前面的皇后是否在一条斜线上。检查方法是看其“横坐标差”与“纵坐标差”是否相同。检查函数如下：
1
2
3
4
5
6
 
bool check(int pt) {
    for (int i = 0; i < pt; i++) {
        if (abs(v[i] - v[pt]) == abs(i - pt)) return false;
    }
    return true;
}

完整的代码如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int v[15], ans;
bool flag[15];

bool check(int pt) {
    for (int i = 0; i < pt; i++) {
        if (abs(v[i] - v[pt]) == abs(i - pt)) return false;
    }
    return true;
}

void dfs(int pt) {
    if (pt == n) {
        ans++;
        if (ans <= 3) {
            for (int i = 0; i < n; i++) {
                cout << v[i] << " ";
            }
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (flag[i]==false) {
            flag[i] = true;
            v[pt] = i;
            if (check(pt)) dfs(pt + 1);
            flag[i] = false;
        }
    }
    
}

int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}

P1036 选数

此题需要从小到大取数求和，然后再判断是否是素数。用递归的方式来进行枚举。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, k, tot, ans;
int a[22], p[22];

bool isPrime(int v) {
    for (int i = 2; i*i <= v; ++i) {
        if (v%i == 0) {
            return false;
        }
    }
    return true;
}

void dfs(int pt) {
    if (pt == k+1) {
        if (isPrime(tot)) {
            ans++;
        }
    } else {
        // 每一层都必须取比前一层更大的下标，防止重复取
        for (int i = p[pt-1]+1; i <= n; ++i) {
            p[pt] = i;
            tot += a[i];
            dfs(pt+1);
            tot -= a[i];
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}

P1596 Lake Counting S

此题既可以用 DFS，也可以用 BFS。考虑到 N 和 M 最大值为 100，所以递归的层次最多为 1 万层，所以我们可以试试 DFS。

以下是参考代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
int n, m;
char tu[105][105];
int ans;
int movex[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int movey[8] = {1, -1, 0, 0, 1, -1, 1, -1};

void dfs(int x, int y) {
    tu[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int nx = x + movex[i];
        int ny = y + movey[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m 
            || tu[nx][ny] != 'W') continue;
        dfs(nx, ny);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tu[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tu[i][j] == 'W') {
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

P2036 PERKET

因为 N 最多为 10，每种食材可以选或者不选两种情况，所以最多情况数为 2^10=1024 种。搜索时间满足要求。

所以，此题用 DFS 可以非常方便解决。在搜索的时候，我们可以将食材的相关信息带到 DFS 函数的参数中，方便最后答案的求解。

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
26
27
28
29
30
31
32
33
34
35
36
37
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int s[11], b[11], v[11];
int ans = INT_MAX;

/**
 * pt: 当前处理到的食材
 * cnt: 当前选中的食材数量
 * ss: 当前选中的食材的总酸度
 * bb: 当前选中的食材的总甜度
 */
void dfs(int pt, int cnt, int ss, int bb) {
    if (pt == n) {
        if (cnt > 0) {
            ans = min(ans, abs(ss - bb));
        }
        return;
    }
    v[pt] = 1;
    dfs(pt + 1, cnt + 1, ss * s[pt], bb + b[pt]);
    v[pt] = 0;
    dfs(pt + 1, cnt, ss, bb);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> b[i];
    }
    dfs(0, 0, 1, 0);
    cout << ans << endl;
    return 0;
}

P12139 黑白棋

此题是搜索题，需要在中间尽可能检查状态来剪枝，以节省搜索次数。

题目有三类限制，分别可以用在不同的剪枝环节。

限制一：在每一行和每一列中，黑色棋子和白色棋子的数量必须相等（即为 3）。

  • 我们可以对每一行记录黑子和白子的数量，如果某一行或某一列的一种颜色达到 3，后面则不能用这个颜色。

限制二：不能有超过两个相同颜色的棋子连续排列。

  • 我们可以在当前落子的时候，检查它的左边和上面连续的几个格子，看是否有 3 个相同的子。

限制三：行列唯一性

  • 可以放到最后检查。

另外，这个棋盘有几个位置已经设定了值，我们需要标记下来，搜索的时候跳过对这些位置的尝试，但需要在这些位置做合法性检查。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int row_cnt[6][2], col_cnt[6][2];
char tu[7][7], mark[7][7];

bool check(int r, int c) {
    // 在每一行和每一列中，黑色棋子和白色棋子的数量必须相等（即为 3）
    if (row_cnt[r][1] > 3 || row_cnt[r][0] > 3 || col_cnt[c][1] > 3 || col_cnt[c][0] > 3) return false;
    
    // 不能有超过两个相同颜色的棋子连续排列
    if (r >= 2) {
        if (tu[r][c] == '1' && tu[r-1][c] == '1' && tu[r-2][c] == '1') return false;
        if (tu[r][c] == '0' && tu[r-1][c] == '0' && tu[r-2][c] == '0') return false;
    }
    if (c >= 2) {
        if (tu[r][c] == '1' && tu[r][c-1] == '1' && tu[r][c-2] == '1') return false;
        if (tu[r][c] == '0' && tu[r][c-1] == '0' && tu[r][c-2] == '0') return false;
    }
    return true;
}

// 行列唯一性检查
bool final_check() {
    set<int> row_set, col_set;
    for (int i = 0; i < 6; i++) {
        int v = 0;
        for (int j = 0; j < 6; ++j) {
            v = v * 10 + (tu[i][j] - '0');
        }    
        row_set.insert(v);
    }
    if (row_set.size() != 6) return false;
    for (int j = 0; j < 6; ++j) {
        int v = 0;
        for (int i = 0; i < 6; ++i) {
            v = v * 10 + (tu[i][j] - '0');
        }
        col_set.insert(v);
    }
    if (col_set.size() != 6) return false;
    return true;
}

void dfs(int r, int c);
void try_dfs(int r, int c) {
    char ch = tu[r][c];
    row_cnt[r][ch - '0']++;
    col_cnt[c][ch - '0']++;
    if (check(r, c)) {
        int nr = r;
        int nc = c + 1;
        if (nc == 6) {
            nr++;
            nc = 0;
        }
        dfs(nr, nc);
    }
    row_cnt[r][ch - '0']--;
    col_cnt[c][ch - '0']--;
}

void dfs(int r, int c) {
    if (r == 6) {
        if (final_check()) {
            for (int i = 0; i < 6; i++) {
                for (int j = 0; j < 6; j++) {
                    cout << tu[i][j];
                }
            }
            cout << endl;
            // 因为只有一个合法解，所以找到答案就退出
            exit(0);
        }
        return;
    }
    
    if (mark[r][c] == 0) {
        tu[r][c] = '1';
        try_dfs(r, c);
        tu[r][c] = '0';
        try_dfs(r, c);
    } else {
        tu[r][c] = mark[r][c];
        try_dfs(r, c);
    }
}

void init() {
    memset(mark, 0, sizeof(mark));
    mark[0][0] = '1';
    mark[0][1] = '0';
    mark[0][3] = '0';
    mark[1][3] = '0';
    mark[2][4] = '0';
    mark[2][5] = '0';
    mark[4][2] = '1';
    mark[4][5] = '1';
    mark[5][1] = '0';
    mark[5][4] = '1';
}

int main() {
    init();
    dfs(0, 0);
    return 0;
}

P1605 迷宫

用 DFS 来枚举，但需要标记走过的路。

  • 因为最多只有 5x5=25 个格子，所以递归的深度最大只有 25，不存在溢出情况。
  • 因为有陷阱（不能走）和起点终点（不能重复走），所以我们假设平均每次有 2 条支路，
    整个的最坏情况估计只有 2^23=8388608 次，所以也不会超时。

一些陷阱：

  • 终点可能也有障碍物，这个时候始终就到不了。
  • 起点在走之前需要标记，否则会重复走。

参考代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <bits/stdc++.h>
using namespace std;

// 0 - 空地
// 1 - 障碍物
int tu[6][6], n, m, t, sx, sy, ex, ey, ans;

int movex[]={1,-1,0,0};
int movey[]={0,0,-1,1};

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        ans++;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int tox = x + movex[i];
        int toy = y + movey[i];
        if (tox >=1 && tox<=n && toy>=1 && toy<=m && tu[tox][toy]!=1){
            tu[tox][toy]=1;
            dfs(tox, toy);
            tu[tox][toy]=0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> t;
    cin >> sx >> sy >> ex >> ey;
    while (t--) {
        int x, y;
        cin >> x >> y;
        tu[x][y] = 1;
    }
    tu[sx][sy] = 1;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

P2404 自然数的拆分问题

DFS，有两个技巧：

  • 保证后面的数 >= 前面的数。
  • 让每个数必须小于 n，这样不会出现 n=n 这种等式。
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
26
27
28
29
30
31
32
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, tot, v[10];

void dfs(int pt) {
    if (tot == n) {
        cout << v[1];
        for (int i = 2; i < pt; ++i) {
            cout << "+" << v[i];
        }
        cout << endl;
        return;
    }
    for (int i = v[pt-1]; tot + i <=n && i < n ; ++i) {
        tot += i;
        v[pt] = i;
        dfs(pt+1);
        tot -= i;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    v[0] = 1;
    dfs(1);
    return 0;
}

CSPJ 教学总结：STL

2025-04-12 22:00:46

STL 库是 C++ 语言的标准库，我们在比赛中主要用到的有如下内容。

string 类

  • substr
  • find
  • replace
  • insert
  • erase
  • c_str

容器

  • pair
  • vector
  • deque
  • list
  • stack
  • queue
  • priority_queue
  • map
  • unordered_map
  • set
  • unordered_set

算法库

函数 调用示意 说明
sort sort(v.begin(), v.end()) 快速排序
stable_sort stable_sort(v.begin(), v.end()) 稳定排序
unique unique(v.begin(), v.end()) 去重，返回的是去重后的元素末地址。可以结合 erase 函数来把多余数据删除
next_permutation next_permutation(v, v+n) 返回全排列的下一个值，当没有下一个排列时，函数返回 false
prev_permutation prev_permutation(v, v+n) 返回全排列的上一个值，当没有上一个排列时，函数返回 false
nth_element nth_element(v.begin(), v.begin() + k, v.end()), 函数执行后，v.begin()+k 位置的数为排序后的最终位置，即左边的数都小于它，后面的数都大于它
lower_bounds lower_bounds(v, v+n, a) 查找大于或等于 a 的第一个位置，如果没找到则返回 end()
upper_bounds upper_bounds(v, v+n, a) 查找大于 a 第一个位置，如果没找到则返回 end()
equal_range equal_range(v, v+n, a) equal_range 返回一个 pair，first 元素是查找到的匹配 a 值的左边界，second 元素是匹配到的 a 值的右边界，边界为左闭右开原则。当 first == second 的时候，相当于没找到目标值
__gcd __gcd(a, b) 返回 a 和 b 的最大公约数
reverse reverse(v.begin(), v.end()) 将原序列逆序

练习

题号 说明
P1996 约瑟夫问题 适合用 list
P3613 寄包柜 适合用 map 和 pair
P4387 验证栈序列 适合用 stack
P1540 机器翻译 NOIP 2010 提高组，适合用 vector 以及 STL 的 find 算法
P1449 后缀表达式 适合练习 stack
P2058 海港 NOIP 2016 普及组，练习桶和队列
P2234 营业额统计 练习 set 和 lower_bound 函数

P4387 验证栈序列

解法：把 A 数组中的元素住栈里面 push，然后如果栈顶元素和 B 数组的当前元素相同，就 pop，同时 B 数组的当前元素后移。

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
26
27
28
29
30
31
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int t, n, a[100010], b[100010];

int main() {
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) 
            cin >> a[i];
        for (int i = 0; i < n; ++i) 
            cin >> b[i];
        stack<int> q;
        int idx = 0;
        for (int i = 0; i < n; ++i) {
            q.push(a[i]);
            while (!q.empty() && q.top() == b[idx]) {
                q.pop();
                idx++;
            }
        }
        if (q.empty()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

P1540 机器翻译

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    int m, n, t, ans = 0;
    cin >> m >> n;
    vector<int> v; 
    while (cin >> t) {
        if (find(v.begin(), v.end(), t) == v.end()) { // 如果不在内存中
            v.push_back(t); 
            ++ans;
        }
        if (v.size() > m) 
            v.erase(v.begin());
    }
    cout << ans << endl;
}

P1449 后缀表达式

表达式计算:

  • 不停读入。
  • 如果读到数字，就和之前的数字拼接：a = a * 10 + ch - '0'
  • 如果读到 . 就压栈
  • 如果读到运算符，就出栈两个数进行运算，结果再压栈
  • 如果读到 @ 结束
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
26
27
28
29
30
31
32
33
34
35
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

stack<int> s;
int a, v1, v2;

int main() {
    char ch;
    while (cin >> ch) {
        if (ch == '@') break;
        if (ch >= '0' &&  ch <='9') {
            a = a*10 + ch - '0';
        } else if (ch == '.') {
            s.push(a);
            a = 0;
        } else if (ch == '+') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v1 + v2);
        } else if (ch == '-') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v2 - v1);
        } else if (ch == '*') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v1 * v2);
        } else if (ch == '/') {
            v1 = s.top(); s.pop(); v2 = s.top(); s.pop();
            s.push(v2 / v1);
        }
    }
    cout << s.top() << endl;
    return 0;
}

P2058 海港

解法：用一个队列记录所有 24 小时内的船。用一个桶记录每个国家的乘客数量。

  • 每次有新船入队列的时候，更新桶。如果桶更新前是 0，则 ans++
  • 每次新船入队列后，检查最早的队列，如果超24 小时，则出队
  • 出队的时候，更新桶，如果桶的数量减为 0，则 ans-- 
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int t;
    int len;
    vector<int> v;
};

// 桶，记录每个国家的乘客数量
int cnt[100010], n, t, ans;
// 队列
queue<Node> q;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        Node a;
        cin >> a.t >> a.len;
        a.v.resize(a.len);
        for (int j = 0; j < a.len; ++j) {
            cin >> a.v[j];
            if (cnt[a.v[j]] == 0) ans++;
            cnt[a.v[j]]++;
        }
        q.push(a);
        int min_t = a.t - 86400;
        // 检查出列
        a = q.front();
        while (a.t <= min_t) {
            for (int j = 0; j < a.len; ++j) {
                cnt[a.v[j]]--;
                if (cnt[a.v[j]] == 0) ans--;
            }
            q.pop();
            a = q.front();
        }
        cout << ans << endl;
    }
    return 0;
}

P2234 营业额统计

把营业额往 set 里面放，这样数据就是有序的。然后用 lower_bound 查找大于等于 x 的值。

  • 如果找到了，那么波动就是 0
  • 如果没找到，比较当前位置和上一个位置与 x 的差，取较小那个；同时插入 x

取上一个位置的时候要处理一下边界，如果是在 s.begin()位置的话就不用处理了。

取当前位置的时候要处理一下，看看是不是在 s.end()。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

set<int> s;
int n, x, ans;
bool debug = false;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    cin >> x;
    ans = x;
    s.insert(x);
    for (int i = 1; i < n; ++i) {
        cin >> x;
        set<int>::iterator it;
        it = s.lower_bound(x);
        if (it != s.end() && *it == x) {
            continue;
        } else {
            int diff = INT_MAX;
            if (it != s.end()) {
                diff = min(diff, abs(*it-x));
            }
            if (it != s.begin()) {
                it--;
                diff = min(diff, abs(*it-x));
            }
            ans += diff;
            s.insert(x);
        }
    }
    cout << ans << endl;
    return 0;
}

CSPJ 教学思考：数学题

2025-04-12 21:40:39

数学题是信息学竞赛中重要的一类题目，通常包括几何、数论、容斥原理等。

本文将相关的题目归纳整理，用于教学。

几何

P2241 统计方形

本题解法：每个矩形（包括正方形）都可以由一段左边线段和一段上边线段确定。因此，我们只需要枚举所有可能的线段。

对于一个长是 N 宽是 M 的棋盘。

  • 左边的线段长度为 1 的有 N 个，长度为 2 的有 N-1 个，…长度为 N 的有 1 个。
  • 上边的线段长度为 1 的有 M 个，长度为 2 的有 M-1 个，…长度为 M 的有 1 个。

所以:

  • 左边的线段一共有 （1+2+3+...+N）= N*(N+1)/2 个。
  • 上边的线段一共有 （1+2+3+...+M）= M*(M+1)/2 个。
  • 因此，总共有 N*(N+1)/2 * M*(M+1)/2 个矩形。

用相同的办法可以推导正方形的数量，方法如下：

  • 对于左边长度为 1 的线段有 N 个，相应的上边长度为 1 的线段有 M 个。
  • 所以可以构造出 N*M 个边长为 1 的正方形。

同理：

  • 对于左边长度为 2 的线段有 N-1 个，相应的上边长度为 2 的线段有 M-1 个。
  • 所以可以构造出 (N-1)*(M-1) 个边长为 2 的正方形。

以此类推，可以构造出 N*M + (N-1)*(M-1) + (N-2)*(M-2) + (N-M+1)*1 个正方形(N>M)。

另外，需要注意使用 long long 来保存结果。完整的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <bits/stdc++.h>
using namespace std;
unsigned long long n, m, ans1, ans2;
int main() {
    cin >> n >> m;
    ans1 = n*(n+1)/2 * m*(m+1)/2;
    while (n > 0 && m > 0) {
        ans2 += n*m;
        n--; m--;
    }
    cout  << ans2 << " " << ans1 - ans2 << endl;
    return 0;
}

数论

P1044 栈

这道题可以先用暴力的办法把前面几个数打出来，然后我们能发现数的规律是：1,1,2,5,14,42,132,429,1430,….

这是计算组合中很常见的卡特兰数，卡特兰数有两种公式，第一种公式是：

  • f(n) = f(n-1) * (4 * n - 2) / (n + 1)

我个人觉得这个公式不太好记。另一个公式是：

这个递推式相对好记一点：即C(n) = C(0)*C(n-1) + C(1)*C(n-2) ... C(n-1)*C(0)

以下是用该递推式实现的答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

long long ans[19];
int main() {
    int n;
    cin >> n;
    ans[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; ++j) {
            ans[i] += ans[j] * ans[i-1-j];
        }
    }
    cout << ans[n] << endl;
    return 0;
}

P3612 USACO17JAN Secret Cow Code S

这是一道 USACO 的题目，需要我们先找出规律，然后再试图求解。

此题找规律的技巧是分析坐标每次在折半还原时的变化规律。
为了分析规律，我们可以看每次翻倍时，坐标的关系变化。

对于一个长度为 N 的字符串S，每次其长度变为 2*N。所以，我们对每一位进行标号：

1 2 3 4... N N+1 N+2 N+N

其中，除 S[N] == S[N+1] 外（按题意，此项为特殊项），其它位置都符合如下规律：

  • S[1] == S[N+2]
  • S[N-1] == S[N+N]

所以，将右边的坐标减去 N 再减 1，就得到左边的坐标。

所以，设总长为 L, 如果 a 的位置在右半侧，则对应到左半侧的坐标关系是：

  • if (a == L/2+1) a = 1;
  • else a = a - L/2 - 1;

如此递归下去，直到位置落在最初的长度上。
因为字符下标是从 0 开始，所以下标最后要减 1.

最后注意用 long long 来转换坐标。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
 

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

string s;
long long a, n;
bool debug = false;

long long di(long long a, long long L) {
    if (debug) {
        // 可用 debug 查看坐标变化过程
        cout << "test a = " << a << ", L = " << L << endl;
    }
    if (a <= n) {
        return a;
    } else {
        // 如果 a 的位置在右半侧，则调整到左半侧
        if (a > L/2) {
            if (a == L/2 + 1) a = L/2;
            else a = a - L/2 - 1;   
        }
        return di(a, L/2);
    }
}

int main() {
    cin >> s >> a;
    n = s.length();

    // 求出开始往回递归时，字符串拼起来的长度 L
    long long L = n;
    while (L < a) L *= 2;

    // 寻找 L 这个长度下，第 a 个字符相当于哪个位置
    int ans = di(a, L);
    cout << s[ans-1] << endl;
    return 0;
}

CSPJ 教学思考：枚举

2025-04-06 11:20:47

枚举就是把所有情况都尝试一遍。比较简单的用 for 循环即可，较复杂的枚举，需要用到递归。

P1304 哥德巴赫猜想

此题直接枚举每个合数拆解成两个质数和的所有可能性。为了避免重复计算质数，我们用一个 map 将其运算结果保存下来。

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
26
27
28
29
30
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

map<int, bool> rec;
bool isPrime(int n) {
    if (rec.find(n) != rec.end()) {
        return rec[n];
    }
    for (int i = 2; i*i <= n; ++i) {
        if (n % i == 0) return rec[n] = false;
    }
    return rec[n] = true;
}

int main() {
    int n;
    cin >> n;
    for (int i = 4; i <= n; i+=2) {
        for (int j = 2; j <= i; ++j) {
            if (isPrime(j) && isPrime(i-j)) {
                printf("%d=%d+%d\n", i, j, i-j);
                break;
            }
        }
    }
    return 0;
}

P2089 烤鸡

此题初看起来 N 很大，但是每种配料最多 3 克，一共 10 种，总克数最多为 30 克。所以超过 30 克的情况答案都为 0。

每种配料 3 种情况，一共 10 种配料，所以暴力枚举的时间复杂度 3^10 约为 59000，不会超时。

枚举的参考代码如下：

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
26
27
28
29
30
31
32
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > ans;
vector<int> a(10);
int n;
void dfs(int pt, int tot) {
    if (pt == 10) {
        if (tot == n)ans.push_back(a);
        return;
    }
    if (tot >= n) return;
    for (int i = 1; i<=3; i++) {
        a[pt] = i;
        dfs(pt+1, tot+i);
    }
}
int main() {
    cin >> n;
    dfs(0, 0);
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) {
        for (int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

P1706 全排列问题

全排列的问题有多种写法，此题可以直接用 STL 中的 next_permutation 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
/**
 * P1706 全排列问题
 */
#include <bits/stdc++.h>
using namespace std;

int n, v[11];

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        v[i] = i+1;
    }
    do {
        for (int i = 0; i < n; ++i) {
            printf("%5d", v[i]);
        }
        printf("\n");
    } while (next_permutation(v, v+n));
    return 0;
}

P1157 组合的输出

其实组合也可以用 next_permutation 来实现。以 n=5,r=3 为例，具体方法是：

  • 构造一个只有 0 和 1 的数组，0 表示选中，1 表示未选中。
  • 数组初始状态：0 0 0 1 1，这样对应输出的是 1, 2, 3
  • 下一个状态： 0 0 1 0 1， 输出 1, 2, 4
  • 结束状态： 1 1 0 0 0，输出 3, 4, 5

以下是实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, r;
int v[25]={0};

int main() {
    cin >> n >> r;
    for (int i = r; i < n; ++i) {
        v[i] = 1;
    }
    do {
        for (int i = 0; i < n; ++i) {
            if (v[i] == 0) printf("%3d", i+1);
        }
        printf("\n");
    } while (next_permutation(v, v+n));
    return 0;
}

更多全排列的练习：

P3392 涂条纹

  • 这道题可以枚举蓝色色块开始的行号和结束的行号，时间复杂度为 O(N^2)。
  • 对于每一种情况，我们需要 N 的时间复杂度来检查。
  • 所以一共的时间复杂度是 N^3。

我们先预保存下来每行的各种颜色的色块数量，这样检查的时候就可以快速求解。

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
26
27
28
29
30
31
32
33
34
35
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int cnt[55][128];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char ch;
            cin >> ch;
            cnt[i][ch]++;
        }
    }
    int ans = INT_MAX;
    // 枚举蓝色行的起止
    for (int i = 1; i < n; ++i) {
        for (int j = i; j < n-1; ++j) {
            int cost = 0;
            for (int k = 0; k < i; ++k)
                cost += m - cnt[k]['W'];
            for (int k = i; k <= j; ++k)
                cost += m - cnt[k]['B'];
            for (int k = j+1; k < n; ++k)
                cost += m - cnt[k]['R'];
            ans = min(ans, cost);
        }
    }
    cout << ans << endl;
    return 0;
}

P3654 First Step

直接枚举每个起点。但是 k==1 时需要特判，因为 k==1 意味着向下和向右重复计算，需要除以 2。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
/**
 * 
 * 陷阱：
 *  k=1时需要特判，因为k=1意味着向下和向右重复计算，需要除以2。
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, m, k, ans;
char tu[110][110];

bool check(int x, int y, int dx, int dy) {
    int nx = x, ny = y;
    for (int i = 0; i < k; i++) {
        if (nx >= n || ny >= m) return false;
        if (tu[nx][ny] == '#') return false;
        nx += dx;
        ny += dy;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tu[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check(i, j, 1, 0)) ans++;
            if (check(i, j, 0, 1)) ans++;
        }
    }
    if (k == 1) ans /= 2;
    cout << ans << endl;
    return 0;
}

P1149 火柴棒等式

NOIP 2008 提高组第二题。推导如下：

  • n 最大为 24。
  • 24 减去加号（2根火柴）和等号（2 根火柴），还剩 20 根。
  • 20 根分配到 3 个数字（A+B=C）上，平均每个数字 7 根，但也可能一个数特别大（10 根），另一个数特别小（2 根）。
  • 每个数字最少用量为 2 根火柴（数字 1）。

枚举办法：

  • 第 1 个数字 A 从 0 - 10000，计算出 A 用的火柴数 t1
  • 第 2 个数字 B 从 A - 10000，计算出 B 用的火柴数 t2
  • 算出来 A+B 的和 C，检查 C 用的火柴数是不是刚好是 n-t1-t2-4
  • 每找到一种，如果 A!=B，则计算两次答案，因为 B+A=C 是另一个对称的答案。

用以上的枚举之后，我们将所有答案输出，发现 A 其实在 N 最大（N=24）的时候也不会超过 1000，测试如下（只输出了 A<=B 的情况）。所以我们就可以将 A 的范围改小，或者直接打表输出答案。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
0+8=8
0+12=12
0+13=13
0+15=15
0+21=21
0+31=31
0+47=47
0+51=51
0+74=74
0+117=117
0+171=171
0+711=711
1+20=21
1+30=31
1+42=43
1+47=48
1+50=51
1+112=113
1+117=118
1+170=171
1+710=711
2+8=10
2+10=12
2+19=21
2+41=43
2+72=74
2+77=79
2+111=113
3+10=13
3+13=16
3+44=47
3+114=117
4+43=47
4+57=61
4+70=74
4+113=117
4+117=121
5+10=15
5+16=21
5+17=22
6+15=21
7+15=22
7+27=34
7+40=47
7+41=48
7+54=61
7+72=79
7+77=84
7+110=117
7+111=118
7+114=121
9+12=21
11+13=24
11+14=25
11+16=27
11+31=42
11+41=52
11+61=72
14+27=41
14+77=91
17+24=41
17+57=74
17+74=91
41+71=112

完成的程序如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
/**
 * 把 A 和 B 的范围改成 10000，同时把 debug 改成 true 可以输出所有可能的组合。
 * 经过测试发现 A和 B的答案范围小于 1000，所以可以改成 1000。
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int num[] = {6,2,5,5,4,5,6,3,7,6};
unordered_map<int, int> record;
int n, ans;
bool debug = false;

int main() {
    cin >> n;
    // 初始化
    for (int i = 0; i < 20000; i++) {
        int tmp = i;
        int cnt = 0;
        do {
            cnt += num[tmp % 10];
            tmp /= 10;
        }while (tmp > 0);;
        record[i] = cnt;
    }
    
    n -= 4;
    for (int i = 0; i < 1000; i++) {
        for (int j = i; j < 1000; j++) {
            int c = i + j;
            if (record[i] + record[j] + record[c] == n) {
                if (i != j) ans+=2;
                else ans++;
                if (debug) {
                     cout << i << "+" << j << "=" << c << endl;
                }
            }
            
        }
    }
    cout << ans << endl;
    return 0;
}

P3799 小 Y 拼木棒

思路如下：

  • 4 根木棒，先选出三根。肯定是有两根的和等于第三根。
  • 最后一根显然是和第三根一样长。
  • 所以，问题转换成：选两根木棒，同时再选两根他们的和，一共有多少种。

在选两根木棒的时候，我们又可以转化为：选一根木棒，然后选另一根大于等于它的木棒。

因为 a 的值在 5000 以内，而 N 最大是 10 万，所以可以把值放到一个计数的桶里面。这样枚举的时候效率更高。

解法：

  • 拿一个 cnt[] 数组保存每个数字出现的次数，同时记录最大值 maxv。
  • 从 1 到 maxv 枚举 a 和 b（其中保证 b 大于等于 a）
  • 计算两个数字的和 c，然后取 c 的次数。
  • 计算一共的组合数，结果对 10^9+7 取模。

参考代码如下：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;
#define MOD (int)(1e9 + 7)

unordered_map<int, int> cnt;
int n, x, maxv;
long long ans;

// 从 a 个数中选 2 个数的组合数
long long C(long long a) {
    return a * (a - 1) / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        cnt[x]++;
        maxv = max(maxv, x);
    }
    for (int a = 1; a <= maxv; a++) {
        for (int b = a; b <= maxv; b++) {
            if (a == b && cnt[a] < 2) continue;
            int c = a + b;
            if (cnt[c] >= 2) {
                long long base = C(cnt[c]) % MOD;
                if (a == b)  
                    base = base * C(cnt[a]) % MOD;
                else  
                    base = base * ((cnt[a] * cnt[b]) % MOD) % MOD;
                ans = (ans + base) % MOD;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

P1028 数的计算

NOIP 2001 普及组 题目。在暴力枚举的时候，需要记住重复的计算。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, ans, record[1010];

int dfs(int a) {
    if (record[a] != 0) return record[a];
    int ret = 1;
    for (int i = 1; i <= a/2; ++i) {
        ret += dfs(i);
    }
    record[a] = ret;
    return ret;
}

int main() {
    cin >> n;
    ans = dfs(n);
    cout << ans << endl;
    return 0;
}

更多练习

P2437 蜜蜂路线

需要用到高精度。

参考代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

string record[1001][1001];

string add(string a, string b) {
    int len_a = a.length();
    int len_b = b.length();
    int len_max = max(len_a, len_b);
    int carry = 0;
    string ret = "";
    for (int i = 0; i < len_max; i++) { 
        int num_a = i < len_a ? a[len_a - i - 1] - '0' : 0;
        int num_b = i < len_b ? b[len_b - i - 1] - '0' : 0;
        int sum = num_a + num_b + carry;
        ret = to_string(sum % 10) + ret;
        carry = sum / 10;
    }
    if (carry > 0) ret = to_string(carry) + ret;
    return ret;
}

string dfs(int n, int m) {
    if (n > m) return "0";
    if (n == m) return "1";
    if (record[n][m] != "") return record[n][m];
    return record[n][m] = add(dfs(n+1, m), dfs(n+2, m));
}

int main() {
    int n, m;
    cin >> n >> m;
    cout << dfs(n, m) << endl;
    return 0;
}