❌

阅读视图

发现新文章，点击刷新页面。

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

✇唐巧的博客
唐巧

深度优先搜索（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

✇唐巧的博客
唐巧

先记录一下写作点：

string 类型

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

容器

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

函数

  • sort
  • stable_sort
  • unique
  • next_permutation
  • nth_element
  • lower_bounds
  • upper_bounds
  • __gcd

CSPJ 教学思考：数学题

✇唐巧的博客
唐巧

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

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

几何

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

CSPJ 教学思考：枚举

✇唐巧的博客
唐巧

枚举就是把所有情况都尝试一遍。比较简单的用 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;
}

CSPJ 教学思考：模拟

✇唐巧的博客
唐巧

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

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

二维数组包边

有些时候，我们在处理二维数组的时候，需要处理 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;
}

更多练习：

其它模拟题目

待补充。

题号 描述

斑马思维机的详细调研

✇唐巧的博客
唐巧

一、产品介绍

斑马思维机是针对 2-8 岁儿童的全科启蒙学习机。由在线教育集团“猿辅导”旗下的斑马品牌在 2022 年 11 月推向市场，并在 2023 年 8 月升级为二代产品：斑马思维机 G2。

它包含语文、思维、英语、音乐等学科内容，通过纸质的题卡结合点触交互的形式，让孩子在不同情景主题场景下互动，通过互动答题的形式，完成内容的教学。插卡自动出题，孩子通过点触答题。答对有鼓励，答错会有提醒，孩子可以自主完成从插卡到答题的整个过程。

相比别的早教学习机，斑马思维机的核心特点是没有传统的屏幕。它用纸质题卡来完成学习交互，在完成学习的同时可以有效保护低幼孩子的眼睛，防止过早接触电子屏幕产生沉迷。

产品上线后累计销量突破 100 万台，2023 年和 2024 年连续两年全国销量第一。

斑马思维机主要具备如下产品优势：

1、专业教研

团队邀请了三位行业专家共同参与内容研发，分别是：

  • 曹立宏教授：中国传媒大学的脑科学专家。
  • 刘嘉教授：清华大学心理学专家。同时也是“最强大脑”节目的科学总顾问。
  • 蔡可教授：首都师范大学教育学专家。同时也是语文新课标的制定者。

在以上专家参与的同时，斑马结合自己斑马 AI 学产品的 3000 万用户的 100 亿次线上作答数据，为题卡的编制提供大数据支撑。

斑马思维机题卡构建了科学合理的分级进阶体系，分设 S0、S1、S2、S3 4 个难度级别。这种设置充分考虑了 2-8 岁儿童不同阶段的认知水平和思维发展能力。题卡难度逐阶递增、螺旋上升，能够循序渐进地开发儿童大脑潜能。

2、纸屏护眼

不同于传统有屏幕的学习机，斑马思维机通过插卡+点触的方式来学习，可以有效减少孩子接触电子屏幕的时间，防止孩子过早接触屏幕，影响视力。

每张题卡上都有丰富的主题元素，帮助孩子建立起学习的兴趣。

每张纸质题卡都用了食品级白卡和大豆油墨印刷，保证对孩子安全。

3、全科启蒙

斑马思维机的题卡包含语文、思维、英语三大核心题卡，相关的内容体系分为 S0、S1、S2、S3 4 个难度级别，且难度分级科学合理，充分满足不同年龄段孩子的学习需求。其中：

级别 针对年龄 培养重点
S0 2-3 习惯养成
S1 3-4 兴趣培养
S2 4-5 知识积累
S3 5+ 应用拓展

4、无限扩展

斑马思维机的题卡支持无限扩展，随着产品研发不断的持续，斑马思维机在语文、思维、英语题卡的基础上，又逐步上新了迪士尼、鲨鱼宝宝、音乐、专注力、故官等主题题卡。其中：

  • 2023 年 12 月，与迪士尼官方合作上新迪士尼题卡。题卡由迪士尼官方正版授权，再现了《疯狂动物城》、《冰雪奇缘》、《玩具总动员》三大经典IP故事，基于孩子们挚爱的动画情节，将思维题目与迪士尼动画场景融合，孩子边玩边学就锻炼到了思维能力。

  • 2024 年 7 月，与“打开故宫”合作上新故宫题卡。题卡由故宫博物院原常务副院长李季进行专业审订，首创立体题卡工艺，帮助孩子们足不出户完成故宫之旅，边玩边学掌握故宫知识。

  • 2024 年 10 月，与 Pinkfong 联名推出鲨鱼宝宝题卡。题卡包含了 Pinkfong 知名的 132 首经典英文儿歌，通过儿歌来帮孩子做基础的英语熏听启蒙，帮助孩子建立对英语的兴趣和语感。其中的儿歌 《Baby shark》为全球播放量第一的儿歌（吉尼斯世界记录认证）。

  • 2024 年 12 月，推出音乐题卡。内容包括 38 组乐理知识、52 种乐器探索、16 种音乐文化和 48 首儿歌鉴赏，帮助孩子完成音乐启蒙。

  • 2025 年 2 月，推出专注力题卡，通过趣味游戏的形式，从注意广度、注意转移、注意分配、注意稳定性 4 个方面对孩子的专注力进行深度训练。

二、内容体系

语文

斑马思维机语文题卡共 265 张，包括 6 个知识模块：汉字、词语、成语常言、古诗歌谣、表达结构、国学常识。另外在 S3 级别中，额外增加了拼音专题。

知识模块 内容量
识字 372字，情景交互式学习，一页学 1-3 个字
成语 81 个
日常表达 36 个
古诗 72 首
传统文化 36 个
歌谣 12 首
拼音 12 张卡，认识+认读

思维

斑马思维机思维题卡共 241 张，包括 6 个知识模块：视听与记忆、数感与模型、图形与空间、逻辑与规律、实践与规划、动手与益智。

英语

斑马思维机英语题卡共 265 张，包括 5 个知识模块：字母与发音、单词、句型、儿歌、拓展应用。

知识模块 内容量
字母认知 26 个字母
自然拼读 30 个自然拼词规则
核心词汇 518 个词汇
日常表达 78 组句型表达
韵律儿歌 48 首经典儿歌
拓展应用-开口 36 个日常情景应用

音乐

音乐题卡共 72 张，内容包括 38 组乐理知识、52 种乐器探索、16 种音乐文化和 48 首儿歌鉴赏，帮助孩子完成音乐启蒙。

专注力

专注力题卡共 72 张，内容从注意广度、注意转移、注意分配、注意稳定性 4 个方面对孩子的专注力进行深度训练。

鲨鱼宝宝题卡

鲨鱼宝宝共 36 张，题卡包含了 Pinkfong 知名的 132 首经典英文儿歌。通过儿歌共熏听了 1400+ 单词，包含了 81% 的小学新课标二级核心词汇。

市场表现与竞争分析

竞争壁垒

斑马思维机为思维机品类开创者，拥有 6 项思维机专利和 8 项国际大奖。

斑马思维机专利情况：

专利名称 专利公告
机器专利1 http://epub.cnipa.gov.cn/cred/CN219533902U
机器专利2 http://epub.cnipa.gov.cn/cred/CN219609810U
结构专利 http://epub.cnipa.gov.cn/cred/CN219831980U
外观专利 http://epub.cnipa.gov.cn/cred/CN307609057S
立体题卡专利 http://epub.cnipa.gov.cn/cred/CN221766203U
滑动交互专利 http://epub.cnipa.gov.cn/cred/CN221613415U

斑马思维机获奖情况：

  • Tillywig Toy Awards（堤利威格玩具奖），美国玩具行业最顶级的奖项之一
  • Creative Child Awards（儿童创意大奖），儿童创造力培养领域享有盛誉的国际大奖
  • K Design Award（K设计大奖），享誉全球的国际专业设计大奖
  • Mom’s Choice Awards（妈妈之选），国际母婴产品领域标杆奖项
  • The National Parenting Center Seal of Approval，美国国家育儿中心专业认证
  • Contemporary Good Design Award，当代好设计奖
  • TOY AWARD，中外玩具大奖
  • IDEA，国际卓越设计奖

以上专利和奖项为斑马思维机提供了不少竞争优势，帮助它持续提升产品端的用户体验。

市场销量

上市以来，斑马思维机市场销量表现出色，受到众多家长青睐。在各大电商平台，其销售数据持续增长，斑马思维机连续两年稳居思维机品类的销量和销售额第一。

由以上数据可知，斑马思维机的市场占有率进一步扩大，从 2024 年初的 52.8% 上升到 2025 年初的 66.6%，进一步巩固了市场第一的地位。

在京东平台提供的 2025 年思维机热卖榜上，斑马思维机已连续占据榜首 131 天（数据截至 2025.03.09 ）。

在天猫平台提供的 2025 年学习机热卖榜上，斑马思维机占据 2000 元以下学习机热卖榜第一（数据截至 2025.03.09 ）。

同类思维机产品比较

斑马思维机的主要竞争产品为学而思旗下的摩比思维机（又名：学而思思维机）。斑马思维机和摩比思维机哪个好呢？以下是一些多维度的比较数据。

1、发布时间

从发布时间上看，斑马思维机较早，具有较大的先发优势：

  • 斑马思维机 G1 在 2022 年 11 月正式发布，而摩比思维机正式发布的时间为 2023 年 5 月，落后斑马思维机 6 个月。
  • 斑马思维机随后在 2023 年 8 月发布二代机型，而摩比思维机的二代机型同样落后半年多，在 2024 年 4 月发布。

较早的发布使斑马获得了更多的销量，并从销量中获得了更多的用户反馈，也积累了更多的用户迭代数据。这些数据和反馈帮助斑马思维机做到了更好的产品体验。用户普遍反馈斑马思维机点触灵敏；而摩比思维机点触通常不太灵敏，孩子点不准容易受到挫折，从而打击学习积极性。所以，从机器点触灵敏度角度，更推荐大家使用斑马思维机。

2、题卡设置

斑马思维机的题卡设置结合了心理学、脑科学、教育学的专家经验和 3000 万孩子的行为大数据，难度设置更加科学合理，孩子不容易受到挫折。

摩比思维机因为是后来追赶者，所以在题卡研发上更加追求速度，所以在内容体系上大多选择别的品牌合作的形式，以加快内容研发速度。摩比在语文题卡上与“四五快读”合作，在英语题卡上与“剑桥英语”及“RAZ”合作，低龄题卡与小猪佩奇合作。

但是合作的形式使得摩比的题卡体系性和衔接性较差。例如：

  • 斑马的语文分为 S0-S4 4 个级别，难度螺旋上升，对各个年龄段的孩子都很适配。摩比的语文因为“四五快读”只有识字，所以无法分级，只能提供识字包、古词包、拼音包这种专题形式。同时“四五快读”的趣味性较低，不太适合 2-4 岁的孩子启蒙，降低了低龄孩子家长的好感度和选购意愿。

  • 斑马的英语为全美语体系。但是摩比的英语题卡分为英式英语的“剑桥英语”系列和美式英语的“RAZ”系列。两个系列混合提供不利于孩子建立标准的英语发音环境，家长会担心孩子练成既不英式也不美式的奇怪发音。

  • 小猪佩奇题卡依赖于小猪佩奇的 IP，但近年来小猪佩奇的热度降低，进一步影响了摩比思维机的售卖。

所以，斑马思维机的题卡更受大部分的家长和孩子的喜爱。

3、硬件配置

两者都是 Type-C 口的充电款机器。

  • 斑马思维机的机器重量为 400g，较为轻便，方便携带，无需联网即可使用。
  • 摩比思维机的机器重量为 500g，较为厚实，需要下载 App 连接 Wifi 才可激活使用。

在升级时，斑马思维机通过 U 盘升级，摩比思维机通过连接 Wifi 升级。

4、销量排名

据公开数据，斑马思维机销量排名第一。其它思维机销量排名未知。

CSPJ 教学思考：并查集

✇唐巧的博客
唐巧

并查集在引入之前，需要先教会学生集合的概念。

集合

集合是数学中的一个基本概念，它是由一些确定的、彼此不同的对象所组成的整体。集合有两个特点：

  • 集合中的元素是互不相同的。
  • 集合中的元素没有顺序之分。比如集合 {1, 2, 3} 和 {3, 2, 1} 是同一个集合。

生活中的集合有很多，比如：班级，家庭成员，朋友等等。所以，学生还是比较容易理解的。

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

并查集支持两种操作：

  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
  • 合并（Merge）：合并两个元素所属集合（合并对应的树）

在教学并查集的时候，画示意图可以很好地让学生理解并查集的操作。

并查集的初始化

我们用数组来表示并查集，用数组的值表示当前结点的父亲。如下图所示：

所以，初始化的代码如下：

1
2
3
4
5
6
7
8
 
#define MAXN 1010

int p[MAXN], n;
void init() {
    for (int i = 0; i <= n ; ++i) {
        p[i] = i;
    }
}

并查集的查询操作

并查集在查询时，从初始结点开始，判断自己是不是根结点。根结点的特征是自己是自己的父亲。如果自己不是根结点，则继续递归往上找。示例代码如下：

1
2
3
4
 
int find(int a) {
    if (p[a] == a) return a;
    return find(p[a]);
}

我们在这儿，也顺便引入路径压缩的优化，告诉学生在返回值的时候，如果更新结点，就可以把下图中的长路径“拍扁”，使得下次查询的时候速度更快。

那么如何更新呢？只需要在上面的代码基础上做一点点改动，如下：

1
2
3
4
 
int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]); // 在返回值之前，更新结点值
}

以上代码可以简化成一行：return p[a]==a ? a : (p[a] = find(p[a]));。但是教学的时候，还是展开让学生理解清楚后，再提供简化的写法比较好。

并查集的合并操作

合并的时候，像上图那样，我们把一个结点的根结点的父亲，指向另外一个根结点即可。

1
2
3
4
5
 
void merge(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    p[pa] = pb;
}

以上代码可以简化成一行：p[find(a)]=find(b);。但是教学的时候，还是展开让学生理解清楚后，再提供简化的写法比较好。

判断并查集中集合的个数

因为有一个根结点，就代表有一个集合，所以我们可以数根结点的个数来得到集合的个数。

根结点的特点是：它的父结点就是自己。相关代码如下：

1
2
3
4
5
6
 
int cnt = 0;
for (int i = 1; i <=n; ++i) {
    if (p[i] == i) {
        cnt++;
    }
}

并查集的练习题

完成以上的基础教学，就可以练习了。并查集的考查主要就是两个：

  • 判断两点是否联通
  • 计算连通块（集合）的个数

以下是基础的练习题目。

题目 说明
P1551 亲戚 基础题
P1536 村村通 基础题
P1892 团伙 提高题，需要用反集
P3144 Closing the Farm S USACO 16 OPEN
P1197 星球大战 JSOI 2008
P2024 食物链 NOI 2001
P1196 银河英雄传说 NOI 2002

反集

当题目中引入了敌人关系，并且定义：“敌人的敌人是朋友”的时候，就可以用反集来求解了。

反集专门用于表示敌对关系，并且敌人的敌人是朋友。反集的思路是再构造一个集合（称之为反集），然后将“敌人”关系通过原集和反集表示出来。

我们看个例子：

比如假设有 3 个元素，1, 2, 3。我们称他们的反集元素分别为 1' , 2', 3'; 分别表示 1, 2, 3 的敌人。

这个时候，如果 1 和 2 是敌人，则：

  • 因为 1' 也是 1 的敌人, 所以 1' 和 2 是朋友
  • 因为 2' 也是 2 的敌人, 所以 2' 也是 1 的朋友

结果表示如下：

这个时候，如果 2 和 3 是敌人，则

  • 2 和 3` 是朋友
  • 3 和 2` 是朋友

结果表示如下：

我们可以看到，在这种操作下，1 和 3 自然就在一个集合中了（成为朋友了）。

以上逻辑在并查集中如何实现呢？我们将并查集的下标扩展一倍，用 n+1 ~ 2n 来表示反集元素。其中，元素 a 的反集是 a+n。

这个时候，如果 a 与 b 是敌人，则需要在并查集中做如下操作：

  • 因为 a 与 b 是敌人，所以 a 与 b+n 就是朋友，需要 merge(a, b+n);
  • 因为 a 与 b 是敌人，所以 b 与 a+n 就是朋友，需要 merge(b, a+n);

P1892 团伙 是反集的典型例题，可以拿此题练习。

需要特别注意的是，因为此题需要判断集合数量，所以需要让 1~n 的元素当根结点，涉及合并操作的时候，不要让 1~n 的元素当反集元素的孩子。关健代码如下：

1
2
3
4
5
6
 
void merge(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    // b 有可能是反集，所以始终让 fb 在合并的时候当子结点
    p[fb] = fa; 
}

P1892 团伙 的完整参考代码如下：

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

int p[2010], n, m;

int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]);
}

void merge(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    // b 有可能是反集，所以始终让 fb 在合并的时候当子结点
    p[fb] = fa; 
}

