MoreRSS

site iconDevTang | 唐巧修改

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

Inoreader Feedly Follow Feedbin Local Reader

DevTang | 唐巧的 RSS 预览

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，写起来较繁琐

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;
}

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()) 将原序列逆序

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;
}

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;
}

CSPJ 教学思考：模拟

2025-03-29 23:06:22

模拟是最有效的练习编程熟练度的基础算法，也是有效的掌握各种编程技巧的练习方式。

本文将把各种模拟技巧与题目结合，用题目带着学生掌握这些模拟技巧。

二维数组包边

有些时候，我们在处理二维数组的时候，需要处理 x，y 坐标的边界。这样写起来会比较麻烦，但是，如果我们将数据从下标 1 开始保存，那么就人为在数据外面留了一圈缓冲带。这个时候，在处理 x，y 周围坐标的时候，就不会出现数据下标越界的情况了。

例题：P2670 NOIP 2015 普及组 扫雷游戏

该题如果正常写，需要判断每个格子周围 8 个格子的状态。如果我们把数据从 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
 
/**
 * P2670 [NOIP 2015 普及组] 扫雷游戏
 * 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, m;
char tu[110][110];
int movex[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int movey[] = {-1, 0, 1, -1, 1, -1, 0, 1};

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (tu[i][j] == '*') continue;
            int cnt = 0;
            for (int k = 0; k < 8; ++k) {
                int x = i + movex[k];
                int y = j + movey[k];
                if (tu[x][y] == '*') cnt++;
            }
            tu[i][j] = cnt + '0';
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << tu[i][j];
        }
        cout << endl;
    }
    return 0;
}

例题：B4248 语言月赛 202503 数字棋盘

本题也可以用包边的技巧，保证数据在检查的时候不会越界。参考代码如下：

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
 
#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[1001][1001];
int x, y;

bool check(int i, int j) {
    // 检查上方格子
    if (i > 1 && a[i-1][j] == y) return true;
    // 检查下方格子
    if (i < n && a[i+1][j] == y) return true;
    // 检查左侧格子
    if (j > 1 && a[i][j-1] == y) return true;
    // 检查右侧格子
    if (j < m && a[i][j+1] == y) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> x >> y;
    int count = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == x && check(i, j)) {
                count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

P10719 GESP202406 五级 黑白格

此题需要求枚举从坐标(x,y)到坐标(a,b)的 1 的个数。我们先用将从(0,0)到(a,b)的 1 的个数保存在一个数组 s[110][110]中，然后再通过容斥原理来进行快速求(i,j)到(a,b)中 1 的个数。具体方法如下：

第一步：对于每一个 s[i][j]，满足：s[i][j] = s[i-1][j] + cnt，其中 cnt 为第 i 行前 j 个数中 1 的个数。于是，我们就可以递推求出所有的 s[i][j]，代码如下：

1
2
3
4
5
6
7
 
for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int j = 1; j <= m; j++) {
        cnt += (tu[i][j] == '1');
        s[i][j] = s[i-1][j] + cnt;
    }
}

以上代码使用了“包边”的技巧，因为我们下标是从 1 开始的，所以下标 i-1 不会越界。

第二步：根据容斥原理。从坐标(i,j)到坐标(a,b)的 1 的个数为：s[a][b] - s[i-1][b] - s[a][j-1] + s[i-1][j-1]。如下图所示：

以上公式如果使用“包边”技巧，让有效坐标从 1 开始，也会帮助 i-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
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, m, k, ans;
int s[110][110]; // 表示从(0,0)到(a,b)的 1 的个数
char tu[110][110];

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> tu[i]+1;
    }
    // 从第二行递推
    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= m; j++) {
            cnt += (tu[i][j] == '1');
            s[i][j] = s[i-1][j] + cnt;
        }
    }
    ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int a = i; a <= n; a++) {
                for (int b = j; b <= m; b++) {
                    int cnt = s[a][b] - s[i-1][b] - s[a][j-1] + s[i-1][j-1];
                    if (cnt >= k) {
                        int tmp = (a-i+1) * (b-j+1);
                        if (tmp < ans) ans = tmp;
                    }
                }
            }
        }
    }
    if (ans == INT_MAX) cout << 0 << endl;
    else cout << ans << endl;
    return 0;
}

围圈数数

有一种模拟题，要求我们把人围成一个圈，在圈上数数，然后问你数到的是谁。类似于小时候玩的“点兵点将”游戏，可能是顺时针数，也可能是逆时针数。

对于这种数数题目，最简单的做法是：直接用加减来进行目标的选择。加减之后，下标可能变负数或者超过总数，这个时候进行简单的取模调整，就可以将下标调整正常。

例题：P1563 玩具谜题

此题我们：

  • 用 idx = (idx + b) % n; 来完成顺时针数
  • 用 idx = (idx - b + 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;
#define MAXN int(1e5 + 10)

int n, m;
int face[MAXN];
string name[MAXN];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> face[i] >> name[i] ;
    }

    int idx = 0;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        // 圈内向左 == 圈外向右
        if ((face[idx] == 0 && a == 0)
           || (face[idx] == 1 && a == 1)) {
            idx = (idx - b + n) % n;
        } else {
            idx = (idx + b) % n;
        }
    }
    cout << name[idx] << endl;
    return 0;
}

例题：B4246 环形游走

此题有个技巧：就是走的时候可能绕多圈，这个时候我们先把要走的步数模 n: step % n, 这样就把前面的多圈跳过了，也不会把坐标减成特别特别小的负数。

参考代码如下：

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int current = 0;
    for (int i = 0; i < m; i++) {
        int step = a[current] % n;
        current = (current - step + n) % n;
    }
    cout << current + 1 << endl;
    return 0;
}

更多练习：

例题：B3921 小杨的考试

绕圈一类的问题不止是以上那种真实的圈，也可能是像星期几这样逻辑上的圈（日期就像是一个圈，从星期一到星期日，然后又回到星期一）。

B3921 GESP202312 一级 小杨的考试这道题让我们计算日期。最简单的办法，是让星期几先落到 0-6 的表示法（0 表示星期一，6 表示星期日）。然后我们就可以用简单的加 N 天，然后模 7，快速定位到未来是星期几。对于过去，我们也可以简单通过减 N%7 天，然后减掉差的天数后 +7 再模 7，让结果落到 0-6 上。

参考代码如下：

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

int x, n;
int main() {
    cin >> x >> n;
    x = (x - 1 + n) % 7 + 1;
    cout << x << endl;
    return 0;
}

矩阵操作

矩阵操作这类模拟题，会要求我们在一个二维（或三维）的数组上进行各种操作，包括填充，旋转，查找，合并等。需要我们熟悉各种矩阵操作的技巧。

例题：P5725 求三角形

此题是一道基础的填充题。

  • 对于第一种要求，我们用在二维数组上填充实现。
  • 对于第二种要求，我们直接输出结果，在合适的位置加上一些空格。

示例代码如下：

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

int tu[11][11];
int n;
int main() {
    cin >> n;

    // 处理第一种要求
    int cnt = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            tu[i][j] = cnt++;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            printf("%02d", tu[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    // 处理第二种要求
    cnt = 1;
    int bk = n-1;
    for (int i = 1; i <= n; ++i, bk--) {
        for (int j = 1; j <= bk; ++j) printf("  ");
        for (int j = 1; j <= i; ++j) {
            printf("%02d", cnt++);
        }
        printf("\n");
    }
    
    return 0;
}

例题：P5461 赦免战俘

此题我们需要熟练使用递归来进行标记。参考代码如下：

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

int n, m;
char v[1100][1100];

void mark(int x, int y, int size) {
    if (size == 1) return;
    int half = size/2;
    for (int i = x; i < x+half; ++i) {
        for (int j = y; j < y+half; ++j) {
            v[i][j] = '0';
        }
    }
    mark(x, y+half, half);
    mark(x+half, y, half);
    mark(x+half, y+half, half);
}

int main() {
    cin >> n;
    m = 1<<n;
    memset(v, '1', sizeof(v));
    mark(0, 0, m);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

例题：P5731 蛇形方阵

蛇形方阵是一道基础题，用于练习二维数组上的操作。我使用的模拟技巧是：

  • 定义一个 order 变量，表示当前方向
  • 与 order 变量配合，定义一个 movex 和 movey 数组，表示当前方向的移动

相关代码是：

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

每次移动，先判断是否越界或者已经填充过值：

  • 如果越界或已经填充过值，则改变方向再移动
  • 如果没越界，则移动

关键代码如下：

1
2
3
4
5
 
if (nx < 1 || nx > n || ny < 1 || ny > n || tu[nx][ny] != 0) {
    order = (order + 1) % 4;
    nx = x + movex[order];
    ny = y + movey[order];
}

因为要填充 n*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
33
34
35
36
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int n, x, y, order;
int tu[15][15];
int movex[] = {0, 1, 0, -1};
int movey[] = {1, 0, -1, 0};
int main() {
    cin >> n;
    memset(tu, 0, sizeof(tu));
    x = 1;
    y = 0;
    order = 0;
    for (int i = 1; i <= n*n; i++) {
        int nx = x + movex[order];
        int ny = y + movey[order];
        if (nx < 1 || nx > n || ny < 1 || ny > n || tu[nx][ny] != 0) {
            order = (order + 1) % 4;
            nx = x + movex[order];
            ny = y + movey[order];
        }
        x = nx;
        y = ny;
        tu[x][y] = i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%3d", tu[i][j]);
        }
        printf("\n");
    }
    return 0;
}

例题：P4924 魔法少女小Scarlet

本题涉及矩阵的旋转，实际操作起来还是有点麻烦。这里我们按旋转的中心来重建坐标系的话，可以观察到如下规律：

  • 顺时针旋转：(a, b) -> (b, -a)
  • 逆时针旋转：(a, b) -> (-b, a)

这样，我们就可以构建关键的旋转代码了，假如我们是基于中心点 (x, y) 半径是 r 的顺时针旋转的话，那么，对于坐标 (a, b)，我们：

  • 首先：把它移动到以 (x, y) 为中心：(a-x, b-y)
  • 然后：我们把坐标按上面的规则变换成 (b-y, x-a)
  • 最后：我们把坐标加上 (x, y) 的偏移，还原成原始坐标：(b-y+x, x-a+y)

以上逻辑写成代码是：g[b-y+x][x-a+y]=f[a][b]

同理，如果是逆时针旋转：

  • 首先：把它移动到以 (x, y) 为中心：(a-x, b-y)
  • 然后：我们把坐标按上面的规则变换成 (y-b, a-x)
  • 最后：我们把坐标加上 (x, y) 的偏移，还原成原始坐标：(y-b+x, a-x+y)

以上逻辑写成代码是：g[y-b+x][a-x+y]=f[a][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
32
33
34
35
36
37
38
39
40
41
42
43
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

#define MAXN 510
int f[MAXN][MAXN], g[MAXN][MAXN];
int n, m;
int main() {
    cin >> n >> m;
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = cnt++;
        }
    }
    for (int i = 1; i <=m; ++i) {
        int x, y, r, z;
        cin >> x >> y >> r >> z;
        if (z == 0) {
            for (int a = x-r; a <= x+r; ++a)
                for (int b = y-r; b <= y+r; ++b)
                    g[b-y+x][x-a+y]=f[a][b];

        } else {
            for (int a = x-r; a <= x+r; ++a)
                for (int b = y-r; b <= y+r; ++b)
                    g[y-b+x][a-x+y]=f[a][b];
        }
        
        for (int a = x-r; a <= x+r; ++a)
            for (int b = y-r; b <= y+r; ++b)
                f[a][b] = g[a][b];
    } // end of m
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

例题：P1205 USACO1.2 方块转换 Transformations

此题需要推导矩阵旋转的规律。我们可以把原坐标和新坐标写下来，做成一个表格。

然后，我们把坐标的变化写成下面的表格形式：

通过观察，我们发现：

  • 黄色和红色的坐标在变换前后刚好相等，即： 新 x = 原 y
  • 两侧的白色的坐标加和刚好等于 n-1，即：原 x + 新 y = n - 1 => 新 y = n - 原 x - 1

综上，坐标变换公式为：新(y, n-x-1)=原(x, y) 。

所以，坐标变换相关代码为：

1
2
3
4
5
 
for (int x = 0; x < n; ++x) {
    for (int y = 0; y < n; ++y) {
        tmp[y][n-x-1] = ori[x][y];
    }
}

与此类似，我们可以推出“反射”的代码关系是 新(x,n-y-1)=原(x,y)，相关变换代码为：

1
2
3
4
5
 
for (int x = 0; x < n; ++x) {
    for (int y = 0; y < n; ++y) {
        tmp[x][n-y-1] = ori[x][y];
    }
}

完整的参考代码如下（可以把 debug 变量设置成 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
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

char ori[12][12], dest[12][12];
char tmp[12][12], tmp2[12][12];
int n;
bool debug = false;

bool match(char a[12][12], char b[12][12]) {
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            if (a[x][y] != b[x][y]) return false;
        }
    }
    return true;
}

void print(char a[12][12]) {
    for (int i = 0; i < n; ++i) {
        cout << a[i] << endl;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> ori[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> dest[i];
    }
    // 方案一
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp[y][n-x-1] = ori[x][y];
        }
    }
    if (debug) {
        cout << "debug 1: " << endl;
        print(tmp);
    }
    if (match(tmp, dest)) {
        cout << "1" << endl;
        return 0;
    }
    // 方案二
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp2[y][n-x-1] = tmp[x][y];
        }
    }
    if (match(tmp2, dest)) {
        cout << "2" << endl;
        return 0;
    }
    // 方案三
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp[y][n-x-1] = tmp2[x][y];
        }
    }
    if (match(tmp, dest)) {
        cout << "3" << endl;
        return 0;
    }
    // 反射
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp[x][n-y-1] = ori[x][y];
        }
    }
    if (match(tmp, dest)) {
        cout << "4" << endl;
        return 0;
    }
    // 反射+旋转90
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp2[y][n-x-1] = tmp[x][y];
        }
    }
    if (debug) {
        cout << "debug 5-1: " << endl;
        print(tmp2);
    }
    if (match(tmp2, dest)) {
        cout << "5" << endl;
        return 0;
    }
    // 反射+旋转180
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp[y][n-x-1] = tmp2[x][y];
        }
    }
    if (debug) {
        cout << "debug 5-2: " << endl;
        print(tmp);
    }
    if (match(tmp, dest)) {
        cout << "5" << endl;
        return 0;
    }
    // 反射+旋转270
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            tmp2[y][n-x-1] = tmp[x][y];
        }
    }   
    if (debug) {
        cout << "debug 5-3: " << endl;
        print(tmp2);
    }
    if (match(tmp2, dest)) {
        cout << "5" << endl;
        return 0;
    }
    // 不改变
    if (match(ori, dest)) {
        cout << "6" << endl;
        return 0;
    }
    cout << "7" << endl;
    return 0;
}

更多练习：

游戏模拟

游戏模拟类的题目通常会告诉你一个相对复杂一点的游戏规则，然后让你用程序将这个游戏规律实现，最终将游戏的结果输出出来。

这种题目一方面考查了读题能力，需要对游戏规则的理解清楚，另一方面则是要对游戏规则进行建模，用合适的数据结构实现游戏中的模拟。

以下是一些相关的题目。

题号 描述
P1042 NOIP 2003 普及组 乒乓球
P1328 NOIP 2014 提高组 生活大爆炸版石头剪刀布
P1518 USACO2.4 两只塔姆沃斯牛 The Tamworth Two
P1089 NOIP 2004 提高组 津津的储蓄计划
P1161 数组标记

滑动窗口

例题：P1614 爱与愁的心痛

此题的解法是：构造一个“滑动的窗口”。先求出前 m 个数的和，这相当于窗口的原始位置。之后每次让窗口往右移动一格。每次移动的时候，会将最左侧的数字剔除，同时纳入一个新数字。如下图所示：

我们在滑动窗口的时候，需要用这个变量，分别指向：

  • 当前窗口最左的数字 p1
  • 当前窗口下一个要加入的数字 p2
  • 在滑动的时候，不断更新当前窗口的值 tot

以下是关键代码：

1
2
3
4
5
6
7
8
 
p1 = 0;
p2 = m;
while (p2 < n) {
    tot -= v[p1];
    tot += v[p2];
    ans = min(ans, tot);
    p1++; p2++;
}

完整代码如下：

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 n, m, tot, ans;
int p1, p2;
int v[3300];
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    // 初使化滑动窗口
    tot = 0;
    for (int i = 0; i < m; ++i) {
        tot += v[i];
    }
    ans = tot;
    p1 = 0;
    p2 = m;
    // 滑动窗口，更新值
    while (p2 < n) {
        tot -= v[p1];
        tot += v[p2];
        ans = min(ans, tot);
        p1++;
        p2++;
    }
    cout << ans << endl;
    return 0;
}

模拟输入输出

有一些模拟需要我们有比较复杂的输入和输出操作技巧。在模拟输入和输出的时候，常用的两个函数是 sscanf 和 snprintf，其中：

  • sscanf 允许我们从一个字符串中读入内容。
  • snprintf 允许我们将输出内容先输出到一个字符串中。

以下我们用例题来演示其用法。

例题：P1957 口算练习题

此题的输入长度不固定，我们需要先判断输入的长度。同时，输出的时候，我们还需要输出“输出内容”的长度。这对我们处理输入和输出都带来了挑战。

我们可以把表达式整行整行读入，再用 sscanf 和 snprintf 来进行分析处理。以下是相关的示意：

1
2
3
4
 
int a, b;
char s[100], out[100];
sscanf(s, "%d%d", &a, &b);
snprintf(out, sizeof(out), "%d+%d=%d", a, b, a + b);

另外，我们还需要一次读入一整行，我用的方法是用 scanf, 代码如下：

1
2
 
scanf("%[^\n]", s);
getchar();

需要注意，以上代码每读入一行，需要用 getchar() 将行末的换行给读掉。

我们也可以用 cin.getline(s, sizeof(s)); 来读取数据。

以下是完整的示意代码：

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, a, b;
char ch, s[100], out[100];

int main() {
    scanf("%d", &T); getchar();
    while (T--) {
        scanf("%[^\n]", s); getchar();
        if (s[0] >='0' && s[0] <= '9') { // 也可使用函数： isdigit(s[0])
            sscanf(s, "%d%d", &a, &b);
        } else {
            sscanf(s, "%c%d%d", &ch, &a, &b);
        }
        memset(out, 0, sizeof(out));
        if (ch == 'a') {
            snprintf(out, sizeof(out), "%d+%d=%d", a, b, a + b);
        } else if (ch == 'b') {
            snprintf(out, sizeof(out), "%d-%d=%d", a, b, a - b);
        } else if (ch == 'c') {
            snprintf(out, sizeof(out), "%d*%d=%d", a, b, a * b);
        }
        printf("%s\n", out);
        printf("%lu\n", strlen(out));
    }
    return 0;
}

以上的 scanf 部分如果替换成 cin，示意代码如下：

1
2
3
4
5
6
7
8
9
 
int main() {
    cin >> T;
    cin.getline(s, sizeof(s));
    while (T--) {
        cin.getline(s, sizeof(s));
        // 省略
    }
    return 0;
}

例题：P1067 多项式输出

此题是 NOIP 2009 普及组的题目。此题练习了 snprintf 的使用。同时，此题用 printf 的 %+d 可以保证正数输出带+号。

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

int n;
string ans;
char outs[100];

int main() {
    ans = "";
    cin >> n;
    for (int i = n; i>=0; i--) {
        int a;
        cin >> a;
        // 系数为0，跳过
        if (a == 0) continue;
        // 指数为0，单独处理
        if (i == 0) {
            memset(outs, 0, sizeof(outs));
            snprintf(outs, sizeof(outs), "%+d", a);
            ans += outs;
        } else {
            // 先处理系数
            if (a == 1) {
                snprintf(outs, sizeof(outs), "+x");
            } else if (a == -1) {
                snprintf(outs, sizeof(outs), "-x");
            } else {
                snprintf(outs, sizeof(outs), "%+dx", a);
            }
            ans += outs;
            // 再处理指数
            memset(outs, 0, sizeof(outs));
            if (i == 1) {
                snprintf(outs, sizeof(outs), "");
            } else {
                snprintf(outs, sizeof(outs), "^%d", i);
            }
            ans += outs;
        }
    }
    if (ans[0] == '+') {
        ans = ans.substr(1);
    }
    cout << ans << endl;
    return 0;
}

P1010 NOIP 1998 普及组 幂次方

此题的技巧是利用递归来循环处理。特殊情况是 2^1 写作 2，而不是 2(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
36
37
 
/* 
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

string conv(int n) {
    if (n == 0) return "0";
    else if (n == 1) return "2(0)";
    else if (n == 2) return "2";
    else {
        string ret = "";
        int base = 1;
        int cnt = 0;
        while (n >= base) {
            if (n & base) {
                string sub = "";
                if (base == 2) sub = "2";
                else sub = "2("+conv(cnt)+")";

                if (ret == "") ret = sub;
                else ret = sub + "+" + ret;
            }
            base <<= 1;
            cnt++;
        }
        return ret;
    }
}


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

更多练习：

其它模拟题目

待补充。

题号 描述