❌

阅读视图

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

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

围圈数数

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

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

例题一：P1563 NOIP 2016 提高组 玩具谜题

此题我们：

  • 用 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 语言月赛 202503 环形游走

此题有个技巧：就是走的时候可能绕多圈，这个时候我们先把要走的步数模 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;
}

矩阵变换

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

例题：P5725【深基4.习8】求三角形

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

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

示例代码如下：

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

例题：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 1007 魔法少女小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;
}

游戏模拟

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

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

以下是一些相关的题目。

题号 描述
P1042 NOIP 2003 普及组 乒乓球
P1328 NOIP 2014 提高组 生活大爆炸版石头剪刀布
P1518 USACO2.4 两只塔姆沃斯牛 The Tamworth Two

其它模拟题目

题号 描述

斑马思维机的详细调研

✇唐巧的博客
唐巧

一、产品介绍

斑马思维机是针对 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> 两个比较器，以下是相关代码：

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

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

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

3、教学题目

推荐的教学题目如下：

题目名 说明
P2240 部分背包问题 较简单的一道贪心题
P1223 排队接水 贪心进阶
P1803 凌乱的yyy 贪心进阶
P5019 铺设道路 NOIP2018 提高组真题

4、例题代码

P2240 部分背包问题

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

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

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

参考代码如下：

#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 排队接水

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

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

#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

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

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

按开始时间排序贪心

此贪心的方法如下：

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

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

参考代码如下：

/**
 * 按开始时间排序
 */
#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;
}

按结束时间排序贪心

此贪心的方法如下：

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

这种贪心的思路是：对于每一个结束时间，如果能排（开始时间在上一个结束时间之后），就尽量安排。如果不能排，则尝试下一个结束时间。

参考代码如下：

/**
 * 按结束时间排序
 */
#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 提高组真题。之所以作为提高组题目，是因为很难想到这种贪心策略，不过一旦想清楚，写起来是很简单的。

贪心策略是：

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

参考代码：

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

以上。

读《蹒跚前行 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 的模版，每次教学前让孩子复述这个环节，通过这种方式来强化模版的记忆，帮助学生掌握这个算法。

模版如下：

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 标记的同时，如何判断标记物是矩行

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

题目名 说明
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 的正负号。记住这样的技巧就可以快速定义出这两个数组。代码如下：

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

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

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

迷宫寻路加强：求步数

有了上面的代码，我们可以在题目上做变动，比如把输出的要求改为：
如果能到达，则输出到达终点的最短步数 ，引导学生思考，现有的代码要做怎样的改造，才能实现新的要求。

于是，我们讨论得出，需要将”步数”引入到代码中，于是，原来的代码增加了两处修改：

  • 每次入队的时候，将当前位置到达的步数也入队
  • 如果到达终点，记录下来当时的步数

改动的代码如下：

/**
 * 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 来记录处理过的元素下标。于是，判断是否处理完的条件变成了如下的形式：

while (idx != q.size())

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

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

最终，整体的代码如下：

/**
 * 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，同样的我们需要写正数和负数两遍。
  • 写完后两个数组的字符串也应该是刚好一样的，可以帮我们作为一个检查手段。

具体如下所示：

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

完整的《马的遍历》的代码如下：

/**
 * 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 不仅仅可以是在地图上。

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

/**
 * 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 开始读数据即可。

此题的参考代码如下，代码的最后用注释带了一个测试用例。

/**
 * 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’：

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

参考代码：

/**
 * 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，我们就可以引入结构体，来让代码更整洁一点。结构体定义如下：

struct Node {
int x, y;
Node() {x=y=0;}
Node(int _x, int _y) {x = _x; y=_y;}
};

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

pair 的关键用法如下：

// 定义
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;

完整的代码如下：

/**
 * 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，参考代码如下：

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

参考代码如下：

/**
 * 宽度优先搜索。
 * 
 * 先用 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
.....#.#
##.....#
##.....#
.......#
##.....#
#..#...#
*/

P1141 01迷宫

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

参考代码：