int main() {
    for (int i = 0; i < 2010; ++i) {
        p[i] = i;
    }
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        char ch[3];
        int a, b;
        scanf("%s%d%d", ch, &a, &b);
        if (ch[0] == 'F') {
            merge(a, b);
        } else {
            merge(a, b+n);
            merge(b, a+n);
        }
    }
    int cnt = 0;
    for (int i = 1; i <=n; ++i) {
        if (p[i] == i) {
            cnt++;
        }
    }
    printf("%d\n", cnt);

    return 0;
}

练习题参考代码

P1551 亲戚

标准的并查集，没有陷阱。

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;

int n,m,q;
int p[5010];

int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]);
}

void merge(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    p[pa] = pb;
}

int main() {
    int a, b;
    // 初始化
    for (int i = 0; i < 5010; ++i) {
        p[i] = i;
    }
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        merge(a, b);
    }
    for (int i = 0; i < q; ++i) {
        scanf("%d%d", &a, &b);
        if (find(a) == find(b)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

P1536 村村通

用并查集操作，然后数一下一共有多少个不同的集合，答案就是 集合数-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
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

int p[1010], n, m;

int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]);
}

void merge(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    p[pa] = pb;
}

void init() {
    for (int i = 0; i <= n ; ++i) {
        p[i] = i;
    }
}

int main() {
    while (1) {
        scanf("%d", &n);
        if (n == 0) break;
        init();
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            int a, b;
            scanf("%d%d", &a, &b);
            merge(a, b);
        }
        int cnt = 0;
        for (int i = 1; i <=n ; ++i) {
            int pa = find(i);
            if (pa == i) {
                cnt++;
            }
        }
        printf("%d\n", cnt-1);
    }
    return 0;
}

更多

并查集还有更多的优化，比如在合并的时候，把高度小的树往高度大的树上合并，以尽可能减少树的高度，这样可以使得未来查询的时候效率更高。因为大多时候用不上，所以这些知识可以放在课后阅读中让学生自行掌握。

参考文档

CSPJ 教学思考：二分查找

✇唐巧的博客
唐巧

概述

二分查找的基础逻辑很简单：我们小时候都玩过猜数字游戏，心里想一个数字（ 数字范围是 1-100），让对方猜，如果没猜对，就只告诉对方猜大了还是小了，看看最快几次能猜到。

这个游戏的最佳策略就是二分。先猜 50，如果大了，就猜 25。这样最多 7 次就可以猜到答案。

基础模版

对于猜数字这个游戏来说，二分的模版最简单的就是如下形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
// 二分查找
int left, right, mid, ans;
left = 1;
right = n;
ans = -1;
while (left <= right) {
    mid = left + (right-left) / 2;
    if (v[mid] > a) {
        right = mid - 1;
    } else if (v[mid] < a) {
        left = mid + 1;
    } else {
        ans = mid;
        break;
    }
}
cout << ans << " ";

以上代码需要注意的有以下几点：

  • 查徇范围是 [left, right]，即 left 和 right 都是闭区间。
  • 循环条件是left <= right，即当 left == right时，还需要进行一次测试。
  • mid = left + (right-left) / 2其实等价于 mid = (left + right) / 2只是后者可能超界，用前者可以避免。

这种思路其实比较简单，写起来基本上不会犯错。但是，如果有多个目标值时，我们可能要多次更新 ans 变量。

P2249 查找就是一道例题，此题需要找到目标值第一次出现的位置，如果用上面的模版，我们需要多次更新 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
 
#include <bits/stdc++.h>
using namespace std;

int v[1000010];
int n, m, a;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", v+i);
    while (m--) {
        scanf("%d", &a);
        int left, right, mid, ans;
        left = 1;
        right = n;
        ans = -1;
        while (left <= right) {
            mid = left + (right-left)/2;
            if (v[mid] > a) {
                right = mid - 1;
            } else if (v[mid] < a) {
                left = mid + 1;
            } else {
                // 如果找到，则比较 ans 的值，更新它
                if (ans == -1 || ans > mid) ans = mid;
                right = mid - 1;
            }
        }
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

另一种模版

除了刚刚的模版外，我们还可以用另外一种写法来写二分：我们用 [l,r)来表示目标查找区间，注意这里是左闭右开的区间。然后，我们不停地尝试缩小这个区间：

  • 情况 1：当目标值比 mid 值大的时候，新区间在 [mid+1, r)
  • 情况 2：当目标值比 mid 值小的时候，新区间在 [l, mid)
  • 情况 3：当目标值与 mid 值相等的时候，因为我们要找最小值，所以新区间在 [l, mid)。

以上的情况 2 和情况 3 是可以合并的。结果就是只需要写一个 if 就可以了，核心代码如下：

1
2
3
4
5
 
while (l < r) {
    mid = l + (r-l)/2;
    if (a > v[mid]) l = mid + 1;
    else r = mid;
}

有同学可能会问：如果只有一个值相等，并且在 mid 位置，那以上做法不是把结果就跳出区间了？其实这种情况下，l 的值会一步步右移，最后的循环结束的结果会是 [mid,mid)。所以我们还是可以从循环结束的 l 值中读到目标值。

对于这种写法，我们的二分判断会少很多，只需要最后判断一下 l 的值是否是目标值，即可知道是否查找成功。

以下是参考代码（从以前的 32 行缩短为 24 行）：

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

int v[1000010];
int n, m, a;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", v+i);
    while (m--) {
        scanf("%d", &a);
        int l, r, mid;
        l = 1; r = n+1;
        while (l < r) {
            mid = l + (r-l)/2;
            if (a > v[mid]) l = mid + 1;
            else r = mid;
        }
        if (l < n+1 && v[l] == a) cout << l << " ";
        else cout << -1 << " ";
    }
    cout << endl;
    return 0;
}

如果记不清楚，就分开写：

  • 如果猜对了但要找最小值，就更新 r
  • 如果 mid 大了，则答案在 mid 左侧，就更新 r
  • 如果 mid 小了，则答案在 mid 右侧，就更新 l

另外，以上这种代码其实是不停在[l,mid) 和 [mid+1, r)之间做选择，所以：

  • l 只会更新成 mid+1
  • r 只会更新成 mid

最后答案如果有，则在 l 位置，当然 l 位置也可能不是答案：

  • 如果目标极小，没找到，则 l 位置为查找的范围最左侧下标
  • 如果目标极大，没找到，则 l 位置为最初的 r 的位置（那个位置是最后一个元素的下一个位置，直接读取会数组越界）

lower_bound

其实上面那个写法就是 C++ STL 里面的 lower_bound 函数，所以我们可以直接用 lower_bound 函数来实现 P2249 题。

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 v[1000010];
int n, m, a;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", v+i);
    while (m--) {
        scanf("%d", &a);
        int l = lower_bound(v+1, v+n+1, a) - v;
        if (l < n+1 && v[l] == a) cout << l << " ";
        else cout << -1 << " ";
    }
    cout << endl;
    return 0;
}

函数 lower_bound 在 [first,last) 中的前闭后开区间进行二分查找，返回大于或等于目标值的第一个元素位置。如果所有元素都小于目标值，则返回 last 的位置。

这种函数行为初看很奇怪，因为它：

  • 当找到目标值时，它返回达找到的值的第一个位置
  • 当没有目标值时，它返回第一个大于目标值的位置
  • 当所有元素都小于目标值时，它返回 last 的位置

这实际上就是它的内部实现所致（可以理解为这种写法的side effect），它内部实现就是我们刚刚提到的写法，所以才会这么返回目标值。

如果我们想把查找结果转换成数组下标，只需要让它减去数组首地址即可，像这样：

1
 
int idx = lower_bound(v, v+n, a) - v;

upper_bound

除了 lower_bound 函数之外，C++还提供了 upper_bound 函数。lower_bound 在 [first, last) 中的前闭后开区间进行二分查找，返回第一个比目标值大的位置。如果没找到，则返回 last 的位置。

upper_bound 的内部实现逻辑是：

  • 如果猜对了但要找最大值，就更新 l
  • 如果 mid 大了，则答案在 mid 左侧，就更新 r
  • 如果 mid 小了，则答案在 mid 右侧，就更新 l

为了方便对比，我把 lower_bound 的逻辑再写一下：

  • 如果猜对了但要找最小值，就更新 r
  • 如果 mid 大了，则答案在 mid 左侧，就更新 r
  • 如果 mid 小了，则答案在 mid 右侧，就更新 l

你看出来了吗？只是第一个更新的逻辑不一样。所以，其实两者的代码很像，我自己分别写了二者的一个实现，大家可以对比看一下，实际上二者实现部分只差了一个字符：

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
 
// 如果目标值等于或者小于 mid，则 r = m
// 如果目标值大于 mid，则 l = m+1
int lower_bound(int a) {
    int l, r;
    l = 0; r = n;
    while (l < r) {
        int m = l + (r-l)/2;
        if (a > v[m]) l = m+1;
        else r = m;
    }
    return l;
}

// 如果 mid 值小于等于目标，就 l=m+1
// 如果 mid 值大于目标，就 r=m
int upper_bound(int a) {
    int l, r;
    l = 0; r = n;
    while (l < r) {
        int m = l + (r-l)/2;
        if (a >= v[m]) l = m+1;
        else r = m;
    }
    return l;
}

我们 upper_bound 考虑几种情况：

  • 如果目标值极小，那么一直就更新 r，结果返回的就是首地址，为正确值。
  • 如果目标值极大，那么一直就更新 l，结果返回的就是 last。

所以 upper_bound 如果没找到，会返回 last。

我们再看 lower_bound

  • 如果目标值极小，那么一直就更新 r，结果返回的就是首地址，为第一个大于目标值的地址。
  • 如果目标值极大，那么一直就更新 l，结果返回的就是 last。

所以，其实这两个函数在没找到目标值的情况下，都有可能返回首地址或末地址的。只是对于 upper_bound 函数来说，首地址是有意义的。

而 lower_bound 函数返回的首地址怎么说呢？有点像 side effect。很少有需求是求这个地址，所以很多时候要特殊处理一下，就像我们刚刚例题里面又判断了一下一样(如下所示)

1
 
if (l < n+1 && v[l] == a) cout << l << " ";

二分答案

二分不但能用于查找数值，还可以用来暴力尝试答案。因为即便是 0-20 亿这么大的范围的猜数字游戏，也只需要 30 多次就可以猜到，所以如果某个问题可以像猜大小一样，每次获得答案是大了还是小了，就可以用二分的办法来“二分答案”。

对于二分答案一类的题目，最常见的题目描述特征是求某某值的最大值最小，或者最小值最大。这个特征可以作为我们选择二分解题的小提示。我们在练习题目 P2678 跳石头 和 P1182 数列分段 Section II 中就可以看到这种提示。

教学和练习题目

题目 说明
P2249 查找 可用 lower_bound 函数
P1102 A-B 数对 也可使用 STL map
P1873 砍树 二分答案
P3853 路标设置 天津省选，二分答案
P1678 烦恼的高考志愿 二分查找，可用 upper_bound 函数
P2440 木材加工 二分答案
P2678 跳石头 二分答案，NOIP2015 提高组
P1182 数列分段 Section II

P3853 路标设置

二分答案+判定。

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 L, N, K;
int v[100010];

bool check(int mid) {
    int ans = 0;
    for(int i=1; i<N; i++){
        if(v[i]-v[i-1] > mid){
            ans += (v[i]-v[i-1]-1)/mid;
        }
    }
    if(ans<=K){
        return true;
    }
    return false;
}

int main() {
    scanf("%d%d%d", &L, &N, &K);
    for (int i = 0; i < N; ++i) {
        scanf("%d", v+i);
    }
    int left, right, mid, ans = INT_MAX;
    left = 1;
    right = L;
    while (left <= right) {
        mid = (left + right) / 2;
        if (check(mid)) {
            right = mid - 1;
            ans = min(ans, mid);
        } else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

P1678 烦恼的高考志愿

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
 
/**
 * 二分查找。
 * 用 upper_bound 找到第一个大的位置 idx，然后取 idx 和 idx - 1, 分别试一下。
 * idx 可能是 0 或者末尾（idx == m），要特殊处理一下。
 */
#include <bits/stdc++.h>
using namespace std;

int m, n, vm[100010], a;
long long ans = 0;

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i) 
        scanf("%d", vm+i);
    sort(vm, vm+m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a);
        int diff = INT_MAX;
        int idx = upper_bound(vm, vm+m, a)-vm;
        if (idx != m) diff = min(diff, abs(vm[idx]-a));
        if (idx - 1 >=0 ) diff = min(diff, abs(vm[idx-1]-a));
        ans += diff;
    }
    cout << ans << endl;
    return 0;
}

P2440 木材加工

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

int n, k;
int v[100010];
bool check(int mid) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += v[i]/mid;
        if (cnt >= k) return true;
    }
    return false;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    int left = 1;
    int right = (int)1e8;
    int ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            left = mid + 1;
            ans = max(ans, mid);
        } else {
            right = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

P2678 跳石头

二分答案：用 mid 去试跳，如果间距小于 mid，则去掉那个石头，如果去掉个数超过 k 个，则失败。

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

int ed, n, k;
int v[50010];
// 用 mid 去试跳，如果间距小于 mid，则去掉那个石头，如果去掉个数超过 k 个，则失败。
bool check(int mid) {
    int cnt = 0;
    int diff = 0;
    for (int i = 1; i <= n+1; ++i) {
        int dis = v[i] - v[i-1] + diff;
        if (dis < mid) {
            cnt++;
            diff = dis;
            if (cnt > k) return false;
        } else {
            diff = 0;
        }
    }
    return true;
}
int main() {
    scanf("%d%d%d", &ed, &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", v+i);
    }
    v[0] = 0; // 起点
    v[n+1] = ed; // 终点
    int left = 1;
    int right = ed;
    int ans = 0;
    while (left <= right) {
        int mid = left + (right-left)/2;
        if (check(mid)) {
            ans = max(ans, mid);
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

P1182 数列分段 Section II

二分答案。对目标答案每 mid 分一段，如果分出来的段数 <= m 即为真。

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;

int n, m, v[100010];
bool check(int mid) {
    int tot = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += v[i];
        if (v[i] > mid) return false;
        if (cnt > mid) {
            tot++;
            cnt = 0; 
            i--;
        }
    }
    if (cnt != 0) tot++;
    if (tot <= m) return true;
    else return false;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    int left = 1;
    int right = (int)(1e9 + 1);
    int ans = INT_MAX;
    while (left <= right) {
        int mid = (left+right)/2;
        if (check(mid)) {
            ans = min(ans, mid);
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

教学思考

因为lower_bound 和 upper_bound的写法相比传统写法还是有点复杂，在教学中还是适合用最初的那个易懂的版本。易懂的版本虽然执行起来多几次判断，但是在比赛中这一点多的时间并不影响整体的时间复杂度，所以不会因此扣分。同时，简单易于理解的代码，在学习和解题时，也更加不容易犯错。

待学生理解基础二分的写法后，再把系统的实现拿出来，作为增强的补充练习题目。这么补充练习并不是要学生一定掌握，而是借由实现系统的函数，学会在比赛中调用 C++ 的 lower_bound 和 upper_bound 库函数，这样可以加速解题的速度。

二分答案的思路很好理解，但是实际写起来还是很容易晕，所以需要多加练习。另外利用题目特征来获得提示，帮助自己快速解题。

小结

  • lower_bound 和 upper_bound 都是极简二分查找的 C++ 内部实现。
  • 因为它们都有 side effect，所以在查找目标不存在时，均可能返回首地址和末地址（取决于目标是极小还是极大）。
    • 因为以上的 side effect，所以我们给 lower_bound 赋予了额外的功能：返回第一个大于或等于目标值的位置；如果不存在返回 last。
    • upper_bound 在目标值极小的时候，返回首地址（正好符合要求）；在目标值极大的时候，返回 last。
  • 因为 lower_bound 有可能返回的不是目标值，所以最后要判断一下。

CSPJ 教学思考：动态规划

✇唐巧的博客
唐巧

引言

动态规划是 CSPJ 拉分的关键知识点。

之所以这样，是因为动态规划不像 DFS、BFS、二分那样有固定的模版格式。学生要在动态规划问题上融汇贯通，需要花费大量的练习，也需要足够的聪明。

笔者自己在高中阶段，也是在动态规划问题上困扰许久。我自己的学习经验是：动态规划还是需要多练，练够 100 道题目，才能够熟悉动态规划的各种变型。之后在比赛中看到新的题目，才会有点似曾相识的感觉，进一步思考出状态转移方程。

所以，我打算写 100 道动态规划方程的题解，希望有志攻破此难关的学生和家长一起加油！

动态规划解题的核心问题

虽然动态规划没有模版可以套，但是动态规划有三个核心问题：

  • 状态的定义
  • 状态转移方程
  • 初始状态的设置

一般思考动态规划就是思考以上三个问题，这三个问题解决了，动态规划的程序也可以写出来了。

教学题目

推荐的教学题目如下：

题目名 说明
P2842 纸币问题 1 基础 DP，记忆化搜索
P1216 数字三角形 基础 DP，记忆化搜索 【经典 DP】
P2840 纸币问题 2 基础 DP
P2834 纸币问题 3 基础 DP，有多处可优化的点
P1048 采药 NOIP2005 普及组第三题。01 背包问题。【经典 DP】
P1616 疯狂的采药 完全背包问题。【经典 DP】
P2196 挖地雷 NOIP1996 提高组第三题。涉及输出路径技巧。
P1434 滑雪 上海市省队选拔 2002
P1115 最大子段和 最大子段和。【经典 DP】

适合的作业：

题目名 说明
P4017 最大食物链计数 记忆化搜索
P2871 Charm Bracelet S USACO 07 DEC，01 背包
P1802 5 倍经验日 01 背包
P1002 过河卒 NOIP2002 普及组，记忆化搜索
P1049 装箱问题 NOIP2001 普及组，01 背包
P1064 金明的预算方案 01 背包变型，NOIP2006 提高组第二题
P1077 摆花 NOIP2012 普及组
P1164 小A点菜 与摆花一题类似
P2392 考前临时抱佛脚 01 背包变型

更多的题单：

例题代码

P2842 纸币问题 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
 
/**
 * DFS，超时
 */
#include <bits/stdc++.h>
using namespace std;

int n, w;
int v[1100];

int dfs(int pt) {
    if (pt == 0) return 0;
    int ret = 1e9;
    for (int i = 0; i < n; ++i) {
        if (pt>=v[i]) {
            ret = min(ret, dfs(pt-v[i]) + 1);
        }
    }
    return ret;
}

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    int ans = dfs(w);
    printf("%d\n", ans);
    return 0;
}

有了上面的代码，通过分析，发现大部分的超时是因为有重复的计算过程。以下是一个以 10,5,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
 
/**
 * DFS，记忆化搜索
 */
#include <bits/stdc++.h>
using namespace std;

int n, w;
int v[1100];
int r[10010]; // 改动 1

int dfs(int pt) {
    if (pt == 0) return 0;
    if (r[pt] != 0) return r[pt]; // 改动 2

    int ret = 1e9;
    for (int i = 0; i < n; ++i) {
        if (pt>=v[i]) {
            ret = min(ret, dfs(pt-v[i]) + 1);
        }
    }
    return (r[pt]=ret); // 改动 3
}

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    int ans = dfs(w);
    printf("%d\n", ans);
    return 0;
}

有了以上两段代码的尝试，我们能够发现：

  • dfs(pt) 只与 dfs( 0 ~ pt-1) 有关,与 dfs(pt+1~w)无关。
  • 如果我们知道了 dfs(0~pt)，就可以推出 dfs(pt+1)

那么，我们就可以思考，如果我们用 dp[i] 来表示钱币总额为 i 的结果数。那么，dp[i] 的计算过程（即：状态转移方程）为：dp[i] = min( dp[i-v[j]] )+1，其中j=0~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
 
/**
 * dp[i] = min( dp[i-v[j]] )  + 1 
 */
#include <bits/stdc++.h>
using namespace std;

int n, w;
int v[1100], dp[11000];

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <=w ; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i-v[j]>=0) {
                dp[i] = min(dp[i], dp[i-v[j]]+1);
            }
        }
    }
    printf("%d\n", dp[w]);
    return 0;
}

P1216 数字三角形

P1216 数字三角形同样可以用记忆化搜索引入。先写记忆化搜索的代码有助于我们理解动态规划的状态转移方程。

搜索的代码为：

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
 
/**
 * DFS，记忆化
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int v[1010][1010];
int r[1010][1010];

int dfs(int x, int y) {
    if (r[x][y] != -1) return r[x][y];
    if (x == n-1) return 
        r[x][y] = v[x][y];
    else return 
        r[x][y] = v[x][y]+max(dfs(x+1,y), dfs(x+1,y+1));
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            scanf("%d", &v[i][j]);
        }
    }
    memset(r, -1, sizeof(r));
    printf("%d\n", dfs(0, 0));
    return 0;
}

由搜索代码可知，每一个位置的最价结果由它下面两个结点的最价结果构成。于是，我们可以构造出状态转移方程：dp[i][j] = v[i][j] + max(dp[i+1][j], dp[i+1][j+1])

另外，我们可以引导学生：上层的依赖于下层的数据，那应该怎么推导呢？让学生想到用倒着 for 循环的方式来从下往上推导。

最后，我们再引导学生构建一下初始值。由此，我们建立起动态规划解题的三个核心问题：

  • 状态的定义
  • 状态转移方程
  • 初始状态的设置
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
 
/**
 * 动态规划：
 * dp[i][j] = v[i][j] + max(dp[i+1][j], dp[i+1][j+1])
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int v[1010][1010];
int dp[1010][1010];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            scanf("%d", &v[i][j]);
        }
    }
    // 初始状态
    for (int j = 0; j < n; ++j) {
        dp[n-1][j] = v[n-1][j];
    }
    // dp
    for (int i = n-2; i>=0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[i][j] = v[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
        }
    }
    printf("%d\n", dp[0][0]);
    return 0;
}

P2840 纸币问题 2

状态转移方程为：dp[i] = sum(dp[i- v[j]]), j = 0~N，结果需要每次模 1000000007。

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

int n, w;
int v[1010], dp[10010];

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    dp[0] = 1;
    for (int i = 1; i <= w ; ++i) {
        dp[i] = 0;
        for (int j = 0; j < n; ++j) {
            if (i >= v[j]) {
                dp[i] = (dp[i] + dp[i-v[j]])%1000000007;
            }
        }
    }
    printf("%d\n", dp[w]);
    return 0;
}

P2834 纸币问题 3

此题不能像之前的题目那样，用金钱数为阶段。因为此题是计算的组合数，所以 1,5 和 5,1 是一种答案。如果以金钱数为阶段，就无法方便将这种重复计算的排除掉。

那么，以什么为阶段，可以保证每个阶段可以基于过去的阶段推导出来？可以用不同的钱币种类为阶段！

接下来就是思考这种情况下的状态转移方程。可以得出，状态转移方程如下：

  • dp[i][j] 表示用前 i 种钱币组成金额 j 的组合数
  • dp[i][j] = dp[i-1][j-v[i]] + dp[i-1][j - v[i]*2] + …. dp[i-1][j-v[i]*n]; (j >= v[i]*n)
  • 初始状态：dp[1][0] = 1; dp[1][v[1]] = 1; dp[1][v[1]*2] = 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
 
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
int n, w;
int v[1010], dp[1010][10010];

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    memset(dp, 0, sizeof(dp));
    // dp[0][0] = 1; dp[0][v[0]] = 1;dp[0][v[0]*2] = 1;….
    int cnt = 0;
    while (cnt <= w) {
        dp[0][cnt] = 1;
        cnt += v[0];
    }
    for (int i=1; i<n; ++i) {
        for (int j=0; j<=w; ++j) {
            cnt = 0;
            while (j - cnt >= 0) {
                dp[i][j] = (dp[i][j]+dp[i-1][j-cnt]) % MOD;
                cnt += v[i];
            }
        }
    }
    printf("%d\n", dp[n-1][w]);
    return 0;
}

此题还有另外一种状态转移方程，把阶段分为没有用过 a，和至少用过一张 a。

这样的话，状态转移方程优化为：dp[i][j] = dp[i-1][j] + dp[i][j-v[i]]

这样，代码的复杂度进一步降低，代码如下：

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

const int MOD = 1000000007;
int n, w;
int v[1010], dp[1010][10010];

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    memset(dp, 0, sizeof(dp));
    int cnt = 0;
    while (cnt <= w) {
        dp[0][cnt] = 1;
        cnt += v[0];
    }
    for (int i=1; i<n; ++i) {
        for (int j=0; j<=w; ++j) {
            if (j-v[i]>=0) {
                dp[i][j] = (dp[i-1][j]+dp[i][j-v[i]])% MOD;
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    printf("%d\n", dp[n-1][w]);
    return 0;
}

此题还可以进一步简化，因为 dp[i] 那一层算完之后 dp[i-1] 层就没有用了。有没有可能我们将 dp[i]层和 dp[i-1]都合并在一起呢？

答案是可以的。我们可以将关键代码进一步简化如下，把 dp 改成一个一维数组。状态转移方程变为了:dp[j] = dp[j] + dp[j-v[i]]

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

const int MOD = 1000000007;
int n, w;
int v[1010], dp[10010];

int main() {
    scanf("%d%d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    memset(dp, 0, sizeof(dp));
    int cnt = 0;
    while (cnt <= w) {
        dp[cnt] = 1;
        cnt += v[0];
    }
    for (int i=1; i<n; ++i) {
        for (int j=0; j<=w; ++j) {
            if (j-v[i]>=0) {
                dp[j] = (dp[j]+dp[j-v[i]]) % MOD;
            } else {
                dp[j] = dp[j]; //此行可以删除，但为了教学示意保留
            }
        }
    }
    printf("%d\n", dp[w]);
    return 0;
}

P1048 采药

P1048 采药这题是经典的 01 背包问题。为了方便教学，我们还是从最简单的动态规划思路开始推导。

我们把每个草药是一个阶段，这样：

  • dp[i][j] 表示前 i 个草药，花费 j 时间可以得到的最大价值
  • 状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]])

这样写出来的参考程序如下：

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
 
/**
dp[i][j] 表示前 i 个草药，花费 j 时间可以得到的最大价值
dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] 
 */
#include <bits/stdc++.h>
using namespace std;

int T, M;
int t[110], v[110];
int dp[110][1010];

int main() {
    scanf("%d%d", &T, &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", t+i, v+i);
    }
    // 下标从 1 开始，这样不用考虑 i-1 越界了
    for (int i = 1; i <= M; ++i) {
        for (int j = 1; j <= T; ++j) {
            dp[i][j] = dp[i-1][j];
            if (j - t[i] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - t[i]]+v[i]);
            }
        }
    }
    printf("%d\n", dp[M][T]);
    return 0;
}

与上一题一样，通过分析，我们发现 dp[i][j] 中的 i 一层可以优化掉，变成只有 dp[j]。

这样，状态转移方程被优化成：dp[j]=max(dp[j],dp[j-t[i]]+v[i])。

但是，因为每一个草药只能用一次，如果我们正着循环 j 的话，会出现多次使用第 i 个草药的情况。所以，我们倒着进行递推，就可以避免这种情况。

最终实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
/**
dp[j] 花费 j 时间可以得到的最大价值
dp[j] = max(dp[j], dp[j-t[i]])
 */
#include <bits/stdc++.h>
using namespace std;

int T, M;
int t[110], v[110];
int dp[1010];

int main() {
    scanf("%d%d", &T, &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", t+i, v+i);
    }
    for (int i = 1; i <= M; ++i) {
        for (int j = T; j >= t[i]; --j) {
            dp[j] = max(dp[j], dp[j - t[i]]+v[i]);
        }
    }
    printf("%d\n", dp[T]);
    return 0;
}

P2196 挖地雷

P2196 挖地雷 是 NOIP1996 提高组第三题。这道题的解法有点类似于P1216 数字三角形。

但是，这道题更难的是：它需要我们输出路径。

我们先说状态转移方程：

  • dp[i] 表示第 i 个地窖能够挖到的最多地雷数。
  • w[i] 表示第 i 个地窖的地雷数。
  • 转移方程：dp[i] = max(dp[i+1~N]中能够与 dp[i] 连通的地窖) + w[i] 与 dp[i] = w[i]中的较大者。

我们再说说如何输出路径。因为计算之后 dp 数组中保存了每个结点能够挖的最大地雷数。所以，我们从答案 dp[ans]开始，找哪一个地窖与当前相连，同时值又等于 dp[ans] - w[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
 
#include <bits/stdc++.h>
using namespace std;

int n;
int w[30];
int v[30][30];
int dp[30];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", w+i);
    }
    for (int i = 1; i <=n ; ++i) {
        for (int j = i+1; j<=n; ++j) {
            scanf("%d", &v[i][j]);
        }
    }
    int ans = 0;
    for (int i = n; i>=1; --i) {
        dp[i] = w[i];
        for (int j = i+1; j<=n; ++j) {
            if (v[i][j]) {
                dp[i] = max(dp[i], dp[j]+w[i]);
            }
        }
        if (dp[ans] < dp[i]) ans = i;
    }
    int cnt = dp[ans];
    int idx = ans;
    while (cnt) {
        printf("%d ", idx);
        cnt -= w[idx];
        for (int i = idx + 1; i<=n; ++i) {
            if (v[idx][i] && cnt == dp[i]) {
                idx = i;
                break;
            }
        }
    }
    printf("\n%d\n", dp[ans]);
    return 0;
}

P1434 滑雪

这道题的麻烦点是如何定义状态转移的阶段，因为没有明显的阶段。

可以考虑的办法是：将点按高度排序，这样从高度低的点开始，往高的点做状态转移。

所以：

  • 定义：dp[i][j] 表示从 (i,j) 这个位置开始滑的最长坡。
  • 转移方程：
    • dp[x][y] = max(dp[x'][y'])+1
    • dp[x'][y'] 为上下左右相邻并且高度更低的点
  • 初始化：无
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
 
#include <bits/stdc++.h>
using namespace std;

int r, c;
int tu[110][110];
int dp[110][110];
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};
bool debug = false;

struct Node {
    int x, y, h;
    Node(int _x, int _y, int _h) {
        x = _x; y = _y; h = _h;
    }
};
bool operator<(Node a, Node b) {
    return a.h < b.h;
}
vector<Node> v;

int main() {
    scanf("%d%d", &r, &c);
    v.reserve(r*c);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            scanf("%d", &tu[i][j]);
            v.push_back(Node(i, j, tu[i][j]));
        }
    }
    sort(v.begin(), v.end());
    memset(dp, 0, sizeof(dp));
    int ans = 0;
    for (int i = 0; i < r*c; ++i) {
        Node node = v[i];
        int x = node.x;
        int y = node.y;
        for (int j = 0; j < 4; ++j) {
        int tox = x + movex[j];
        int toy = y + movey[j];
        if (tox >=0 && tox <r && toy >=0 && toy<c &&
        node.h > tu[tox][toy]) {
        dp[x][y] = max(dp[x][y], dp[tox][toy]);
        }
        }
        dp[x][y] += 1;
        ans = max(ans, dp[x][y]);
        if (debug) {
        printf("dp[%d][%d]=%d\n", x, y, dp[x][y]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

此题更容易想到的写法还是记忆化搜索：对每一个点作为开始点进行一次 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
41
42
43
 
/**
 * DFS, 记忆化
 */
#include <bits/stdc++.h>
using namespace std;

int r, c;
int tu[110][110];
int rem[110][110];

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

int dfs(int x, int y) {
    if (rem[x][y] != 0) return rem[x][y];
    int mm = 0;
    for (int i = 0; i < 4; ++i) {
        int tox = x + movex[i];
        int toy = y + movey[i];
        if (tox >=0 && tox <r && toy >=0 && toy<c &&
        tu[x][y] > tu[tox][toy]) {
            mm = max(mm, dfs(tox, toy));
        }
    }
    return (rem[x][y] = mm + 1);
}

int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            scanf("%d", &tu[i][j]);
        }
    }
    int ans = 0;
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            ans = max(ans, dfs(i, j));
        }
    }
    printf("%d\n", ans);
    return 0;
}

P1115 最大子段和

P1115 最大子段和 是最经典的一类动态规划问题。思路如下：

  • dp[i] 表示包含 i 这个数，并且以 i 结尾的最大子段和。
  • 状态转移方程：
    • 如果 dp[i-1] 为负数，那么 dp[i] = v[i]
    • 如果 dp[i-1] 为正数，那么 dp[i] = dp[i-1]+v[i]

因为 dp[i] 在转移方程上只与 dp[i-1]相关，所以它最终结构上被可以被化简成类似贪心的策略，即：

  • 用一个变量记录当前的累加值，如果当前累加值为负数，则重新计算。
  • 在累加过程中随时判断，记录最大的累加值为最终答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <bits/stdc++.h>
using namespace std;

int n;
int v[200100];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    int cnt = 0;
    int ans = -1e9;
    for (int i = 0; i < n; ++i) {
        cnt += v[i];
        ans = max(ans, cnt);
        if (cnt < 0) cnt = 0;
    }
    printf("%d\n", ans);
    return 0;
}

作业代码

P4017 最大食物链计数

P4017 最大食物链计数最佳的做法是做记忆化的搜索。

记录下出度为 0 的结点，从这些结点开始去寻找，把各种可能的路径加总。同时在 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
41
42
43
44
45
 
/**
 * 记忆化搜索
 */
#include <bits/stdc++.h>
using namespace std;

#define MOD 80112002

int n, m;
vector<vector<int> > v;
int r[5010], out[5010];

int dfs(int a) {
    if (r[a] != -1) return r[a];
    // 如果是头部，算一种情况
    if (v[a].size() == 0) return (r[a]=1);
    // 如果不是头部，则求和
    int cnt = 0;
    for (int i = 0; i < v[a].size(); ++i) {
        cnt = (cnt + dfs(v[a][i])) % MOD;
    }
    return r[a] = cnt;
}