/**
 * 此题 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 离开中山路参考代码如下：

/**
 * 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 格血时，下一步不管走到哪儿都是死，所以就不用扩展了。

参考代码如下：

/**
 * 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 自己拥有的公司的赢利能力的时候，如果逻辑没有变，就可以持续持有。

投资用闲钱，晚上能睡觉

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

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

小结

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

在 VS Code 中使用 cin 输入数据

✇唐巧的博客
唐巧

问题

默认在 VS Code 中，我们无法使用 cin 输入数据。

解决方案

步骤如下：

  • 安装 Code Runner 插件
  • 按 command + ,进入设置页面，输入 Run in Terminal
  • 勾选上 Whether to run code in Integrated Terminal.

如下图所示：

第一性原理思考：解决问题的通用框架(续)

✇唐巧的博客
唐巧

我在《第一性原理思考：解决问题的通用框架》介绍了一种思考解决问题的通用框架。其中的第 3 步：信息判断是制定解决方案的核心步骤，但我在原文中讲得比较笼统，这次再展开详细介绍一下。

信息判断有很多种方式和方法，我想先重点介绍几种我认为比较有用的判断方式，最后再介绍一些常见的信息判断的误区。

28 原理

我们在框架的第 1 步信息收集中，已经将问题相关的各种因素收集得比较全面。这个时候我们会发现，信息通常会非常丰富。而且，通常正面和反面的信息都有，这个时候信息判断决策就会比较困难。这个时候，我就需要用 28 原理，来找到最最核心的因素。

大自然其实就告诉了我们这个原理。在自然界，如果影响一个事情的因素有 10 个，那么这 10 个因素每个刚好权重占比 10%，是从来没有的现象。大部分时候，大自然的事物呈正态分布，核心的 20% 的因素对结果产生了 80% 的影响。

举几个真实的案例。

案例一：优化内容

我在负责小猿搜题的时候，我们想优化题目解析的呈现。该工作最极致的优化做法，就是请老师为每一道题目录制一个 5 分钟左右的视频讲解。但是，我们有 2 亿道题目，如果全部优化一遍，我们的成本巨大，这个想法将变得不可执行。

在讨论方案的时候，我们想到这个问题或许符合 28 原理，于是我们将学生的搜索结果进行统计。结果发现，80% 的搜索结果落在了大概 500 万道题目上。于是，2 亿的工作量一下子缩减了 97.5%，我们只需要做不到 5% 的工作，就可以将题目呈现体验提升 80%。

案例二：优化硬件产品

利用 28 原理做产品决策的“减法”也同样很有效果，特别是硬件产品。对于硬件产品来说，每一项功能的生产成本与功能的使用频率不成正比。核心的功能占到了 80% 以上的使用时间，但核心功能的成本占比通常不到 80%，这个时候，聚焦提升核心功能体验，减少非核心功能的开发，都是对 28 原理的应用。

案例三：填报志愿

我高考完面临填报志愿选专业，我自己喜欢计算机专业，但是呢，我的分数不够上 985 学校里面计算机专业较强的大学。于是我的决策因素就有很多，要不要换专业，如果不换选哪个学校的计算机专业。这方面的考量因素很多，比如：

  • 地域。我应该选哪个城市？
  • 学校。我应该选哪个学校？
  • 专业排名。这个学校的计算机专业排名是多少？
  • 竞争激烈度。其他人会抢这个专业吗？我的胜算是多大？
  • 就业难度。这个专业方向好就业吗？
  • 就业薪资。就业薪资是多少？
  • 兴趣。我对哪些专业有兴趣？
  • 风险。落榜的风险。

最后我花了很长时间，首先决定还是以兴趣做为第一导向，选择了计算机专业。然后优先挑选了北京的学校，因为我觉得北京离互联网行业近，可以有比较多的机会实习。最终我选择了北师大的计算机系，虽然这个专业在院校排名里面较为靠后。

在我的逻辑里面，“兴趣”就是占据 80% 权重的因素。因为有兴趣，才有可能付出比别人多，做得比别人好。相比兴趣，别的因素都不那么重要。事实证明，我的决策还是对的。我对计算机的兴趣帮助我在学习和工作中都保持了较高的投入度，进而获得了比较大的正面回报。我也在研究生阶段获得了 在 IBM 和网易的实习机会。当然，我的运气也不错，赶上了互联网行业的红利期。

谬误推导

“谬误推导”这个词是我生造的，因为我还没有找到合适的词语用于描述这种思维方式。

谬误推导是指：假设某个观点是真理，然后按照原本的逻辑推导演绎，现实世界应该会是什么样。如果推出一个与现实世界相反的结论，就说明之前的观点有误。

我有两次明显体会到谬误推导的实际用处，分享给大家。

案例一：民宿是不是一个好生意

有一年的春节，我在京郊租了一个大院子，想体验一下退休之后的田院生活。过去之后，我发现京郊有很多人把自己的宅基地改造成这种居住体验良好的民宿，然后出租获利。然后我就很好奇这是不是一个好生意，加上当时我们有“租一个院子没事去过周末”的想法，所以我们把那个村待出租的院子都考查了一番，也问了一下价格。

最后我花了一些时间，结论是：这不是一个好的生意。里面涉及的原因有很多，但我主要测算了一下财务回报模型，发现这个事情回报率太低。另外居住的新鲜感过去之后，因为远离城市会有各种不便，整体体验也不算太好。

当我把自己的逻辑分享给 gcz 的时候，他直接用了“谬误推导”来判断，他说：如果这个事情成立，那么民宿就应该产生规模化的品牌，但现在显然没有，说明这个事情不靠谱。

我当时惊了，我想：这不符合“第一性原理”呀！看事情不应该从本源去思考吗？但是我又一想，“谬误推导”还是很有价值的，因为：

  • “谬误推导”很快，我们在工作中的很多事情权重不高，深入研究一个事情的本质原因性价比太低。
  • “谬误推导”还是为第一性原理思考提供了快速的反面证据。如果要推翻这个“谬误推导”，我们容易找到那个核心问题。

案例二

段永平分享过一个在步步高的案例。当时步步高每年的广告费用很大，有高管提出：我们的广告费用这么高，不如我们自己做广告公司。因为这样，我们首先不愁客户，我们自己就是自己的客户。然后别的东西我们可以学，我们也可以招成熟广告公司的人，我们很努力，假以时日，我们肯定可以做得比较优秀。

段永平用“谬误推导”拒绝了这个提议，他说：我不知道这里面有什么逻辑问题，但是我知道我们肯定做不成。因为：如果这个假设成立的话，世界上最大的广告公司应该是”可口可乐广告公司”和“宝洁广告公司”。但显然并不是，所以我们做广告公司这件事情一定不成立。

终局思维

终局思维是把一个事情的发展看长远，从而忽略掉短期因素的影响。人们天然对身边刚刚发生的事情赋予巨大的权重，而把过去很久发生的事情赋予较低的权重，但这个是不对的。终局思维可以帮助我们看到影响事情发展的核心因素。

终局思维可以帮助我们做难而正确的事情。有一些事情决策成本巨大，比如：猿辅导要投入力量做 AI 研究院，这方面的工作非常费钱，而且短期可能看不到产出。但是如果我们用终局思维想：未来的教育产品是否需要 AI 赋能？答案就会更容易一些。

又比如，一些错误决策已经做了，有一些沉没成本已经投入了，是立即纠正，还是慢慢收缩调整？如果站在终局思维，那么就应该尽快调整，因为如果未来是要调整的，那么每提前一天都是减少更一步的损失。所以段永平说：「发现错误立即改正，不管付出多大的代价，都是最小的代价；不改正错误，将付出更大的代价」。

用终局思维看待每一次失败，失败也显得不那么重要了。如果失败没有导致个人信心丧失，反而激发出更强的斗志，同时我们又从失败中吸取了教训，那么失败是个人迈向成功的必经之路。

再说两个案例。

案例一：直播带货

拿直播带货来说，每一次直播带货事故都会对达人品牌产生不利影响，虽然短期的影响可能不大，但是这反映出达人团队的品质把控上的能力问题。长期来看，必将影响消费者在达人直播间购物的心智。所以这么来看，如果不有效解决带货品质问题，小杨哥直播间长期很难存活。

长期来看，如果直播带货的规模巨大，势必对人们的生活产生重大影响，规范直播带货中的各种宣传用语是必然的。在这个过程中，没有做好准备的达人都会被时代抛弃。

案例二：挑选领导/下属/伙伴

终局思维可以用来挑选下属、上级和合作伙伴。如果你有一个合作伙伴，每次都出会一些问题，虽然没有出大事，但是长期来看，它必将影响你的生意，早日换掉他就是一个明智的选择。公司内的上下级共事也一样可以用终局思维，如果做不到上下同欲，下属必然在未来会遭遇误解，那么与其这样，不如用脚投票，离开他不欣赏的上级。

批评观点的 4 种角度

这是我从《如何阅读一本书》中学到的方法，作者认为，批评别人的观点只能有 4 种：

  • 证明观点的知识不足。
  • 证明观点的知识错误。
  • 证明观点不合逻辑。
  • 证明观点的分析与理由是不完整的。

如果你不能用相关证据显示作者是知识不足、知识有误，或不合逻辑，你就不能反对他。

很多人面对一些结论的时候，表现出强烈的反对，但是如果你发现他不能按以上标准来反对的话，就说明他并不真正在反对，只是「不喜欢」这个结论，而这只是在表达一种情绪或者偏见。我们应该尽量避免陷入情绪中，或者至少应该在陷入情绪中时，知道自己当前只是在发泄，而不是在讨论问题。

我们在下结论的时候，也可以用这 4 点去检查一下，自己有没有知识不⾜、知识错误、不合逻辑等问题。

信息判断的误区

再说说一些信息判断的误区。

误区一：把相关性当因果

很多人把相关性归纳到因果上面。驳倒这个误区最有趣的论述就是：医院是死亡率最高的地方，所以我们应该远离医院。

作为练习，请思考下面的论述有什么问题：

统计显示，⼤部分喜欢吸烟的⼈肺癌发病率⽐不吸烟的⼈⾼ 10 倍，所以吸咽导致肺癌。

｜
｜
｜
｜
｜
｜请想一想再往下翻答案
｜
｜
｜
｜
｜
｜

答案：喜欢吸烟与肺癌只能通过上面的统计证明相关，但是不能推导出因果关系。著名的统计学家 Fisher 就喜欢吸烟，他举了一个反驳的例子：有没有可能有一种基因，带有这种基因的人会喜欢吸烟，同时，这种基因会导致肺癌发病率高。这样，不管这类人抽不抽烟，他们因为带有这种基因，所以都会有较高肺癌发病率。

关于这个误区，这里还有更多的资料（需要梯子）。

误区二：从众心理

从众效应由美国社会心理学家阿施提出，是一种普遍存在的社会心理和行为，从众心理通常是由于个体受到集体的隐形或者显性的压力，而改变自己的目标，最终选择和多数人一致的意见或行为。

从众心态在广告学中最佳的应用案例，就是讲自己的产品「销量第一」。当然，咱们不能撒谎，得真的是销量第一的时候才能讲「销量第一」。斑马思维机去年卖了 30 多万台，远远超过第 2 名，我们就找咨询公司做了一下市场调研，宣布自己销量第一。我们公司兄弟部门的产品小猿学练机，也讲自己「销量第一」。

但是，销量第一的产品就一定最好吗？其实不见得。当年的手机霸主洛基亚，也是曾经的销量第一，不也被苹果超过了。所以，从逻辑上讲，「销量第一」与产品体验第一，只能说具有一定的相关性，无法产生因果推导。

但是，大家都有从众的心态。「销量第一」就是告诉你，别人都选择了我，你是跟随大众，还是与众不同？大部分人都会选择从众。

当然，购物决策对个体的影响不大，选择「销量第一」的产品大多数时候也没毛病。但是，当我们在面临重大问题做决策的时候，从众可不一定是一个好的选择。

很多系统对从众选择会有天然的抑制，比如：

  • 股票市场，如果大家都跟着舆论买同一支股票，那么股票的价格就会高于其内在价值，造成投资的亏损。
  • 如果大家高考都报一个专业，这个专业的录取分数就会巨高。
  • 如果今年苹果非常贵，大家都选择种苹果，那么几年后苹果就会烂大街。“阳光玫瑰”就是一个真实的例子。

所以，做重大决策的时候，问问自己为什么？如果答案是：因为别人也这样，那就有点危险。

误区三：现状即是真理

现实的一些情况，原因可能很复杂，所以不能把现状做简单归因。

比如：一个企业家把公司做上市了，挣了上百亿的利润，他就一定很会经营吗？不一定。他也可能做了假账，他也可能吃到了时代的红利，比如恒大。

比如：中医到底有没有效果？简单认为它在中国存在了上千年就能当证据吗，肯定不能。放血疗法在西医还流行了上千年呢，咱们怎么不认为它有效？那应该怎么证明中医有效？

比如：有个理财经理给你推荐某个产品，说它过去 5 年年化收益超过 10%。潜台词是说：未来也会这样。那过去的业绩一定能推导出未来的业绩吗？不一定吧。

对自己的现状分析也很重要，一些人获得了一些成功就很骄傲，觉得自己很厉害，做什么都可以成功。但是成功到底是因为自己的实力还是时代给的机会，如果不能理性分析，就很可能在未来栽跟头。

误区四：情绪

情绪是做决策巨大的敌人。股票市场就是贪婪情绪和恐惧情绪的集结地，稍不注意你就被情绪统治了行为，追涨杀跌。

基于情绪做信息判断和行为有利于情绪在当下的释放，但是相关的后果我们不一能在未来能够承受。所以，更加理智的办法是把情绪的处理和信息的判断分开。

情绪的问题可以用适当的方式来排解和宣泄。信息判断和决策的问题，还是交给理性。

另外，我们也需要识别他人的情绪，将他人的情绪与事实分开接收。现在网络上的一些观点，都带有强烈的情绪，我们需要有足够的智慧去分辨它们。

小结

本文介绍了信息判断的几种框架思维，包括：28 原理、谬误推导、终局思维等。也介绍了一些思维误区，包括：把相关性当因果、从众心理、现状即是真理、情绪等。

以上。

五分钟弄懂 CSP-J

✇唐巧的博客
唐巧

本文约 1500 字，阅读需用时 5 分钟。

什么是 CSP-J

CSP（Certified Software Professional）全称是中国计算机学会（CCF）主办的“软件能力认证”，它是中国计算机学会为了提高计算机软件人才的专业水平而设立的一项专业技能认证。CSP 认证分为两个级别：CSP-J（Junior，入门级）和CSP-S（Senior，提高级）。

因为该认证主要用于选拔 NOIP 选手，所以认证的报名通道仅向各中小学的计算机老师开放。

比赛在每年的 9 月开学之后进行，比赛分为两轮。第一轮为笔试，第二轮为上机。第一轮通过之后，才能参加第二轮。2023 年 CSP-J 第一轮的通过分数线为 63 分。

比赛报名的官方网站为 https://www.noi.cn/，这里有官方关于 CSP-J 的更多介绍。

信息学相关比赛的分类

参加信息学比赛，按打怪升级的过程，可以是从 GESP 考级开始。GESP 每 3 个月就有一次考级，可以及时检验学习成果。平均 3 个月就可以完成一个级别的知识学习，在学习初期，正反馈的频率还比较高。

以下是各个比赛面向的人群和获奖难度。

比赛名 面向人群 获奖难度
GESP 小学生+初中生 共 8 级。GESP 7 级 80 分或 8 级 60 分，可跳过 CSP 第一轮
CSP-J 小学生+初中生 各省约前 20% 可拿省一等奖
CSP-S 高中生 各省约前 20% 可拿省一等奖
NOIP 高中生 各省约前 20% 可拿省一等奖
NOI 高中生 2024 年总获奖率为 85%，前 50 可获金奖
IOI 高中生 代表中国参加全球的比赛

大部分小学生和初中生的目标是 CSP-J，获得一等奖可以被各大重点高中点招。

大部分高中孩子的目标可能在 NOIP 的一等奖，因为有了这个奖项，就可以被保送或者自主招生降分录取，高考的压力会小很多。我当年就是有 NOIP 的奖项，获得了北师大的自主招生参考资格（当时全国只有 50 个资格），然后考试通过了北师大的自主招生。

CSP-J 的获奖难度

我做了一个《北京 CSP-J 近五年比赛情况》表，如下：

从中可以看到：

  • 初赛报名人数逐年增长，每年增长都在 10% 以上。22 年和 23 年分别增长了62% 和39%
  • 第一轮初赛的通过率逐年下降，每年最少下降 2pp，23 年通过率为 24%
  • 复赛获奖率非常高，即便是最低的 2023 年，也有71% 的孩子在复赛中获奖

虽然报名人数在增加，但好消息是：复赛中一等奖的获奖人数是基本按照复赛人数来计算的，得奖比例约为 20%，所以参赛人数越多，一等奖的名额就越多。

几年级可以拿到 CSP-J 一等奖

获得 CSP-J 一等奖的年级分布如下，绝大多数（74%）的孩子都是在初二或者初三，才能获得 CSP-J 一等奖。

但是，也有少量的优秀小学生（约6%），可以在小学阶段就拿到 CSP-J 一等奖，这样的学生在 2022 年有 146 人。

CSP-J 的备赛准备

CSP-J 的最佳备赛年龄是 4 年级的上学期。因为，CSP-J 的比赛在每年的 9 月份，如果从 4 年级上学期开始备赛，那么就可以有整整两年来准备。但如果从 5 年级开始备赛，那么备赛时间就只有 1 年了。

是 4 年级不是 3 年级或更早的原因是：孩子在 4 年级的智力水平发育程度相对比较容易接受 C++ 这种比较抽象的编程语言。更早的年龄还是以兴趣培养为主较好，编程语言也可以选择 Scratch 或者 Python。但到了 4 年级，就应该学 C++ 了。

因为 C++ 语言是官方比赛语言，所以准备的时候应该直接从 C++开始，否则后期还涉及语言的切换，会浪费更多的备赛时间。

CSP-J 的备赛分为如下 3 个阶段，总共约 600 小时（240 小时上课，360 小时练习）：

  • C++ 语言学习。约 24 课时。
  • 数据结构。约 24 课时。
  • 算法。约 192 课时。

总课时约 240 小时，再加 360 小时以上的练习。

一般孩子如果从 4 年级开始，每周上 2 小时的课，完成作业 3 小时，那么就需要 120 周，差不多两年的时间还差一点。如果暑假再补一些时间进去，就刚刚够学习时长。

以上是冲着全国只有 146 人达成的“小学生阶段拿一等奖”为目标的训练方式。如果目标不那么激进，按大部分学生的学习进度，在初二获奖一等奖。那么准备时间就多了 1 倍，有 6 年级和初一整整两年。而且中间可以多次参赛，积累比赛经验。这样获奖的可能性就大大增加了。

所以，理性一点的目标是：

  • 小学 4 年级开始准备
  • 小学 6 年级能够进入复赛
  • 初中 1 年级保二等奖，争一等奖
  • 初中 2 年级争一等奖
  • 初中 3 年级参加 CSP-S
  • 高中 1 年级争 CSP-S 和 NOIP 二等奖
  • 高中 2 年级争 CSP-S 和 NOIP 一等奖

其它

我也在指导一个北京的五年级孩子学习编程，准备 CSP-J，现在学习完 40 课时（约 5 个月时间），已经通过了 GESP 2 级。欢迎同行和家长联系我一起交流，我的微信：tangqiaoboy 。

以上。

西贝创始人贾国龙的成与败 - 读《折腾不止》

✇唐巧的博客
唐巧

最近读完了李翔写的《折腾不止 - 西贝创始人贾国龙的成败与蓝图》，有一些感悟，记录一下。

市场规模

餐饮行业整个市场的规模非常大，中国大概有 5 万亿的市场规模。但是基本上都是很小规模的店。

从规模化角度看，现在中国最大的中餐品牌是海底捞，营收大概有 400 亿，剩下的公司都没有过百亿。几十亿营收的公司有：九毛九（旗下有太二酸菜鱼），营收 40 亿；呷哺呷哺，营收 40 亿。

西贝也属于几十亿营收这个梯队，23 年营收 62 亿。

餐饮行业的市场规模看起来是可以 “抗通胀的”，我想到的原因是：

  • 餐饮行业的人力成本是重要的一部分支出，人力工资每年在增长。
  • 原材料成本会通胀。

我也简单查了中国统计局数据，过去 10 年中国餐饮行业的市场规模一直在增长。其中：

  • 2014 年餐饮收入达 29000 亿元
  • 2017 年餐饮收入达 39100 亿元
  • 2023 年餐饮收入达 52890 亿元

所以，餐饮行业从规模上看，是一个挺好的行业。只是能够一直坚持做好的企业不多。比如以前很火的小肥羊、俏江南，现在就已经销声匿迹。

贾国龙把西贝的成功，主要还是归因于战略选择的成功和时代机遇。其中核心的战略选择环节是：进北京、边缘开大店、进商场、全国开店。时代红利是指赶上了商业综合体的红利，很多商场给的租金比较低。

但是西贝能够持续稳定经营，还是来源于自身独特的定位（小店、小贵、儿童友好），以及对菜品品质的把控。

定位的讨论

贾国龙认为：定位理论虽然对，但是国内把它教条化了。好象除了它对，其他都错。定位理论是“小山头理论”，他们认为这是企业的唯一选择。但企业还可以做草原、做大海，为什么非得做小山头呢？

这让我想起来小米，小米用这个品牌做手机、做智能家居、也做汽车。看起来现在发展得还行。我相信雷军肯定是读过《定位》的，有一次别人问他为什么，他说小米想做“人车家全生态”，只有都用小米这个品牌，用户才能接受这样的定位。

美团也是一个案例。美团现在不停讲美好生活，大家慢慢就把美团与生活服务关联上，这样美团买药，外卖，团购，用美团这个品牌都不违和。

我认为这种“大草原”的品牌，最大的风险还是某一方面的产品投入不够，从而把整个集团的品牌损害了。记得我大学的时候是联想的无脑粉，于是第一款 MP3 买了一款联想的产品，当时其实比别的牌子要贵，但是我觉得联想这个品牌我信得过。后来我发现，这个 MP3 的产品力其实很一般，所以我的心智就变成了：“联想这家公司做 PC 还行，做别的不太行”。所以，如果不是战略选择，就不要轻易用集团品牌。

书中提到贾国龙做新的餐饮店，君智战略咨询的董事长谢伟山建议用新品牌贾国龙也采纳了。因为新品牌做失败了，大家不会因此对西贝有什么联想。

不止只是贾国龙，华与华的老板华杉也在批判定位理论（下图）。华杉认为：独特的销售主张（USP）比定位更重要。而定位理论的几个逻辑都有问题，华杉认为：

  • 定位理论说：顾客导向的时代已经过去，竞争导向的时代来临。但其实我们现在大部分成功的公司，还是因为服务好了顾客才成功，而不是因为把竞争对手打败才成功。
  • 定位理论要求有足够强的营销资源，但是实际上很多产品的市场规模和利润都无法支撑足够多的营销资源。

所以，关于“定位”，贾国龙说得很好：“没有对错，需要具体情况具体分析”。所以，这本书让我对定位理论「去魅」了。

定价的讨论

贾国龙提到顾问孟庆祥给他的三个启发，分别是：

  • 产品要匹配营销
  • 应该要投入研发，增加产品竞争力
  • 有竞争力的产品，才有定价权

我很认同以上观点。小贵的产品，才有竞争力。因为小贵才能支持研发和营销的成本。

斑马的硬件产品也一直秉承这样的理念。我们的斑马思维机、斑马拼音机等产品都是属于同行中较贵的产品。但是，这并不代表我们有着暴利。我们只是把创新的成本、产品品质的成本都放到了定价中，以便维护斑马一直以来给用户的高品质的感受。

海底捞的竞争力来自于淘汰

海底捞对业务在最后 10% 的人淘汰。海底捞因为是一个个的单店模型，所以很容易横向比较。每一个层级岗位的干部，都有相对明确的业绩产出，这个时候，如果业绩产出不行，从结果上就比较好判断。

末位淘汰也给了海底捞其他干部一定程度上的危机感，避免大公司懒散的文化。

一些不好的感受

贾国龙的一些话也给了我不太好的感受。

第一个：他喜欢下指标。 比如他说中国堡一年要开 365 家店，KPI 是很容易让人走偏的管理方式。又比如说，XXX 年要上市，要做到 XXX 亿。但他也有一个对这个不好习惯的“补丁”，就是会朝令夕改。比如第二次访谈的时候，他就表示贾国龙中国堡开了 50 家就暂停了，因为发现很多问题需要解决。

有了这个补丁，大家会对他说话的权威性降权，难怪他有一个高管说，对他唯一的不满就是老变。

第二个：贾国龙把“做大做强”作为经营的最顶层目标。他为了达成这个目标，选择了更容易规模化的快餐方向，选择了学习麦当劳。在中国堡这个产品上，也有着极强的麦当劳的影子。

虽然贾国龙也知道产品为王，懂得 MVP 来验证产品需求。贾国龙也懂得风险控制，一直用合适比例的利润来做这类的探索。但是，我始终认为，“消费者导向”（用户需求）才是驱动企业增长的最顶层原因。

在“做大做强”的目标下去寻找用户需求，不知道会不会更加短视，更加急功近利，又或者是提高风险，都是未知数，所以我不太喜欢。

小结

贾国龙作为西贝的 100% 控股的股东、老板、创始人。一个在餐饮行业深耕 30 多年的创业者。有着异于同行的各种优秀品质。他热爱学习，懂得餐饮的经营管理，又有着强烈的成长和创新动机。

在西贝核心业务每年贡献几个亿利润的情况下，他不停地创新和成长，我从他身上看到了一个企业家对自身成就的不懈追求。

以上。

❌