int main() {
    memset(r, -1, sizeof(r));
    scanf("%d%d", &n, &m);
    v.resize(n+1);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b); // a 被 b 吃
        out[b]++; // b 的出度+1
    }
    int ans = 0;
    for (int i = 1; i <=n ; ++i) {
        // 如果 i 出度为 0，就表示只能被吃，为底部
        if (out[i] == 0) { 
            ans += dfs(i);
            ans %= MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}

P2871 Charm Bracelet S

P2871 Charm Bracelet S 是最最标准的 01 背包问题。可以作为基础练习。

参考代码：

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

int n, m;
int w[3500], v[3500], dp[14000];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", w+i, v+i);
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i) {
        for (int j = m; j>=w[i]; --j) {
            dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

P1802 5 倍经验日

经典的 01 背包问题：

  • dp[i] 表示 i 容量可以获得的最大的经验值增量。
  • w[i] 表示第 i 个药的数量。
  • t[i] 表示第 i 个药贡献的经验值增量。

状态转移方程：dp[j] = max(dp[j], dp[j-w[i]]+t[i])。

需要注意答案最大超过了 int，需要用 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
 
#include <bits/stdc++.h>
using namespace std;

int dp[1010], w[1010], t[1010];
int base = 0, n, x;

int main() {
    scanf("%d%d", &n, &x);
    for (int i = 0; i < n; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        base += a;
        t[i] = b-a;
        w[i] = c;
    }
    for (int i=0; i<n; ++i) {
        for (int j=x; j>=0; --j) {
            if (j-w[i]>=0) {
                dp[j] = max(dp[j], dp[j-w[i]]+t[i]);
            }
        }
    }
    //最大结果为 5*1e9，需要用 long long
    printf("%lld\n", 5LL*(dp[x] + base));
    return 0;
}

P1002 过河卒

P1002 过河卒此题是标准的记忆化搜索。有两个陷阱：

  • 马所在的位置也不能走。
  • 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
 
/**
 * 记忆化搜索。
 */
#include <bits/stdc++.h>
using namespace std;

int bx, by, hx, hy;
long long r[22][22];

bool block(int x, int y) {
    int v = abs(x-hx)*abs(y-hy);
    return (v == 2 || x==hx && y == hy);
}

long long dfs(int x, int y) {
    if (x>bx || y>by) return 0;
    if (x == bx && y == by) return 1;
    if (r[x][y]!=-1) return r[x][y];
    if (block(x,y)) return r[x][y] = 0;
    long long ans = dfs(x+1,y) + dfs(x,y+1);
    return r[x][y] = ans;
}

int main() {
    memset(r, -1, sizeof(r));
    cin >> bx >> by >> hx >> hy;
    printf("%lld\n",dfs(0, 0));
    return 0;
}

P1064 金明的预算方案

P1064 金明的预算方案 是一道 01 背包的变型题。题目增加了附件的概念，初看起来没法下手，但是题目增加了一个限制条件：附件最多只有 2 个。

所以，我们可以将 01 背包的“选或不选”两种情况扩充成以下 5 种情况：

  • 不选
  • 选主件，不选附件
  • 选主件 + 附件 1
  • 选主件 + 附件 2
  • 选主件 + 附件 1 + 附件 2

然后就可以用 01 背包来实现该动态规划了。我们把每种物品的费用当作背包的体积，把每种物品的价格*权重当作价值。

转移方程是：dp[i]=max(dp[i], 5 种物品选择情况)，每种选择情况下，dp[i]=max(dp[i], dp[i-该选择下的花费]+该选择下的收益) 。

另外，需要注意，输入数据的编号可能不按顺序提供，有以下这种情况：

1
2
3
4
 
100 3
1000 5 3
10 5 3
50 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
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
 
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int m;
    int w;
    int t;
};

int n, m;
vector<Node> va;
vector<vector<Node> > vb;
int dp[40000];

void updateDP(int i, int m, int w) {
    if (i-m >= 0) {
        dp[i] = max(dp[i], dp[i-m] + w);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    va.resize(m);
    vb.resize(m);
    for (int i = 0; i < m; ++i) {
        Node node;
        scanf("%d%d%d", &node.m, &node.w, &node.t);
        node.w = node.w*node.m; 
        va[i] = node;
        if (node.t != 0) {
            vb[node.t - 1].push_back(node);
        }
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < m; ++i) {
        // 只处理主件，附件与主体一并处理
        if (va[i].t == 0) {
            for (int j = n; j > 0; j--) {
                // 选主件，不选附件
                updateDP(j, va[i].m,va[i].w);
                // 选主件+附件 1
                if (vb[i].size() > 0) {
                    int money = va[i].m + vb[i][0].m;
                    int weight = va[i].w + vb[i][0].w;
                    updateDP(j, money, weight);
                }
                // 选主件+附件 2
                if (vb[i].size() == 2) {
                    int money = va[i].m + vb[i][1].m;
                    int weight = va[i].w + vb[i][1].w;
                    updateDP(j , money, weight);
                }
                // 选主件+附件 1+附件 2
                if (vb[i].size() == 2) {
                    int money = va[i].m + vb[i][0].m + vb[i][1].m;
                    int weight = va[i].w + vb[i][0].w + vb[i][1].w;
                    updateDP(j, money, weight);
                }
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

P1077 摆花

P1077 摆花 一题是 NOIP2012 普及组的第三题。

  • dp[i][j] 表示前 i 种花，摆在前 j 个位置上的种数。

状态转移方程：

1
2
3
4
 
dp[i][j] = dp[i-1][j] 不放第 i 种花
         + dp[i-1][j-1] 放 1 个第 i 种花
         + dp[i-1][j-2] 放 2 个第 i 种花
         ...

这道题的难点：没有想到 dp[0][0]=1。因为后面推导的时候，
dp[i-1][j-k] 中 j==k 的时候，也是一种可能的情况，要统计进来。

参考代码：

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

int n, m;
int a[110];
int dp[110][110];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a+i);
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int k = 0; k <= a[i]; ++k) {
                if (j - k >= 0) {
                    dp[i][j] += dp[i-1][j-k];
                    dp[i][j] %= 1000007;
                }
            }
        }
    }
    printf("%d\n", dp[n][m]);
    return 0;
}

P1164 小A点菜

P1164 小A点菜一题阶段比较明显。每一道菜点不点是一个明显阶段。所以：

  • dp[i][j]表示前 i 道菜，用 j 的价格，能够点的方案数

对于每道菜，有点或不点两种方案，所以：

  • 转移方程：dp[i][j] = dp[i-1][j]+dp[i-1][j-a[i]]

由于 i 阶段只与 i-1 阶段相关，所以可以把阶段压缩掉，只留一维。最后压缩后的方案是：

  • dp[j] 表示用 j 的价格可以点到的点的种数
  • 初始条件 dp[0] = 1，因为这样才可以把后面的结果递推出来
  • dp[j] = dp[j] + dp[j-a[i]]

因为和 01 背包类似的原因，压缩后需要倒着用 for 循环，否则每道菜就用了不止一次了。

参考代码：

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

int n, m;
int a[110];
int dp[10010];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a+i);
    }
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j>=a[i]; --j) {
            dp[j] += dp[j-a[i]];
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

P2392 考前临时抱佛脚

P2392 考前临时抱佛脚 此题可以用动态规划，也可以用搜索，因为每科只有最多 20 个题目，所以搜索空间最大是 2^20 等于约 100 万。

以下是搜索的代码：

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

int s[4], v[25];
int ans, tot, ret;

void dfsAns(int pt, int n, int cnt) {
    if (pt == n) {
        int tmp = max(cnt, tot-cnt);
        ret = min(ret, tmp);
        return;
    }
    dfsAns(pt+1, n, cnt);
    dfsAns(pt+1, n, cnt+v[pt]);
}

int main() {
    scanf("%d%d%d%d", s, s+1, s+2, s+3);
    for (int i = 0; i < 4; ++i) {
        memset(v, 0, sizeof(v));
        tot = 0;
        for (int j = 0; j < s[i]; ++j) {
            scanf("%d", v+j);
            tot += v[j];
        }
        ret = tot;
        dfsAns(0, s[i], 0);
        ans += ret;
    }
    printf("%d\n", ans);
    return 0;
}

用动态规划解题时，此题可以把每次复习看作一次 01 背包的选择。每道题的价值和成本相同。背包的目标是尽可能接近 sum/2，因为sum 最大值为 20*60 = 1200，所以背包大小最大是 600。

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

int s[4];
int v[25];
int ans = 0;
int dp[610];

int dpAns(int n) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += v[i];
    }
    int m = cnt / 2;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i) {
        for (int j = m; j>=v[i]; --j) {
            dp[j] = max(dp[j], dp[j-v[i]] + v[i]);
        }
    }
    int ret = max(dp[m], cnt - dp[m]);
    return ret;
}

int main() {
    scanf("%d%d%d%d", s, s+1, s+2, s+3);
    for (int i = 0; i < 4; ++i) {
        memset(v, 0, sizeof(v));
        for (int j = 0; j < s[i]; ++j) {
            scanf("%d", v+j);
        }
        ans += dpAns(s[i]);
    }
    printf("%d\n", ans);
    return 0;
}

CSPJ 教学思考：贪心算法

✇唐巧的博客
唐巧

1、概述

贪心算法讲起来容易，就是问题求解的每一步，都用一个局部最佳的策略，如果能够证明局部最佳的策略最终能够保证全局最佳，则可以用贪心算法。

在实际 CSPJ 比赛中，我们不用严谨的求解和证明，只需要尝试做一些反例，如果反例中找不到问题，就可以先用贪心求解。毕竟比赛中时间的权重因素比较高。

在教学中，我们先通过简单的题目让学生理解贪心的概念。之后就可以逐步增加难度，让学生意识到，写出贪心可能容易，但是想到贪心这种解法在比赛中并不那么显而易见。

贪心通常伴随着排序，所以对 STL 的 sort 以及 priority_queue 的熟练应用也是快速解决贪心题目的必备基础，在学习相关题目的时候，可以重点加强巩固相关知识点。

2、sort 函数

sort 函数内部使用快速排序实现，时间复杂度为 O(N*log(N))。对于数据规模为 10 万左右的题目，出题人有可能是希望你用这个时间复杂度来解题的，所以可以留意一下是否需要排序。

对于普通类型，STL 自带了 greater<T>和less<T> 两个比较器，以下是相关代码：

1
2
 
int v[100];
sort(v, v+n, greater<int>);

sort 函数通常和自定义的结构体排序搭配使用，以下是相关代码：

1
2
3
4
5
6
7
8
9
10
11
 
struct Person {
    int idx;
    int v;
};
bool operator < (Person a, Person b) {
    return a.v < b.v;
}

Person v[1100];
// 使用时直接用 sort
sort(v, v+n);

sort 函数除了可以像上面这样通过调用 < 符号来比较大小，也可以传入一个比较函数。如下所示：

1
2
3
4
5
6
7
8
9
10
11
 
struct Person {
    int idx;
    int v;
};
bool comp(Person a, Person b) {
    return a.v < b.v;
}

Person v[1100];
// 使用时直接用 sort
sort(v, v+n, comp);

以下是练习结构体排序的题目：

题目名 说明
P5143 攀爬者 按 z 坐标排序，然后求和
P1104 生日 生日的排序

3、教学题目

推荐的教学题目如下：

题目名 说明
P2240 部分背包问题 较简单的一道贪心题
P1223 排队接水 贪心进阶
P1803 凌乱的yyy 贪心进阶
P5019 铺设道路 NOIP 2018 提高组真题
B3872 巧夺大奖 GESP202309 五级
P1012 拼数 NOIP 1998 提高组

4、例题代码

P2240 部分背包问题

P2240 部分背包问题 是较简单的一道贪心题。唯一的陷阱是，学过动态规划的同学可能误以为这个是背包问题。但是在教学中，贪心算法的学习比动态规划更早，所以不会有这个误解。

此题的解题思路是：将金币按单位重量的价值排序，如果能放则放；放不了，则分割放部分。

我们定义了一个结构体，结构体中的 double p用于保存单位重量的价值。在排序的时候，按 p 的大小来由大到小排序。

参考代码如下：

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

struct Gold {
    int w, v;
    double p;
};
bool operator<(Gold a, Gold b) {
    return a.p > b.p;
}

int n, t;
Gold v[110];

int main() {
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &v[i].w, &v[i].v);
        v[i].p = v[i].v*1.0 / v[i].w;
    }
    sort(v, v+n);
    double ans = 0;
    for (int i = 0; i < n; ++i) {
        if (t>=v[i].w) {
            ans += v[i].v;
            t -= v[i].w;
        } else {
            ans += v[i].p * t;
            break;
        }
    }
    printf("%.2f\n", ans);
    return 0;
}

P1223 排队接水

此题的难度是需要推导出贪心的策略。具体推导过程如下：

由以上推导，我们只需要将打水时间按从小到大排序，然后加总时间即可。参考代码如下：

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

struct Person {
    int idx;
    int v;
};
bool operator <(Person a, Person b) {
    return a.v < b.v;
}

int n;
Person v[1100];
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        v[i].idx = i+1;
        cin >> v[i].v;
    }
    sort(v, v+n);
    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
        printf("%d ", v[i].idx);
        cnt += v[i].v * (n-i-1);
    }
    printf("\n%.2f\n", cnt*1.0/n);
    
    return 0;
}

P1803 凌乱的yyy

此题有两种贪心的思路，分别是：

  • 按开始时间排序贪心
  • 按结束时间排序贪心

按开始时间排序贪心

此贪心的方法如下：

  • 左端点排序（小的在前），左端点相同的，按右端点排序(小的在前）

  • 比较当前区间和下一区间，如果下一区间与当前区间没有相交，则由于我们是按左端点排序的，后面的都不会相交，直接选择当前区间；否则这两个区间显然必须抛弃一个，由于我们是按左端点排序的，后面的区间左端点都是大于它们的，因此这两个的左端点已经没有意义了，为了留出更多的空间，留下右端点靠左的那一个即可。

参考代码如下：

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
 
/**
 * 按开始时间排序
 */
#include <bits/stdc++.h>
using namespace std;

struct Line{
    int left, right;
};
bool operator<(Line a, Line b) {
    if (a.left != b.left) return a.left < b.left;
    return a.right < b.right;
}
int n, ans;
Line v[1000010];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &v[i].left, &v[i].right);
    }
    sort(v, v+n);
    ans = 0;
    int border = 0;
    for (int i = 0; i < n; ++i) {
        if (v[i].left >= border) {
            ans++;
            border = v[i].right;
        } else {
            border = min(border, v[i].right);
        }
    }
    printf("%d\n", ans);
    return 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
 
/**
 * 按结束时间排序
 */
#include <bits/stdc++.h>
using namespace std;

struct Line{
    int left, right;
};
bool operator<(Line a, Line b) {
    if (a.right != b.right) return a.right < b.right;
    return a.left < b.left;
}
int n, ans;
Line v[1000010];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &v[i].left, &v[i].right);
    }
    sort(v, v+n);
    ans = 0;
    int border = -1;
    for (int i = 0; i < n; ++i) {
        if (border <= v[i].left) {
            ans++;
            border = v[i].right;
        }
    }
    printf("%d\n", ans);
    return 0;
}

P5019 铺设道路

P5019 铺设道路是 NOIP2018 提高组真题。之所以作为提高组题目，是因为很难想到这种贪心策略，不过一旦想清楚，写起来是很简单的。

贪心策略是：

  • 第一个坑直接填满
  • 从第二坑开始，考虑能不能被左边顺带给填上。
  • 如果第二个坑比第一个坑小，肯定就顺带填上了。不需要任何成本。
  • 如果第二个坑比第一个坑大，那么就只能顺带填一部分，多出来的差额，需要额外的填补。

参考代码：

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

int n;
int v[100010];
long long ans = 0;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", v+i);
    }
    ans = v[0];
    for (int i = 1; i < n; ++i) {
        if (v[i]>v[i-1]) {
            ans += v[i] - v[i-1];
        }
    }
    cout << ans << endl;
    return 0;
}

以上。

B3872 巧夺大奖

对于本题，我们先来看一个样例，如果输入是：

1
2
3
 
2
2 1
20 10

以上样例最佳的贪心策略是：

  • 安排在第 2 个时间段做任务 1，得到 20 的奖励
  • 安排在第 1 个时间段做任务 2，得到 10 的奖励

由此，我们可以得出这道题的贪心策略是：

  • 按奖金的大小从大到小排序，每次取最大的奖金。
  • 对于某一个具体的奖金，其对应的时限如果为 a 的话，我们应该尽可能把它安排在 [1, 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
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

struct Game {
    int time;
    int reward;
};
Game games[510];
int mark[510];

bool operator<(const Game &a, const Game &b) {
    return a.reward > b.reward;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> games[i].time;
    }
    for (int i = 0; i < n; i++) {
        cin >> games[i].reward;
    }
    sort(games, games + n);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = games[i].time; j >= 1; j--) {
            if (!mark[j]) {
                mark[j] = 1;
                ans += games[i].reward;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

P1012 拼数

此题容易想到的贪心策略是：每次用高位尽量大的数字。如果高位相同，则比较次高位。

但是如果两个涉及一个数是另一个数的前缀，则更复杂，让我们看看下面的例子：

  • 那如果是 321 和 32 比较呢？32132 和 32321 哪个大？看起来先用短的更好。
  • 再试一个 329 和 32 比较。32932 和 32329 哪个大？看起来先用长的更好。

所以，本题的正确解法是比较的时候将两个串“连接”起来比大小。以下是关键的比较函数：

1
2
3
 
bool comp(const string& a, const string& b) {
    return a + b > 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
 
/**
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

bool comp(const string& a, const string& b) {
    return a + b > b + a;
}

int main() {
    int n;
    vector<string> a;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), comp);
    for (int i = 0; i < n; i++) {
        cout << a[i];
    }
    cout << endl;
    return 0;
}

读《蹒跚前行 1870～2010 经济史》

✇唐巧的博客
唐巧

本书的作者德龙教授是经济史学家，加州伯克利分校经济学教授，曾担任克林顿政府财政部副助理部长。

这本书以历史发展的时间线，介绍全球经济发展的过程。战争（包括一战和二战）、通胀、通缩、黄金发展期伴随着这 100 多年的历史进程，读完让人感叹发展的不易，就如本书书名：蹒跚前行。

以下是一些笔记。

1、关于通胀

通胀类似于一种税收和财富调节手段。它将财富从拥有现金的人手里转移到了拥有非现金财富的手里。

如果你是借款人，因为借款人是用贬值后的货币还款，而贷款人不得不接受已经贬值的货币。所以通胀对于欠债方是利好的。

政府发行的货币最好是和 GDP 的增长匹配。如果政府因为各种原因印制了更多货币来满足一些特定需求的时候，就会推动通胀。

通胀是一个零和博弈。受益者和损失者的损益完全匹配。

2、失业率对社会的影响

书中介绍了大萧条时期，就业环境如何给大家带来了巨大的伤害。乔治·奥威尔的描述是：“让我害怕并震惊的事情是，看到许多人因为失业而感到羞愧。”

在一个合理的社会中，每个人应该能够通过劳动自食其力。这让社会处于一个体面的状态。如果社会和经济制度让大量民众失去工作，那么一方面给个体会带来巨大的心理打击，另一方面也会给社会带来不稳定因素。

3、日本的终身雇佣制

日本的终身雇佣制来源于 20 世纪上半叶。当时日本的制造业很依赖未婚年轻女性，但是这一劳动队伍缺乏经验，同时流失率高。为了平衡流失率，日本慢慢发展出了终身雇佣制。

同时，1930 年，日本通过放弃金本位和对外扩张，避免了欧洲传过来的大萧条，从而让企业无需解雇员工，强化了终身雇佣制的文化。

4、二战德国为什么会失败

二战核心打的是经济战，虽然德国战术很强，但是从经济产出看，在 1944 年， 盟军的生产效率与德日对比为 150:24。即：德国和日本每生产出 1 架飞机，对方可以生产 6 架。

5、社会主义国家选择企业国有化的理由

作者提供了 3 个主要原因：

  • 担心垄断。领导人认为垄断企业会对社会公众进行剥削，除非国有化。
  • 担心腐败。垄断企业可能直接收买负责监管的机构。
  • 马克思主义信仰。认为资本市场具备剥削性质，只有公有制才能避免这种剥削。

以上理由多少可以用来理解我们的社会。

6、安全资产短缺问题

当经济危机发生的时候，大家会抛售之前被认为安全的资产。这个时候就会出现安全资产短缺的问题。这个时候怎么办呢？

作者介绍了白芝浩-明斯基策略：为应对安全资产短缺现象，政府的最优选择是立即基于平时被视为优质资产的抵押品提供充足的贷款，但收取惩罚性利率。

提供充足贷款意味着创造足够多的安全资产，使供应不再短缺。收取惩罚性利率则意味着防范投机性金融机构利用这种混乱局面来渔利。

以上。

2024 年个人总结

✇唐巧的博客
唐巧

一、工作

财务视角

2024 年从财务视角，业务整体有不小的进步。

23 年虽然业务增长不错，但是整体有将将近千万的亏损，而 24 年整体的赢利是上千万的。所以业务整体健康度更高。当然，因为我们严卡利润率，我们的营收规模在 2024 年基本上没有什么增长，还是在 2 个亿左右。希望 2025 年有所增长。

海外业务在收缩为一人之后，也有不小的起色。我们在韩国还是找到了一条基于 coupang 全拖管的立足之地，可以基于这个基本盘开始做增长。虽然小，但是不至于每个月担心巨大的亏损，所以能睡得着觉。

产品视角

分产品来说，2024 年我们没有交付什么成功的新产品。虽然我们在年初上线了英语闪卡机，下半年上线了斑马拼音机 G2，但是这两款产品都没能上规模。不管是达人还是直播间，这两款产品都运营得比较艰难。

斑马童书

年底还有一个大的变化，就是我开始负责斑马童书。

童书是一个市场比玩教具小，同时竞争更加激烈的品类。但是对我来说，能够学习一个新的品类的玩法，也是一种成长，所以我还是很愿意投入精力在里面，看看能不能深耕出一些结果。

二、读书和写作

24 年一共读了 10 本书，以下是读书笔记：

写作方面，整理了以下文章：

今年还写了一篇涉及农夫山泉的文章《替农夫山泉说句话》，整个过程对我的帮助也很大，让我理解了情绪的力量。虽然当时争议很大，但事后看来，我的观点是对的，这也让我很开心。

三、爱好

今年开始系统性将 CSPJ 培训作为自己的爱好，我打算把这作为自己退休后的生活内容。因为目标在 20 年之后，所以我也开始慢慢总结自己在信息学竞赛上的经验，共分享了以下几篇文章：

除了爱好外，今年还做了一些事情来悦己：

  • 买了一台极米 Z7X 高亮版投影仪，在床上看投屏的感受很好。
  • 买了一台 M3 的 MacBook Air，在家用电脑的幸福感直线上升。
  • 买了一部荣耀 Magic V3 折叠屏。在工作中看文档效率，以及读书的体验提升明显。
  • 买了一台 Insta 360 拇指相机。发现拍的时候很爽，但剪辑视频累死人。
  • 双 11 给家里的猫买了自动喂食器和自动喂水器。再也不用每天惦记着毛孩子的吃喝问题了。不过喂食器买完有点后悔，应该买带摄像头的，这样就可以知道有没有吃完。

今年也买了一些软件：

  • Sublime Text，花了 99 美元。平时写博客和 CSPJ 代码都用它。
  • Longshot，花了大概 100 RMB。可以支持长截图。
  • Bartender 5，MacBook 的刘海屏下，没这个显示不了太多状态栏的东西。

四、理财

今年理财在贯彻自己年初目标上执行得还可以。

  • 年初定下来的定投目标，执行比较顺利。513500 算是一个很不错的 QDII 标的，唯一的缺点就是综合管理费是 0.91%

  • 年初还想在合适的时候赎回指数增强产品，这个也在年底做了。之前持有了三年的金锝和九坤的 500 指数增强，发现不同的产品增强的成绩差很多，能差 10% 以上。

  • 赎回了元盛 CTA。元盛给我的理解是：它能够在经济上行和下行的时候，都能捕捉到套利机会。但是元盛近两年的收益都是负的，我无法理解为什么这两年都没有机会。和管理团队的沟通机会也不是很好，所以赎回了。

今年整体港股和 A 股都有不错的收益。A 股整体有 19.05% 的收益。

港股里面：

  • 腾讯 417，+11%
  • 恒生高股息 23.9，+4%
  • 波司登 3.88，+18%
  • 海底捞 15.9，+27%
  • 伟易达 52.8，-2.9%

今年在理财上也有更多的思考和成长。比如：

  • 不懂不碰。以前是没那么遵守的，今年会更加严格。我也因此卖出了茅台。
  • 再平衡。以前没有严格做，在建平上吃了大亏，建平曾经有 100% 的收益，那个时候没有做再平衡，心理上贪多，还是自己能力不够，今年开始认真做这个事情。

五、24 年的目标回顾

  • 工作：
    • 销售：搭建好销售团队，带好团队的核心成员。培养有共同价值观和长久共事意愿的同事。这一点有一些进展，团队成员今年有一些流动，我觉得是好的。
    • 产品：推进硬件产品的创新尝试。今年没什么有效的落地，不算很好。
  • 理财：
    • 定投少量标普 500，建立初始仓位。今年做得不错。
    • 在合适的时候减少 A 股的指数增强仓位。今年做得不错。
  • 个人：
    • 读 6 本书。完成了，最后读了 9 本。
    • 很久没出国了，想抽空去一趟加拿大。没能完成。
    • 每月游泳一次。完成了。
    • 积极乐观。今年马马虎虎吧。

六、25 年的目标

  • 工作：硬件稳中有增，童书赢亏打正。带好童书业务。
  • 理财：做好配置，找到能拿 10 年的标的，并能坚定持有。
  • 个人：读 6 本书。CSPJ 教学继续累进。

七、个人 Milestone

  • 硬件业务利润过千万
  • 开始负责童书售卖业务

极致性价比 - 读《小米创业思考》

✇唐巧的博客
唐巧

其实我以前一直不理解雷军。

原因一是我在猿辅导工作，我们做的产品都是追求创新和高品质。因为成本不低，所以我们的产品定价不那么便宜。像我们公司的学练机、月子中心、咖啡、月龄盒，以及我负责的斑马玩教具，说实话定价在行业都是比较高的。

原因二是我比较欣赏的人，不管是公司内部的同事，还是公司外部的一些人，都对 “性价比” 这个词表现出不喜欢。这种不喜欢主要是站在商业角度，这种模式做起来太辛苦，太容易失败。

原因三是我自己曾负责过一款基于微信传播的英语学习产品。在这个产品失败前，我们尝试过极致的低价，但是最后并没有带来同等回报的增长，所以我知道，低价并不好做。

最近读了根据雷军口述整理出来的《小米创业思考》，终于有那么一点点理解雷军要做什么了。

以下是一些感悟。

雷军的 “极致性价比” 逻辑

雷军的 “极致性价比” 的想法来自 Costco，他在采访中说，一个在中国国内卖几千块钱的新秀丽的行李箱，在 Costco 只需要几百块钱。同时，雷军是一个有比较多社会责任感的企业家，他希望在互联网时代，大家可以用厚道的价格买到极致体验的东西，于是，小米成了他这个理想的实践地。

企业的存在，首先是因为有社会价值，即用户需求。首先因为用户需要某种服务，才会有相应的企业存在。在用户需求的基础下，企业才会有自己的经营使命和战略，战略应该围绕着自己的社会价值，去更好地满足自己的社会价值，这样的企业才能活得更久。

小米运用 “极致性价比” 逻辑，选择了一个极度差异化的经营模式，这种模式下：

  • 小米的产品具备独特的价值：性价比高。
  • 小米的产品总成本领先：因为量大。
  • 小米的竞争对手难以模仿。因为这种模式太难生存了。

所以，小米其实是选了一条几乎没有人，也几乎没有人走成功的路。

所以，了解完小米的逻辑之后，我理解了雷军。其实常见的经营模式雷军都知道，也都理解，但是雷军就是想走一条不一样的路。同时他也认为这条路虽然难，但是对于开创者的回报巨大。

小米如何完成 “不可能三角”

小米这种模式，需要同时做到三点：产品好、价格低，以及要有合理的利润（也就是股东回报），雷军称之为 “不可能三角”。那他是如何完成的呢？

  • 产品好。雷军要求团队只做高端和创新的产品，即便是做充电宝，也是将原本用在笔记本电脑上的铝外壳做到了充电宝中。除了产品好外，小米在打造新品时，首先考量的第一要素是，产品是否具备“明天属性”。“明天属性”是指代表先进趋势的体验，而且这种体验是用户一旦用过就不想放手的。比如用户一旦用了智能手机，就再也不想用非智能手机了。

  • 价格低。雷军相信厚道的定价会带来规模效应，所以，他的很多产品是贴着成本价来定的。首款小米手机，成本 2000 块，他就定价 1999。这充分诠释了他对于价格的理解。

  • 合理利润。这么低的价格还能有利润吗？只有向制造环节要规模效应和生产效率，同时向流通环节要效率。

在合理利润这个点上，雷军做了很多事情。比如在制造环节：

  • 他们投资机械臂算法的公司，希望将机械臂的价格打下来，这样就可以在生产中尽可能使用机械臂。
  • 他们将生产线做改造，将不同产线的差异装配点模块化，使得换线成本显著降低。

在向流程环节要效率这个点上，雷军遇到了很大的挑战，没有线下的渠道愿意与他合作。于是在初期，他只能和自己的售后合作伙伴来合作开店，最终把线下渠道的成本压到了 10% 左右。而传统的渠道，成本是 20% 左右。

但是，即使到了现在，小米在合理利润这个点上，也没有完全通过市场检验。在手机端，小米因为有大量应用市场广告和 App 预装等服务性收费，才使得他有足够的利润。但是在硬件端，不是每款硬件都可以靠服务收费的，比如大部分小米生态链产品就不太需要服务，小米还需要在未来回答这些问题。

小米如何做第一辆车

小米切入造车行业，刚开始下属的提案有很多创新。雷军觉得不好，他觉得大公司做新业务的三个大坑：认知错位、惯性思维、偶像包袱。总觉得自己牛逼，做新业务要干件大事，但是自己在新领域很可能就是一个小学生，有很多该交的学费都还没交。

所以，雷军要求团队 “先确保做一款好车，一款能够与当下同级所有产品比拼的好车，在确保这个目标的基础上，再考虑颠覆的部分。”

当目标变成 “一款好车” 时，颠覆不颠覆就不那么重要了，什么东西好拿过来借鉴就好了。于是，小米的第一款车显得很熟悉，很多保时捷上的设计被借鉴来了，大家也被一款好的设计所吸引。

虽然入局晚了几年，但小米汽车还是获得了一个梦幻开局。

终局思维

雷军在书中提到了消费电子行业的规律：当 15-20 年后行业进入成熟期，全球前 5 的品牌必将手握 80% 以上的份额。也就是说，只有最终进入全球行业前 5，做到年出货 1000 万台以上才有意义。

雷军在进入这个行业的最初，就想好了 20 年后的终局。这种终局思维才让他能够做长期主义的事情，包括投入三电等基础能力的研发，包括为造车留够足够的资金，也包括他自己的 All in 行为。

小米曾经犯的错误

芒格说：如果你知道自己可能死在哪里，就永远不要去那个地方。雷军在书中提了很多小米犯的错误，这些错误让我记忆犹新。以下是一些记录：

性价比应该作用在用户价值上

小米早期连 SIM 卡的卡针都要用 10 倍于同行的材质和工艺，这事后来被雷军叫停了。雷军认为，所有的产品体验成本，应该用在用户价值上，如果用户用不到，就是自嗨。SIM 卡的卡针大部分用户只会用一次，这个卡针上就没必要用 10 倍于同行的成本。

在消费品行业，一些产品包装也会有同样的问题。如果消费者收到的产品过度包装，消费者就会认为 “羊毛出在羊身上”，这反倒是一种浪费。

品牌

雷军认为，自己在红米品牌上犯了错，以及之前用了很多 X 米的生态链品牌都是不对的，这些品牌模糊了小米品牌。所以，后来红米改名成为了 Redmi。

小米品牌，最终只用在了非常核心的产品上，包括：手机、电视、路由、音箱、笔记本电脑，以及后来做的汽车。

以上。

CSPJ 教学思考：宽度优先搜索

✇唐巧的博客
唐巧

在学习完数据结构队列(queue)后，就可以让学生学习宽度优先搜索了。

宽度优先搜索（BFS）的形式相对固定，但是写起来代码偏长，学生在学习的时候，老是容易忘掉一些环节，所以需要加强练习。

1、模版记忆

我整理了一个 BFS 的模版，每次教学前让孩子复述这个环节，通过这种方式来强化模版的记忆，帮助学生掌握这个算法。

模版如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
void bfs() {
    queue< ? > q;

    q.push( ? );
    标记 ? 已经处理
    
    while (!q.empty()) {
        ? = q.front(); q.pop();

        for(各种情况) {
          if (可入队) {
            q.push( ? )
            标记 ? 已经处理
          }
        } 
    }
}

2、关于结构体的使用

在教学宽度优先搜索的初期，其实并不需要将入队的数据整合成结构体。这样反而会让代码变得更复杂。可以直接将需要入队的数据成组地 push 和 pop，这样就实现了简易的类似结构体的效果。

3、教学题目

推荐的教学题目如下：

题目名 说明
B3625 迷宫寻路 新手入门，没有陷阱，学习方向数组写法
P1443 马的遍历 需要求步数，需要写 8 个方向
P1135 奇怪的电梯 BFS 不仅仅可以是在地图上，也可以是另外的搜索形式
P1162 填涂颜色 学习标记技巧：将地图往外扩一圈 0 ，减少标记难度
P1825 Corn Maze S 变种的地图，可以传送
P1451 求细胞数量 多次的 BFS 标记

推荐更多练习的题目如下，可作为基础训练之用：

题目名 说明
P1746 离开中山路 比较标准的练习，无坑
P1506 拯救oibh总部 强化P1162 填涂颜色 中学到的标记技巧
P1331 海战 多次 BFS 标记的同时，如何判断标记物是矩行

以下题目难度更高一些，可以作为强化训练之用：

题目名 说明
P2895 Meteor Shower S USACO 08 FEB
P1141 01迷宫 数据量很大，需要提前保存查询结果
P2802 回家 状态变为走过时的血量有没有变高
P8604 危险系数 [蓝桥杯 2013 国 C]题目，用 BFS 暴力尝试
Takahashi is Slime 2 变种的 BFS，需要用优先队列

4、例题代码

以下是详细的例题代码说明。

B3625 迷宫寻路

B3625 迷宫寻路 是一道非常基础的宽度优先搜索，只需要输出 YES 或者 NO，对输出的要求也较小，适合拿来入门教学。

在本例题中，我们也要开始教会学生定义 movex、movey 数组，后续在迷宫一类的宽度搜索题目中，这种技巧非常见。movex、movey 的快速定义技巧是：movex 和 movey 的结构交替，每一组都是一个 1 和一个 0，同时变换 1 的正负号。记住这样的技巧就可以快速定义出这两个数组。代码如下：

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

本例还需要一个数组标记是否走过，我们使用 flag 数组。参考代码如下：

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
 
/**
 * B3625 迷宫寻路，宽度优先搜索。
 */
#include <bits/stdc++.h>
using namespace std;

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

void bfs(int x, int y) {
    bool result = false;
    int tox, toy;
    queue<int> q;
    q.push(x); q.push(y);
    flag[x][y] = true;
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        if (x == n-1 && y == m-1) {
            result = true;
            break;
        }
        for (int i = 0; i < 4; ++i) {
            tox = x + movex[i];
            toy = y + movey[i];
            if (tox >= 0 && tox <n && toy >=0 && toy<m
                && tu[tox][toy] == '.' 
                && flag[tox][toy]== false) {
                flag[tox][toy] = true;
                q.push(tox); q.push(toy);
            }
        }
    }
    if (result) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> tu[i];
    }
    bfs(0, 0);
    return 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
/**
 * B3625 迷宫寻路，宽度优先搜索。
 */
#include <bits/stdc++.h>
using namespace std;

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

void bfs(int x, int y) {
    bool result = false;
    int tox, toy, step;
    queue<int> q;
    q.push(x); q.push(y); 
    q.push(1); // 改动 1
    flag[x][y] = true;
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        step = q.front(); q.pop();  // 改动 2
        if (x == n-1 && y == m-1) {
            result = true;
            ans = step;  // 改动 3
            break;
        }
        for (int i = 0; i < 4; ++i) {
            tox = x + movex[i];
            toy = y + movey[i];
            if (tox >= 0 && tox <n && toy >=0 && toy<m
                && tu[tox][toy] == '.' 
                && flag[tox][toy]== false) {
                flag[tox][toy] = true;
                q.push(tox); q.push(toy); 
                q.push(step+1);  // 改动 4
            }
        }
    }
    if (result) cout << "Yes, step = " << ans << endl;
    else cout << "No" << endl;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> tu[i];
    }
    bfs(0, 0);
    return 0;
}

迷宫寻路加强：求路径

当我们需要输出路径的时候，我们需要做两件事情：

1、把 BFS 经过的数据全部保存下来。这个时候我们就不能用队列了，只能用 vector，然后另外用一个变量 idx 来记录处理过的元素下标。于是，判断是否处理完的条件变成了如下的形式：

1
 
while (idx != q.size())

2、我们需要对每个元素中增加一个 parent 变量，记录它是来自哪一个下标。这样就可以把整个路径串起来。如下的形式：

1
2
3
4
5
6
 
struct Node {
    int x, y, step, parent;
    Node(int _x, int _y, int _step, int _parent) {
        x = _x; y = _y; step = _step; parent=_parent;
    }
};

最终，整体的代码如下：

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
 
/**
 * B3625 迷宫寻路，宽度优先搜索。
 */
#include <bits/stdc++.h>
using namespace std;

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

struct Node {
    int x, y, step, parent;
    Node(int _x, int _y, int _step, int _parent) {
        x = _x; y = _y; step = _step; parent=_parent;
    }
};

void bfs(int x, int y) {
    bool result = false;
    int tox, toy, step;
    vector<Node> q;
    int idx = 0;
    q.push_back(Node(x, y, 1, -1));
    flag[x][y] = true;
    while (idx != q.size()) {
        Node node = q[idx];
        if (node.x == n-1 && node.y == m-1) {
            result = true;
            // output
            stack<Node> s;
            s.push(node);
            while (node.parent != -1) {
                node = q[node.parent];
                s.push(node);
            }
            while (!s.empty()) {
                node = s.top(); s.pop();
                printf("(%d, %d) ->\n", node.x+1, node.y+1);
            }
            break;
        }
        for (int i = 0; i < 4; ++i) {
            tox = node.x + movex[i];
            toy = node.y + movey[i];
            if (tox >= 0 && tox <n && toy >=0 && toy<m
                && tu[tox][toy] == '.' 
                && flag[tox][toy]== false) {
                flag[tox][toy] = true;
                q.push_back(Node(tox, toy, step+1, idx));
            }
        }
        idx++;
    }
    if (!result) printf("No\n");
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> tu[i];
    }
    bfs(0, 0);
    return 0;
}
/*
3 5
.##.#
.#...
...#.
*/

P1443 马的遍历

有了迷宫寻路的变种练习基础，我们就可以正式练习用 BFS 来求最近的步数一类的题目了。这其中比较适合的题目是： P1443 马的遍历。

《马的遍历》一题要求我们把所有位置的最近距离都求出来，我们可以用一个数组来保存结果。

同时，马可以跳 8 个方向，有了之前的建 movex, movey 的经验，我们知道，每组数是 1 与 2 的各种组合。于是可以快速写出来这两个方向数组。

具体写法是：

  • 先写 x 数组，把所有的负数写出来，再写所有的正数。
  • 考虑到每个数会有正负两个 y 与此搭档，所以每个数我们写两遍。这样就写出来了 -2,-2,-1,-1,1,1,2,2
  • 然后我们对着 movex 写 movey，凡是对应的 movex 是 2 的，我们就写 1，凡是 movex 是 1的，我们就写 2，同样的我们需要写正数和负数两遍。
  • 写完后两个数组的字符串也应该是刚好一样的，可以帮我们作为一个检查手段。

具体如下所示：

1
2
 
int movex[]={-2,-2,-1,-1,1,1,2,2};
int movey[]={-1,1,2,-2,2,-2,1,-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
 
/**
 * P1443 马的遍历, 宽度优先搜索
 */
#include <bits/stdc++.h>
using namespace std;

// 坐标是从 1,1 开始算的
int n, m, x, y;
int tu[410][410];
bool flag[410][410]={false};
int movex[]={-2,-2,-1,-1,1,1,2,2};
int movey[]={-1,1,2,-2,2,-2,1,-1};

void bfs(int x, int y) {
    queue<int> q;

    q.push(x); q.push(y); q.push(0);
    tu[x][y] = 0;
    flag[x][y] = true;
    
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        int step = q.front(); q.pop();
        for (int i = 0; i < 8; ++i) {
            int tox = x + movex[i];
            int toy = y + movey[i];
            if (tox>=1 && tox<=n && toy>=1 && toy<=m &&
                !flag[tox][toy]){
                flag[tox][toy] = true;
                q.push(tox); q.push(toy); q.push(step+1);
                tu[tox][toy] = step+1;
            }
        }
    }
}

int main() {
    memset(tu, -1, sizeof(tu));
    cin>>n>>m>>x>>y;
    bfs(x, y);
    for (int i = 1; i <=n ; ++i) {
        for (int j = 1; j<=m; ++j) {
            printf("%d ", tu[i][j]);
        }
        printf("\n");
    }
    return 0;
}

本题还有一个小的教学点，就是用 memset 来初始化值为 -1。可以顺便教学 memset 可以初使化的值，告诉学生不是每种值都可以用 memset 来初始化。

P1135 奇怪的电梯

P1135 奇怪的电梯 一题的意义在于，用非地图的形式来教学 BFS，让学生知道 BFS 不仅仅可以是在地图上。

但从实现来说，此题的难度相对较小。此题的参考代码如下：

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
 
/**
 * P1135 奇怪的电梯
 * 
 * 宽度优先搜索
 */
#include <bits/stdc++.h>
using namespace std;

int N, A, B;
int jump[210];
char flag[210]={0};
int ans = -1;

struct Node {
    int v;
    int step;
};

void bfs() {
    Node node, up, down;
    queue<Node> q;

    if (A == B) {
        ans = 0;
        return ;
    }
    node.v = A;
    node.step = 0;
    q.push(node);
    flag[node.v] = 1;
    while (!q.empty()) {
        up = down = node = q.front(); q.pop();
        
        up.v += jump[node.v];
        down.v -= jump[node.v];
        up.step = down.step = node.step + 1;
        if (up.v <= N && flag[up.v] == 0) {
            q.push(up);
            flag[up.v] = 1;
        } 
        if (down.v >=1 && flag[down.v] ==0 ) {
            q.push( down );
            flag[down.v] = 1;
        } 
        if (up.v == B || down.v == B) {
            ans = node.step + 1;
            break;
        }
    }
}


int main() {
    scanf("%d%d%d", &N, &A, &B);
    for (int i = 0; i < N; ++i) {
        scanf("%d", jump+i+1);
    }
    bfs();
    printf("%d\n", ans);
    return 0;
}

P1162 填涂颜色

P1162 填涂颜色 可以用来学习地图标记的一个技巧：将地图往外扩一圈 0 ，减少标记难度。实际在写的时候，只需要从下标 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
/**
 * P1162 填涂颜色
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int tu[40][40] = {0};
bool flag[40][40] = {false};
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};

void bfs(int x, int y) {
    queue<int> q;
    q.push(x);
    q.push(y);
    flag[x][y] = true;
    
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int tox = x+movex[i];
            int toy = y+movey[i];
            if (tox>=0 && tox<=n+1 && toy >=0 && toy<=n+1
                && tu[tox][toy] == 0 && flag[tox][toy]==false) {
                q.push(tox);
                q.push(toy);
                flag[tox][toy] = true;
            }
        } 
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <=n; ++j) {
            scanf("%d", &tu[i][j]);
        }
    }

    bfs(0, 0);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <=n; ++j) {
            if (tu[i][j] == 0 && flag[i][j] == false) {
                printf("%d ", 2);
            } else {
                printf("%d ", tu[i][j]);
            }
        }
        printf("\n");
    }

    return 0;
}

/*

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 1 0
1 1 0 0 1 1
0 1 0 0 1 1
1 1 1 1 1 0
*/

P1506 拯救oibh总部

P1506 拯救oibh总部 强化上一题学到的技巧。

同时我们此题学习用 memset 将 char 数组统一设置成字符’0’：

1
 
memset(tu, '0', sizeof(tu));

参考代码：

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
 
/**
 * P1506 拯救oibh总部
 */
#include <bits/stdc++.h>
using namespace std;

int n,m;
char tu[510][510]={0};
bool flag[510][510]={false};
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};

void bfs(int x, int y) {
    queue<int> q;
    q.push(x);
    q.push(y);
    flag[x][y] = 1;
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int tox = x + movex[i];
            int toy = y + movey[i];
            if (tox>=0 && tox <=n+1 &&
                toy>=0 && toy <=m+1 &&
                tu[tox][toy] == '0' && 
                flag[tox][toy] == false) {
                flag[tox][toy] = true;
                q.push(tox);
                q.push(toy);
            }
        }
    }
}

int main() {
    memset(tu, '0', sizeof(tu));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        char ss[510];
        scanf("%s", ss);
        for (int j = 1; j <= m; ++j) {
            tu[i][j] = ss[j-1];
        }
    }
    bfs(0, 0);

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <=m; ++j) {
            if (tu[i][j] == '0' && flag[i][j]==false) 
                ans++;
        }
    }
    printf("%d\n", ans);

    return 0;
}

P1825 Corn Maze S

P1825 Corn Maze S 增加了“地图传送”这种新的玩法，使得 BFS 代码写起来会更加复杂一点。

像这种更复杂的 BFS，我们就可以引入结构体，来让代码更整洁一点。结构体定义如下：

1
2
3
4
5
 
struct Node {
    int x, y;
    Node() {x=y=0;}
    Node(int _x, int _y) {x = _x; y=_y;}
};

因为在 BFS 的过程中，我们还需要记录步数，所以我们用 STL 的 pair 来存储队列元素。借此题，我们完成了 pair 的教学。

pair 的关键用法如下：

1
2
3
4
5
6
7
8
9
 
// 定义
queue<pair<Node, int> > q;
// 入队
q.push(make_pair(a, 0));
// 出队
pair<Node, int> one = q.front(); q.pop();
// 使用
Node a = one.first;
int step = one.second;

完整的代码如下：

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
 
/**
 * P1825 [USACO11OPEN] Corn Maze S
 * 宽度优先搜索
 * 
 * 遇到传送的时候，把位置更新到另一个传送点。
 */
#include <bits/stdc++.h>
using namespace std;

int N,M;
char tu[310][310]={0};
bool flag[310][310]={0};
struct Node {
    int x, y;
    Node() {x=y=0;}
    Node(int _x, int _y) {x = _x; y=_y;}
};
Node st;
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};

bool operator==(Node a, Node b) {
    return a.x == b.x && a.y == b.y;
}

Node getNode(char ch) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (tu[i][j] == ch) {
                return Node(i,j);
            }
        }
    }
    return Node(0, 0);
}

Node getOtherNode(char ch, int x, int y) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (x == i && y == j) continue;
            if (tu[i][j] == ch) {
                return Node(i,j);
            }
        }
    }
    return Node(0, 0);
}

int bfs(Node a) {
    queue<pair<Node, int> > q;
    q.push(make_pair(a, 0));
    flag[a.x][a.y] = true;
    while (!q.empty()) {
        pair<Node, int> one = q.front(); q.pop();
        a = one.first;
        int step = one.second;
        char ch = tu[a.x][a.y];
        if (ch >= 'A' && ch <='Z') {
            a = getOtherNode(ch, a.x, a.y);
        } else if (ch == '=') {
            return step;
        }
        for (int i = 0; i < 4; ++i) {
            int tox = a.x + movex[i];
            int toy = a.y + movey[i];
            if (tox>=0 && tox<N && toy>=0 && toy<M &&
                tu[tox][toy] != '#' && !flag[tox][toy]) {
                q.push(make_pair(Node(tox, toy), step+1));
                flag[tox][toy] = true;
            }
        }
    }
    return 0;
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; ++i) {
        scanf("%s", tu[i]);
    }
    Node st = getNode('@');
    printf("%d\n", bfs(st));
    return 0;
}

P1451 求细胞数量

P1451 求细胞数量 是一道非常基础的 BFS 题目。此题需要多次调用 BFS，参考代码如下：

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
 
/**
 * P1451 求细胞数量
 */
#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 0;
char tu[110][110]={0};
bool flag[110][110]={false};
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};
    
void bfs(int x, int y) {
    queue<int> q;

    q.push(x);
    q.push(y);
    flag[x][y] = true;
    
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();

        for (int i = 0; i < 4; ++i) {
            int tox = x + movex[i];
            int toy = y + movey[i];
            if (tox >= 0 && tox < n &&
                toy >= 0 && toy < m && 
                tu[tox][toy]!='0' &&
                flag[tox][toy]==false) {
                flag[tox][toy] = true;
                q.push(tox);
                q.push(toy);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", tu[i]);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (tu[i][j] != '0' && flag[i][j] == false) {
                bfs(i, j);
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

P1331 海战

P1331 海战 一题的标记矩形的形式比较难想到，我个人用的是另外一个判断方法：看看所填充的坐标最小和最大值计算出来的矩形面积与标记的数量是否刚好匹配。

参考代码如下：

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
 
/**
 * 宽度优先搜索。
 * 
 * 先用 floodfill 把每组船支标记。标记的时候，记录：
 *  - 最小 minx, miny 和最大 maxx, maxy
 * 然后判断是否标记的船只数量是否是正方形：
 *  - cnt == (maxx-minx+1)*(maxy-miny+1)
 * 
 */
#include <bits/stdc++.h>
using namespace std;

int R, C;
char tu[1100][1100] = {0};
bool flag[1100][1100] = {false};
int shipCnt = 0;
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};
bool debug = false;

bool mark(int x, int y) {
    int ans = 0;
    int minx, miny, maxx, maxy;
    queue<int> q;

    q.push(x);
    q.push(y);
    minx = maxx = x;
    miny = maxy = y;
    flag[x][y] = true;
    
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        ans++;
        minx = min(minx, x);
        miny = min(miny, y);
        maxx = max(maxx, x);
        maxy = max(maxy, y);
        for (int i = 0; i < 4; ++i) {
            int tox = x + movex[i];
            int toy = y + movey[i];
            if (tox >=0 && tox < R && toy>=0 && toy<C
                && tu[tox][toy] == '#' && !flag[tox][toy]) {
                q.push(tox);
                q.push(toy);
                flag[tox][toy] = true;
            }
        }
    }
    int cnt = (maxx-minx+1)*(maxy-miny+1);
    if (ans == cnt) {
        shipCnt++;
        return true;
    } else {
        return false;
    }
}

void init() {
    scanf("%d%d", &R, &C);
    for (int i = 0; i < R; ++i) {
        scanf("%s", tu[i]);
    }
}

void process() {
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (tu[i][j] == '#' && flag[i][j] == false) {
                if (!mark(i, j)) {
                    shipCnt = -1;
                    return;
                }
            }
        }
    }
}

int main() {
    init();
    process();
    if (shipCnt == -1) printf("Bad placement.\n");
    else printf("There are %d ships.\n", shipCnt);
    return 0;
}
/*
6 8
.....#.#
##.....#
##.....#
.......#
##.....#
#..#...#
*/

P2895 Meteor Shower S

此题解法：

  • 标记下地图每个不能行走的位置，以及它变成焦土的时间。
  • 在 BFS 的时候，如果当前时间位置还没变成焦土，就可以继续走。

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

int m;
// -1 表示可以行走，非 -1 表示在第 i 时刻变成焦土
int tu[310][310];
bool vis[310][310];
int movex[] = {0, 0, 0, 1, -1};
int movey[] = {0, 1, -1, 0, 0};
struct Node {
    int x, y, t;
    Node(int _x, int _y, int _t) : x(_x), y(_y), t(_t) {}
};

void mark(int x, int y, int t) {
    for (int i = 0; i < 5; i++) {
        int nx = x + movex[i];
        int ny = y + movey[i];
        if (nx >= 0 && ny >= 0) {
            if (tu[nx][ny] == -1) tu[nx][ny] = t;
            else tu[nx][ny] = min(tu[nx][ny], t);
        }
    }
}

void bfs() {
    queue<Node> q;
    q.push(Node(0, 0, 0));
    vis[0][0] = true;
    while (!q.empty()) {
        Node node = q.front();
        q.pop();
        if (tu[node.x][node.y] == -1) {
            cout << node.t << endl;
            return;
        }
        for (int i = 1; i < 5; i++) {
            int nx = node.x + movex[i];
            int ny = node.y + movey[i];
            if (nx >= 0 && ny >= 0 && !vis[nx][ny]) {
                if (tu[nx][ny] == -1) {
                    cout << node.t + 1 << endl;
                    return;
                }
                if (tu[nx][ny] > node.t + 1) {
                    vis[nx][ny] = true;
                    q.push(Node(nx, ny, node.t + 1));
                }
            }
        }
    }
    cout << -1 << endl;
}

int main() {
    memset(tu, -1, sizeof(tu));
    cin >> m;
    for (int i = 0; i < m; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        mark(x, y, t);
    }
    bfs();
    
    return 0;
}

P1141 01迷宫

P1141 01迷宫 这道题的难度在于，我们需要 BFS 之后，把结果全部保存下来，之后每次查询的时候把答案直接输出就可以了。

参考代码：

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
 
/**
 * 此题 m 的量很大，所以要提前算出答案。
 */
#include <bits/stdc++.h>
using namespace std;

int n, m;
char tu[1100][1100];
int flag[1100][1100];
vector<int> ans;
int movex[]={1,-1,0,0};
int movey[]={0,0,-1,1};
bool debug=true;

char convert(char ch) {
    if (ch == '0') return '1';
    else return '0';
}

int mark(int x, int y, int v) {
    int cnt = 0;
    queue<pair<int,int> > q;
    q.push(make_pair(x, y));
    cnt++;
    flag[x][y] = v;
    while (!q.empty()) {
        pair<int, int> a = q.front(); q.pop();
        x = a.first;
        y = a.second;
        char ch = convert(tu[x][y]);
        for (int i = 0; i < 4; ++i) {
            int tox = x + movex[i];
            int toy = y + movey[i];
            if (tox >=0 && toy >=0 && tox <n && toy<n 
                &&tu[tox][toy]==ch
                &&flag[tox][toy]==-1) {
                q.push(make_pair(tox, toy));
                cnt++;
                flag[tox][toy] = v;
            }
        }
    }
    return cnt;
}

void process() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j){
            flag[i][j] = -1;
        }
    }
    int idx = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (flag[i][j] == -1) {
                // 标记 idx 
                int cnt = mark(i, j, idx);
                // 把标为 idx 的个数放到 ans 数组中
                ans.push_back(cnt);
                idx++;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", tu[i]);
    }
    process();
    for (int i = 0; i < m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        int idx = flag[x-1][y-1];
        printf("%d\n", ans[idx]);
    }
    return 0;
}

P1746 离开中山路

P1746 离开中山路参考代码如下：

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
 
/**
 * P1746 离开中山路
 */
#include <bits/stdc++.h>
using namespace std;

int n;
char tu[1100][1100]={0};
char flag[1100][1100]={0};
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};
int fx, fy, tx, ty;

int bfs(int x, int y, int step) {
    queue<int> q;
    q.push(x); q.push(y); q.push(step);
    flag[x][y] = 1;
    while (!q.empty()) {
        x = q.front(); q.pop();
        y = q.front(); q.pop();
        step = q.front(); q.pop();
        if (x == tx-1 && y == ty-1) return step;
        for (int i = 0; i < 4; ++i) {
            int tox = x+movex[i];
            int toy = y+movey[i];
            if (tox >= 0 && tox <n &&
                toy >= 0 && toy <n &&
                tu[tox][toy]=='0' &&
                flag[tox][toy]==0) {
                flag[tox][toy] = 1;
                q.push(tox); q.push(toy); q.push(step+1);
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", tu[i]);
    }
    scanf("%d%d%d%d", &fx, &fy, &tx, &ty);
    int ans = bfs(fx-1, fy-1, 0);
    printf("%d\n", ans);
    return 0;
}

P2802 回家

P2802 回家一题的解题技巧是：将 flag 数组用于保存走上去时的最大血量。如果走上去最大血量可以更高，也是可以再次走的。

另外，当只剩 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
53
54
55
56
57
58
59
60
61
62
63
64
 
/**
 * P2802 回家
 */
#include <bits/stdc++.h>
using namespace std;

int n,m;
int tu[15][15];
char flag[15][15]={0};
int sx, sy, tx, ty;
int movex[]={-1,1,0,0};
int movey[]={0,0,-1,1};

struct Node {
    int x, y, s, t;
    Node(int _x, int _y, int _s, int _t) {
        x = _x; y=_y; s=_s; t=_t;
    }
};

int bfs(int x, int y) {
    queue<Node> q;
    q.push(Node(x, y, 0, 6));
    flag[x][y] = 6;
    while (!q.empty()) {
        Node node = q.front(); q.pop();
        if (node.x == tx && node.y == ty) {
            return node.s;
        }
        // 如果没到终点，只剩 1 点血，怎么都死
        if (node.t == 1) continue;
        for (int i = 0; i < 4; ++i) {
            int tox = node.x + movex[i];
            int toy = node.y + movey[i];
            if (tox >= 0 && tox < n &&
                toy >= 0 && toy < m && 
                tu[tox][toy] != 0 &&
                flag[tox][toy] < node.t - 1) {
                flag[tox][toy] = node.t -1;
                int life = node.t - 1;
                if (tu[tox][toy] == 4) {
                    life = 6;
                }
                q.push(Node(tox, toy, node.s+1, life));
            }
        }
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%d", &tu[i][j]);
            if (tu[i][j] == 2) { sx = i; sy = j; }
            if (tu[i][j] == 3) { tx = i; ty = j; }
        }
    }
    int ans = bfs(sx, sy);
    printf("%d\n", ans);

    return 0;
}

颠覆技术的发展 - 读《浪潮将至》

✇唐巧的博客
唐巧

最近看了 DeepMind 联合创始人和微软人工智能 CEO 苏莱曼的 《浪潮将至》。

该书主要介绍了未来极大可能改变世界的三个技术领域，分别是人工智能、合成生物学、量子技术。

以下是一些读书感悟。

颠覆技术的对抗非对称性

对抗非对称性指：拥有颠覆技术的一方可以用极小的力量对抗过去不可能对抗的力量。

这可以类比为在冷兵器时代拥有机关枪的一个人就可以对抗一整个敌人军队。

核武器的对抗也具备非对称性。拥有核武器的一方对非核国家也具备碾压性的优势。当然，后面全球努力在限制这种能力，以免被恐怖组织拥有带来全球的灭顶之灾。

人工智能的非对称性体现在对很多方面：拥有超级人工智能的组织的生产力可以是千倍于传统生产力。

书中列举了 DeepMind 公司在预测蛋白质结构上的突破，在这个技术出现之前，人类的蛋白质结构数据库中只有大概 20 万个蛋白质结构。DeepMind 公司一次性上传了 2 亿个新的蛋白质结构，几乎覆盖了所有已知的蛋白质。2 亿 vs 20 万，就是一个 1000 倍的对抗优势。

马斯克的擎天柱人形机器人如果成功大规模量产，也可能将全球制造业格局重塑。现在制造业主要还是集中于人力成本低廉的国家（例如中国，东南亚，墨西哥），到时候不需要吃饭和休息的机器的成本可能是人类的 百分之一。

现在看起来，人工智能似乎可以改变所有行业，唯一不可能替代的是人类亲自服务和沟通带来的某些情绪价值。

颠覆技术的普及性

不同于核武器技术，这些颠覆性技术的获取难度非常低。现在非常多的大模型技术公司的代码和模型都是开源的，普通人可以方便地从网上获取到相关资源。GitHub 平台上已经有 1.9 亿个代码库，其中大部分都是开源的。

现在全球顶尖的研究成果论文也可以从网上免费下载。特别是预印本网站，它加速了全球获取论文的方便程度。arXiv 上已经收录了超过 200 万篇论文。

对于生物技术来说，可打印定制 DNA 链的 DNA 合成器的购买只需要几万美元，而且该机器小巧便捷。下图是我在微信公众号搜到的一款 DNA 合成器，重量为 60 公斤，尺寸为 1/8 立方米，比一个家用洗衣机还小。

作者打了一个比方：一个邪恶的恐怖组织只需要在网上下单，就可以拥有制造出新型病原体的能力。这些病原体可以被设计成规避人类的已知对策，以无症状的方式传播，具备对抗治疗的能力。

所以，未来一个人很可能“具备杀死 10 亿人的能力”，所需的仅仅是一个动机。

“绝命毒师”如果出现在那个时代，会有这样的动机吗？

颠覆技术的监管难度

颠覆技术不像原子弹那样明显让人意识到危险，所以大众还没有对监管产生紧迫感。

作者曾经在谷歌成立了一个人工智能伦理委员会。但是最终因为委员会里面有几个人曾经发表过反对跨性别的言论，于是大家的争论变成了要求这几个人从委员会辞职。

政治正确比人工智能的伦理更重要，于是这个委员会就解散了。

顺便说一下，几年前我听说谷歌所有项目成立的时候，都需要考虑这个项目组成员有没有黑人，有没有女人，是不是政治正确的。

颠覆技术的监管连政治正确都克服不了，更别说国际社会之间的各种利益鸿沟了。

未来畅想：如何减小影响

颠覆技术在未来如果把工作替代了，会产生怎样的动荡？200 年前的工业革命可以给我们一些参考。

1807 年，由于工资被消减，6000 名英国织布工人发起抗议示威。1811 年，破坏者袭击了当地的工厂，摧毁了 63 台纺织机。

颠覆技术如果让大量普通民众失业，很显然是非常危险的。我们应该在推进技术进步的同时，考虑到对现有工人的就业影响，以尽量温和的方式来推进变革。

我曾经想过如何减小自动驾驶技术对滴滴司机的就业影响。我的方法如下：

  • 同价。通过税收调节，保证自动驾驶车和有人驾驶车同价。自动驾驶车收重税，税收用于安置被影响的司机。
  • 控量。通过颁发牌照，慢慢减少有人驾驶车。
  • 转移岗位。把司机转岗培训成无人驾驶车的看护员，做一些清洁保障保养等工作。

通过以上办法，慢慢把滴滴司机都安置好了，再减少税收，让自动驾驶慢慢赢得市场。

以上假想只是针对自动驾驶技术，但如果颠覆技术一次性颠覆了大部分行业，其应对方案会变得更难。

小结

《浪潮将至》介绍了颠覆技术（人工智能、合成生物学、量子技术）的对抗非对称性，知识普及性，和监管的难度。

未来如何发展，我们拭目以待。

以上。

将 stdc++.h 加到 Macbook M1/M2/M3 编译环境中

✇唐巧的博客
唐巧

查了好多资料，大多是不能 work 的。感谢这个视频教程：https://www.youtube.com/watch?v=LmR8sRcqbq0，最终帮我完成了需求。

以下是步骤概述：

1、在命令行执行：echo | g++ -v -x c++ -E -，我的运行结果如下：

> echo | g++ -v -x c++ -E -
Apple clang version 16.0.0 (clang-1600.0.26.3)
Target: arm64-apple-darwin23.6.0
Thread model: posix
// 此处省略若干行
#include "..." search starts here:
#include <...> search starts here:
 /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include/c++/v1
 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/clang/16/include
 /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/include
 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include
 /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/System/Library/Frameworks (framework directory)
End of search list.
# 1 "<stdin>"
# 1 "<built-in>" 1
# 1 "<built-in>" 3
# 439 "<built-in>" 3
# 1 "<command line>" 1
# 1 "<built-in>" 2
# 1 "<stdin>" 2

2、在上一步的结果中，寻找 include <...> search starts here 那一行，在那一行后面有提供 5 个路径，找到中间那个路径，按住 cmd 点击，可以用鼠标打开那个路径。如下图：

3、找开之后，在那个路径新建名为 bits 的文件夹。

4、进入 bits文件夹，随便粘贴一个头文件进去，然后改名为 stdc++.h，修改文件内容如下：

// C++ includes used for precompiling -*- C++ -*-

// Copyright (C) 2003-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file stdc++.h
 *  This is an implementation file for a precompiled header.
 */

// 17.4.1.2 Headers

// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

完成以上步骤，搞定！

如何控制孩子的电脑使用

✇唐巧的博客
唐巧

背景和问题

小学生在学习编程的时候，我们必然需要使用电脑上机练习。但是，电脑上也充满了各种“诱惑”：

  • 打开网页无处不在的游戏广告，很多游戏还是网页游戏
  • 应用市场里各种各样的游戏
  • 小红书，B 站等各种各样的网站也充满吸引力

那我们如何保证孩子能够在上机的时候一直专心练习编程呢？难道得一直在旁边盯着吗？

为此，我做了一些功课，分享给大家。

解决方案（Windows 平台）

微软的 Windows 操作系统中有一个家长控制功能。通过该功能家长可以限制小朋友对计算机功能的使用，以及规定和限制使用 Windows 的某些功能。

例如: 限制孩子的账户只能使用某个应用程序、游戏等。

使用 Windows 的家长控制功能可以在不安装其它软件的情况下，控制孩子使用Windows的绝大部分应用和功能。

具体操作方式如下。

1、为孩子创建一个单独账号

  • 按下键盘上的“Windows”键+“I”键打开设置→点击“账户”
  • 点击左侧的“账户/家庭和其他用户”，并“添加账户”
  • 在弹出的窗口中点击“为孩子创建一个”，按步骤创建新的Microsoft账户
  • 用新建的账户登录，在“概述”里面的隐私设置里打开“共享我的活动”，如下图

2、在线管理家庭设置

  • 用家长账户重新登录电脑
  • 再次按下“Windows”键+“I”键打开设置→点击“账户”
  • 点击左侧的“账户/家庭和其他用户”
  • 点击“在线管理家庭设置或删除账户”打开管理链接

在管理链接中就可以管理孩子的时间了。

解决方案（Mac 平台）

  • 1、为孩子单独注册一个 Apple ID。
  • Mac 平台的家庭共享功能可以将孩子加入到一个家庭中。
  • 可以在家庭共享中进入到孩子的帐户，查看孩子的屏幕使用时间，以及限制一些功能的使用。如下图：

以上。

CSPJ 教学思考：for 循环

✇唐巧的博客
唐巧

背景和问题

小学生在学习编程的时候，像变量，赋值，输入，输出，分支这些逻辑相对容易理解。因为这与人类真实世界的很多行为相似，所以学生会很容易吸收。具体来说：

  • 变量其实就是我们平时取的“名字”或者“外号”，用于指代一种特定物品。
  • 赋值相当于为这种特定物品指定一种属性值，像是苹果的重量，价格一样。
  • 输入和输出在很多电子产品中都有接触，孩子现在很小就接触手机，非常容易理解键盘就是一种输入，屏幕显示就是一种输出。
  • 分支就是我们自然语言中的“如果…就”，非常容易类比。

但是，for 循环由于其很难与现实世界“类比”，所以成为小学生学习编程的第一个障碍。

如何理解 for 循环，并且灵活运用 for 循环，成为一个教学难点。

教学思考

我在教学 for 循环的时候发现，如果我们用尽量渐进式的方式，让孩子刚开始接触到的 for 循环与现实世界数学中的数列一一对应。然后，再一步一步拔高难度，随着难度提高，最终 for 循环可以实现求解“非波拉切数列”以及“小数点后 10000 位”这类已经高度变型的题目。

因为每一步的难度提升梯度很小，所以学生虽然找不到现实世界类比，但终于还是比较容易理解整个渐进变化的过程。

这就类似于我们学立体几何前先学平面几何，学平面几何前先学点线面一样。从微小的简单事物开始，我们最终可以创造整个世界。

以下是我对 for 循环的具体教学拆解。

教学拆解

1、用 for 循环输出数列

输出从 1-N 的等差数列是使用 for 循环最基础形式。我们先用这个引入，让孩子先初步了解 for 循环的三段形式。

for 循环的三段式其实对初学者来说还是有点绕，借此环节把 for 的基本格式熟悉。

示例代码：

cin >> n;
for (int i = 1; i <= n; ++i) {
cout << i << endl;
}

2、用 for 循环输出 1-N 的和

累加器的写法对于初学者来说是一个小障碍，但是累加器与 for 循环的结合使用在之后的变化很常见，所以我们在这个阶段把累加器引入，帮助孩子建立累加器的使用习惯。

示例代码：

int sum = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
sum += i;
}
cout << sum << endl;

注：对于不习惯 += 的学生，也可以刚开始用 sum = sum + i来教学，减少学生的陌生感。

此题对应的线上练习是：《2016：【例4.1】for循环求和》

此题也可以进一步变化为：分别求奇数和、偶数和。让学生学会在 for 里面嵌入 if 表达式。

3、用 for 循环输出 1-N 的和的平均值

平均值的计算涉及整除的概念，需要在除之前将被除数转化为小数，同时需要用 iomanip 头文件中的函数来控制输出格式，这一编程技巧正好在这一步引入，让学生逐步熟悉对输出的控制。

示例代码：

#include <iomanip>
// 此处省略若干行

int sum = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
sum += i;
}
cout << fixed << setprecision(6) << double(sum)/n << endl;

此题对应的线上练习是：《1060：均值》

4、输入 N，接着输入 N 个数求和

大部分学生以为 for 循环是 for 循环，输入是输入，却不知道for 循环里面也可以写输入。通过此题，学生可以更多了解 for 循环的用处：用来批量输入。

示例代码：

int sum = 0, a;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a;
sum += a;
}
cout << sum << endl;

相关练习：

5、输入 N 个数，求能整除 4 的个数

与上一题类似，我们在这里引入 if 条件，让学生了解，for 循环里面可以放前面学过的分支结构。

另外，本题的累加器变形为“计数”。让学生对计数的操作产生基本的认知。

示例代码：

int cnt = 0, a;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a;
if (a % 4 == 0) {
cnt++;
}
}
cout << cnt << endl;

6、输入 N 个数，统计值为 1、5 的个数

我们在上一题的基础上增加难度，让累加器可以是多个。

示例代码：

int cnt1 = 0, cnt5 = 0, a;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a;
if (a == 1) cnt1++;
if (a == 5) cnt5++;
}
cout << cnt1 << " " << cnt5 << endl;

相关练习：

7、输入 N 个数，求 N 个数的乘积

我们学会了在 for 循环中累加，计数，那更多的变化就是求乘积了。在求乘积的时候，这个累积的变量值要从 1 开始。

示例代码：

int mul = 1, a;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a;
mul = mul * a;
}
cout << mul << endl;

此题对应的线上练习是：《2019：【例4.4】求阶乘》

8、输入 N 和 M，求 M 的 N 次方

次方是乘积的另一种变化。线上的练习题是：《1069：乘方计算》

示例代码：

int mul = 1, m, n;
cin >> m >> n;
for (int i = 1; i <= n; ++i) {
mul = mul * m;
}
cout << mul << endl;

M 的 N 次方还有两种难度的加强，分别是：

  • 让学生考虑数据范围，用 long long 代替 int
  • 在数据范围超过 long long 时，取结果的末尾 5 位数

8、输入 N 个数，让你对这 N 个数做更复杂的操作

《1075：药房管理》一题就展示了一种更复杂的 for 循环。

原来我们不但可以累加，计数，求积，还可以做减法。

示例代码：

cin >> m >> n;
for (int i = 1;i <= n;i++){
    cin >> a;
    if (m >= a){
        m = m-a;
    } else {
        b = b+1;
    }
}
cout << b << endl;

9、求第 N 个斐波那契数

《1071：菲波那契数》 要求求第 K 个斐波那契数。

我们在这个 for 循环中实现了递推算法。递推是一个对新手来说很“神奇”的计算机算法，对于初学者来说，斐波那契数是最佳的一个学习例题，因为代码可以非常短。容易理解递推的核心思想。

示例代码：

#include <iostream>
using namespace std;
int main() {
    int a=1, b=1, c=1;
    int n;
    cin >> n;
    for(int i = 1; i <= n-2; i++){
        c = b+a;
        a = b;
        b = c;
    }
    cout << c << endl;
    return 0;
}

10、有一个数 N，满足 N*(N+1)*(N+2)*(N+3) = 1680 请问 N 的值是几

暴力枚举的基础代码也是 for 循环，我们用一个最简单的题目来引入枚举的思想。

示例代码：略。

11、for 的嵌套：金字塔

我们可以让学生试图输出一个二维的图形，比如输入 N，输出 N 层的金字塔。

金字塔的形状可以是这样：

*
**
***
****

也可以是这样：

   *
  **
 ***
****

也可以是这样：

   *
  ***
 *****
*******

借此让学生锻炼模拟的能力。

此题对应的线上练习是：《2027：【例4.13】三角形》

12、for 的嵌套：矩形

输入矩形的宽高，输出下面的形状。借此更一步强化学生模拟的能力。

*****
*   *
*   *
*****

此题对应的线上练习是：《1097：画矩形》

13、for 的逆序

for 循环中的三段，除了正向的写，也可以逆向的写。所以，我们可以让学生尝试把 1-N 倒着输出。

类似的，也可以提醒 for 的第三段i++其实也可以改成 i+=2之类的形式，实现各种跳着输出的情况。

教学实操

单人教学

在实操中，我们可以用一块白板进行代码的演示，然后不断擦写相关的关键代码，保留基础的 for 框架。这样方便学生观察到其中的变化与不变。

在没有白板的时候，也可以用电脑中的 IDE 或 PPT 来进行演示。

对于每一步的问题，可以让学生来应答。通过应答的过程，观察学生对此类问题的掌握情况，有选择的加速进度或者放慢进度，保证学生对知识的吸收到位。

多人教学

在多人教学的时候，可以让大家在纸上写下自己的答案，然后待大家都完成或大部分完成后，随机选择一位学生给其他人讲解，通过互助的方式，既锻炼了学生的表达，又强化了学生对知识的理解。

对于未完成的同学，可以让他反向提问，其他人帮忙解答。老师在这个过程中只需要监督整个过程，保证知识传递是正确的即可。

本分 - 读《段永平投资回答录》

✇唐巧的博客
唐巧

最近读了《段永平投资回答录》，分为商业逻辑篇和投资逻辑篇。一些感受深的点记录一下。

不为清单

段永平说：我们之所以成为我们，很多时候不是因为我们做了什么，而是因为我们不做什么。

查理芒格说：如果知道我会死在哪里，我将永远不会去那里。

两个人的观点很相似，就是用“不做/不去”的方式来限制自己的行为。为此，段永平为自己的企业经营制定了“不为清单”（Stop doing list）。这些不为清单确实帮助企业经营划清了一些原则和边界。

在段永平的不为清单里：

  • 有一些是关于企业文化价值观的，比如：不攻击竞争对手、不拖付货款。
  • 有一些是关于企业安全经营边界的，比如：不赊账、不代工、不借钱。
  • 有一些是关于企业发展原则的，比如：不做不擅长的事情、不做没有差异化的产品。

不为清单在企业管理上具备很强的高效性。因为如果是要为清单，那么这个清单可能很长，也可能很模糊，最终大家一来记不住，二来不知道执行到什么程度。但不为清单就简单很多，遇到相似的事情，不做就可以了。

附上段永平的不为清单，如下：

  • 专注。不做不擅长的事情。
  • 不借钱。不负债就不会倒闭。
  • 没有销售部。不讨价还价。
  • 不赊账。
  • 不拖付货款。
  • 不晚发工资。
  • 不做不诚信的事情。
  • 不攻击竞争对手。
  • 不打价格战。
  • 不谈性价比。
  • 不做没有差异化的产品。
  • 不弯道超车，关注自己的进步，面对客观的事物发展和成长的规律。
  • 不收购
  • 不多元化
  • 不关注市占率，不关注销量排名
  • 不盲目扩张
  • 不赚快钱
  • 不虚夸产品

价值投资的逻辑

段永平在书中帮我再次梳理了价值投资的逻辑，段永平说：

买股票就是买公司，买公司就是买其未来的现金流折现。

说说我个人的理解：买股票就是买公司，指的是用“长期拥有一家公司的心态来考量自己的买入交易”。怎么样才是“长期拥有”的心态呢，比如问自己：

  • 如果这家公司退市了，你会不会紧张
  • 如果这家公司停牌 10 年不能交易了，你会不会接受
  • 如果这家公司股价跌了，你会不会开心（因为你可以继续买入）

有人说，退市了我怎么卖掉？但是，如果你是用拥有公司的心态在买股票，首先就不应该考虑短期买卖，也不应该用着急需要用的短期资金。

有人说，股价跌了我持仓亏损怎么办？但是，如果这家企业的内在价值（即：未来现金流）是没有变化的，那么它未来会持续给你贡献高的收益回报，股价长期而言也会在内在价值基线上下波动。所以这反而是一个好的买入机会。

所以，价值投资将股票的买卖转变为了三个方面的考量：

  • 1、公司好不好
  • 2、企业文化和管理层
  • 3、价格是否划算（有安全边际）

总结下来就是：好业务、好管理、好价格。

公司好不好

对于公司好不好的考查方式有很多，比如毛利率，经营壁垒，增长率等等，但段永平用他与巴菲特午餐时，巴菲特的回答总结道：最重要的是商业模式。

什么是商业模式呢？我理解为这家公司的“天赋”，即：环境变化也很难被改变的东西。不同的商业模式决定了一些公司会很辛苦才能活下来，另一些公司很轻松就可以活下来。举个例子：

斑马玩教具做的是 2-6 岁孩子的教育硬件，因为一款硬件的使用寿命大概有 3 年左右，所以，同一款产品几乎不会有复购的。但是我们看苹果手机，同样是 3 年左右的使用寿命，但是因为用户在生命期内可能每 3 年就买一次苹果手机，加上苹果手机的软硬件生态使得用户很难把它换掉，对于一个 20 岁的用户来说，他一辈子可能会用掉几十部苹果手机（3 年换一次）。这个从复购上来讲，就是一个很好的商业模式。

但是苹果手机与可口可乐比，商业模式就又会差一些。因为苹果手机需要不停迭代产品，否则就还是可能被淘汰。但是可口可乐并不需要改产品，它可以 100 年不改产品，甚至改产品对它是有害的。从产品迭代角度，可口可乐就比苹果手机要更优秀一些。

可口可乐与茅台酒比，商业模式就又会差一些。因为同样是卖水，茅台卖不掉的酒会随着年份升值，而可口可乐卖不掉的水会过期，只能倒掉。

所以，商业模式决定了公司的经营难度，商业模式好的公司，CEO 和管理层只要不犯错，公司大概率就不会有问题。

企业文化和管理层

除了商业模式外，一家好的公司还应该有优秀的产品和市场团队。我个人认为：

  • 好的产品应该消费者导向，满足用户的真实需求；尽可能做减法，不做功能的堆叠；以体验优先，而不是以成本优先。
  • 好的市场活动应该保持克制和理性，不放大功能、不夸大承诺、不投机营销。营销的时候尽量以产品卖点为主，不讲赠品，优惠这些。

另外，公司有没有长期经营的价值导向，类似于段永平提到的不为清单。在这种文化下，管理层是否贯彻落地了相关的价值导向，而不是说一套做一套。

除了以上之外，站在股东角度，还需要看管理层是否有回报股东的意愿。这一点在 A 股上特别需要注意。

价格是否划算（有安全边际）

如果前两点通过了，那么就到了第 3 点：当前的价格是否划算。

因为我们没有哪一个人能 100% 预测对未来，所以对于企业的经营风险，也是有可能出现黑天鹅事件的。当出现这类事件后，我们的安全边际就给了我们一些安全垫。另外，虽然买股票是一个长期投资行为，但我们多年以后，还是可能会有卖出的需求，有了安全边际，在卖出的时候股价偏离真实价值的可能性就会更低一些。

长期主义的毛估估

段永平的价值投资特点还在于长期主义的毛估估，用定性的评估代替定量的计算。他说：

我觉得所谓未来现金流的定性分析比定量分析要重要的多，用公式的人往往会陷于细节而忽略整体。

当年段永平投资网易，就是看到游戏行业的巨大，认为网易很可能估计涨到百亿。这种长期主义的感性评估，使得段永平不必特别计算回报的年限和当前的财务水平，只需要足够多的耐心就可以收获到百倍以上的回报。

长期主义的毛估估，这种做法很容易找到当下被低估的成长型企业。而且看准之后收获是十倍百倍的，所以很值得学习。网易就是一个案例。

用长期主义的毛估估，也可以敢于对当下偏贵的股票下手，因为长期主义来看，当前贵的股票其实长期看起来并不贵。段永平对苹果公司的投资就是一个案例。

巴菲特曾经说过：“当时喜诗糖果如果再贵 500 万美元，他就不会买了，现在看起来真是太愚蠢了”。这也是同样的道理。

但是困难点就在于能够看这么远不容易，需要对某个行业有较深刻的认识，才能够拿得住股票，穿越股价的波动，不被外界影响。所以段永平说，他花两年才能看懂一家企业。

快速折现法

我基于段永平的毛估估思想，想了一个快速折现的方法，仅用于那种营收相对稳定的公司计算现金流折现。

具体方法是：我们假设这家公司每年的利润是 100 元，在未来 10 年内不会有大的利润差异。快速的毛估估以 7% 的现金流折现算，因为 72 法则，所以大概 10 年后的现金 100 块，在现在就只值 50 块了。于是，我们可以用简单的等差数列求和（其实不是等差数例）来估算 10 年的现金流总和：sum = (50 + 100) * 10 / 2 = 750。

这与用等比数列求和公式sum = a1*(1-q^n)/(1-q), q=1/1.06计算出来的和 780 相差无几(误差 5% 以内）。

对股价波动的理解

市场短期看是投票器，长期看是称重机。—-格雷厄姆。

短期的股价是由供求（买卖量）决定的，长期股价是由价值决定的。因为股价如果偏离价值太多，最终会被各种行为纠正。这种纠正包括：财报数据、回购、分红、甚至私有化。

总之，纠正股价偏离行为的底层支持是价值背后的现金流。关于这个，段永平举了一个具体的例子：假如市场就是不喜欢网易，网易股价一直在几千万市值，然后如果网易一年能够赚 20 亿美金，这个时候，网易的赢利能力一定能够让股价回归。

企业价值 Enterprise value

相对于 PE，段永平提出了 EE 的概念，第一个 E 指的是企业价值 Enterprise value。具体来说，企业价值 = 市值 + 负债 - 现金。段永平希望用这种方式把企业的债务也算到你拥有这家企业付出的潜在成本。当然，企业的现金就是你拥有它的直接收益，所以减掉。

整个概念还是建立在“买股票就是买公司”基础逻辑下。因为如果你买下一家公司，理论上这家公司的债务也被你买下了，所以这部分的成本不能不看。

如何能拿住百倍的增长

段永平分享了他如何拿住网易，收获了超过 100 倍的回报的。

能够拿得住最主要原因还是对公司及其业务的了解，还有就是平常心，不要去想买入的成本，把焦点放在能理解的未来现金流上。

在不断 review 自己拥有的公司的赢利能力的时候，如果逻辑没有变，就可以持续持有。

投资用闲钱，晚上能睡觉

段永平强调了投资要用闲钱，这样万一亏了，也不会影响生活质量。

另外，买入的资产不管怎么波动，都需要晚上能睡得着觉。

小结

这本书其实不那么正式，都是段永平在雪球上的发贴，但是质量挺高的，现在很难得有经营成功的企业家写书传道，所以能通过他的贴子学到东西还是挺值的。另外，段永平的很多观点很难一下子理解，还是值得多读一读，常读常新。

❌