普通视图

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

昨天以前唐巧的博客

CSPJ 教学思考：并查集

唐巧的博客

作者唐巧

2025年2月9日 21:20

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

集合

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

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

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

并查集

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

并查集支持两种操作：

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

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

并查集的初始化

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

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

#define MAXN 1010

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

并查集的查询操作

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

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

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

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

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]));。但是教学的时候，还是展开让学生理解清楚后，再提供简化的写法比较好。

并查集的合并操作

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

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

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

判断并查集中集合的个数

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

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

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 的元素当反集元素的孩子。关健代码如下：

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

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

#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 亲戚

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

/**
 * 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。

/**
 * 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 教学思考：二分查找

唐巧的博客

作者唐巧

2025年1月25日 22:19

概述

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

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

基础模版

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

// 二分查找
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，参考代码如下：

#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 就可以了，核心代码如下：

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 行）：

#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 题。

#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

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

// 如果目标值等于或者小于 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 路标设置

二分答案+判定。

#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 烦恼的高考志愿

/**
 * 二分查找。
 * 用 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 木材加工

/**
 * 二分答案
 */
#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 个，则失败。

#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 即为真。

#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 教学思考：动态规划

唐巧的博客

作者唐巧

2025年1月5日 18:03

引言

动态规划是 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 的方式来做此题，建立基础的解题框架，虽然会超时，但是也帮助我们后面引导孩子学会记忆化搜索。代码如下：

/**
 * 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 为例的示意：

所以，我们可以将重复计算的过程保存下来，以后再次需要计算的时候，直接读取保存的结果即可。在此思想下，我们只需要在上面改动三行，即可将超时的程序改为通过。具体代码如下：

/**
 * 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。

这样，我们就可以引导学生写出第一个动态规划程序。

/**
 * 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 数字三角形同样可以用记忆化搜索引入。先写记忆化搜索的代码有助于我们理解动态规划的状态转移方程。

搜索的代码为：

/**
 * 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 循环的方式来从下往上推导。

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

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

/**
 * 动态规划：
 * 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。

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

参考程序如下：

#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]]

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

#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]]

#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]])

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

/**
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 个草药的情况。所以，我们倒着进行递推，就可以避免这种情况。

最终实现的代码如下：

/**
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],则表示那个地窖是下一个点。

参数代码：

#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'] 为上下左右相邻并且高度更低的点
初始化：无

#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，同时在进行递归调用的时候，如果当前点处理过，则返回上次的结果。

参考代码如下：

/**
 * 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]相关，所以它最终结构上被可以被化简成类似贪心的策略，即：

用一个变量记录当前的累加值，如果当前累加值为负数，则重新计算。
在累加过程中随时判断，记录最大的累加值为最终答案。

#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 的时候，记录下搜索的结果。

参考代码如下：

/**
 * 记忆化搜索
 */
#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 背包问题。可以作为基础练习。

参考代码：

#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。

#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。

P1064 金明的预算方案

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

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

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

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

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

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

以下是参考程序：

#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 个位置上的种数。

状态转移方程：

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 的时候，也是一种可能的情况，要统计进来。

参考代码：

#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 循环，否则每道菜就用了不止一次了。

参考代码：

#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 万。

以下是搜索的代码：

/**
 * 搜索
 */
#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。

#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 教学思考：贪心算法

唐巧的博客

作者唐巧

2025年1月5日 10:28

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 经济史》

唐巧的博客

作者唐巧

2024年6月29日 23:03

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

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

以下是一些笔记。

1、关于通胀

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

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

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

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

2、失业率对社会的影响

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

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

3、日本的终身雇佣制

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

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

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

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

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

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

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

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

6、安全资产短缺问题

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

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

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

以上。

2024 年个人总结

唐巧的博客

作者唐巧

2025年1月1日 10:41

一、工作

财务视角

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

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

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

产品视角

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

斑马童书

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

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

二、读书和写作

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

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

《上下同欲的几种情况》, 我思考清楚了与上级下级的关系，写了此文。
《关于私域的思考》，因为工作涉及私域售卖，总结了私域的特点。
《如何在抖音直播卖货》，一篇科普文章。
《第一性原理思考：解决问题的通用框架》，该文章是我今年在公众号的爆文，7 万阅读量。该文以及该文的《续篇》对我梳理自己的工作也有不小的帮助。

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

三、爱好

今年开始系统性将 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

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

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

唐巧的博客

作者唐巧

2024年12月22日 22:37

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

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

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

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

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

以下是一些感悟。

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

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

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

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

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

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

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

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

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

产品好。雷军要求团队只做高端和创新的产品，即便是做充电宝，也是将原本用在笔记本电脑上的铝外壳做到了充电宝中。除了产品好外，小米在打造新品时，首先考量的第一要素是，产品是否具备“明天属性”。“明天属性”是指代表先进趋势的体验，而且这种体验是用户一旦用过就不想放手的。比如用户一旦用了智能手机，就再也不想用非智能手机了。
价格低。雷军相信厚道的定价会带来规模效应，所以，他的很多产品是贴着成本价来定的。首款小米手机，成本 2000 块，他就定价 1999。这充分诠释了他对于价格的理解。
合理利润。这么低的价格还能有利润吗？只有向制造环节要规模效应和生产效率，同时向流通环节要效率。

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

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

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

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

小米如何做第一辆车

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

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

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

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

终局思维

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

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

小米曾经犯的错误

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

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

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

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

品牌

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

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

以上。

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

唐巧的博客

作者唐巧

2024年12月15日 16:54

在学习完数据结构队列(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;
}

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

唐巧的博客

作者唐巧

2024年11月17日 22:56

最近看了 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 编译环境中

唐巧的博客

作者唐巧

2024年12月1日 11:29

查了好多资料，大多是不能 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

完成以上步骤，搞定！

如何控制孩子的电脑使用

唐巧的博客

作者唐巧

2024年11月8日 09:09

背景和问题

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

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

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

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

解决方案（Windows 平台）

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

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

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

具体操作方式如下。

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

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

2、在线管理家庭设置

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

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

解决方案（Mac 平台）

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

以上。

CSPJ 教学思考：for 循环

唐巧的博客

作者唐巧

2024年11月7日 09:13

背景和问题

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

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

但是，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 表达式。

奇偶数之和线上练习：《2018：【例4.3】输出奇偶数之和》
奇数求和的线上练习：《1065：奇数求和》

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 来进行演示。

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

多人教学

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

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

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

唐巧的博客

作者唐巧

2024年10月27日 11:50

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

不为清单

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

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

两个人的观点很相似，就是用“不做/不去”的方式来限制自己的行为。为此，段永平为自己的企业经营制定了“不为清单”（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 输入数据

唐巧的博客

作者唐巧

2024年9月27日 22:18

问题

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

解决方案

步骤如下：

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

如下图所示：

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

唐巧的博客

作者唐巧

2024年9月19日 12:59

我在《第一性原理思考：解决问题的通用框架》介绍了一种思考解决问题的通用框架。其中的第 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

唐巧的博客

作者唐巧

2024年9月17日 21:51

本文约 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 。

以上。

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

唐巧的博客

作者唐巧

2024年9月17日 14:01

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

市场规模

餐饮行业整个市场的规模非常大，中国大概有 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 多年的创业者。有着异于同行的各种优秀品质。他热爱学习，懂得餐饮的经营管理，又有着强烈的成长和创新动机。

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

以上。

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

唐巧的博客

作者唐巧

2024年9月6日 03:47

前言

马斯克运用第一性原理成功创立了 SolarCity、特斯拉、SpaceX。我们在生活和工作中，也会涉及很多需要解决的未知问题。大多数时候我们都听从于「长辈经验」，这种决策方式大多数时候是对的，但是对于创新工作或者重要决策却可能是一个灾难。

我结合自己的工作实践，总结出一个基于第一性原理的思考框架，希望可以帮助大家重建问题分析的通用框架。

我应用这个通用框架解决以下各种工作上的问题：

如何提升 iOS 开发水平
如何优化直播间销量
如何在韩国卖斑马思维机

作为案例，我也教大家用这个框架解决以下生活问题：

减肥没效果怎么办
如何找到男/女朋友

希望对你有帮助。

框架概述

这个框架把解决问题分成 4 步：

信息收集
信息建模
信息判断
策略迭代

我们拿一个生活中的问题来举例：“有个朋友减肥一直没效果，想让你帮忙分析一下”。

第 1 步：信息收集

当你的朋友给你说减肥没效果的时候，你不要着急给他下诊断出解决方案，不着急说：你一定是缺少运动，或者说一定是吃太多。因为在“减肥没效果”这件事情上的原因可能有成千上万种，你得先找到原因，才能对诊下药。所以，你应该先收集信息。

在收集信息上，得做两个大类的信息收集：

1、收集经验数据
2、收集原始数据

收集经验数据

什么是经验数据？经验数据就是人们在这件事情上已经形成的方法总结。拿减肥来说，不管是小红书还是 B 站，还是微信公众号，上面已经有很多人分享减肥这件事情的经验，有成功的总结，也有常见的失败，这些都是宝贵的经验数据，你应该先收集下来。

还有哪儿有经验数据？专门的减肥书籍，应该可以找到很多。身边的减肥成功的朋友、健身房的身材管理教练，也是可以去咨询收集信息的重要来源。

对于减肥来说，以上的信息收集渠道可能就够了。对于一个通用的问题，可供寻找的经验数据源有以下这些供参考：

查阅类：搜索引擎、ChatGPT、国家统计局资料、专门书籍、知网数据库、行为研究报告
走访类：专家访谈、用户访谈、实地走访。

对于一个你完全不了解的领域，可以用 What-else 研究法。以研究 iOS 开发为例：

(what) 什么是 iOS 开发？然后你可能通过查找资料发现这是一种移动开发技术。
(else) 还有哪些是移动开发。你可能找到 Android开发，Windows Mobile 开发等。
(what) Android 是什么？然后你可能查到这是 Google 出的移动开发技术。
(else) Google 家还出了哪些开发语言？然后你可能查到 Flutter。

应用 What-else 研究法，你可以快速扩展自己在该领域的知识点，从而慢慢把知识点连成线，形成经验数据的图谱。

收集原始数据

原始数据是指现场的、未经加工和解释的数据。马斯克在思考如何造火箭的时候，查阅制造火箭的基础原料成本，就是在收集原始数据。这为他进一步利用第一性原理，推测出火箭的制造成本有大幅下降空间提供了基础信息。

还是说回减肥这个案例，对于这个减肥没效果的朋友，最重要的原始数据是什么呢？

有人说是他自己是怎么减肥的，这只说对了一半。如果你只是听他讲他是怎么减肥的，那就不是“原始数据“。因为这里面已经有了你的这个朋友的主观判断在里面。这件事情的原始数据应该是你的朋友每天的日常的生活现场和减肥的现场。你应该全程跟着这个朋友，记录下这个现场，这才是最最原始的，未经加工的数据。

我很喜欢一个美剧叫豪斯医生（Doctor House），主人公豪斯医生就从来不相信病人的口述，而是像个侦探一样，从各种现场的细节来判断真相，最终找到真实的病因，对诊下药。我想他一定是和我一样明白原始数据重要性的😁。

第 2 步：信息建模

有了第 1 步的信息收集工作，我们对问题已经有了足够多的了解，接下来就可以开始第 2 步的信息建模工作了。

信息建模的工作分为 3 步，分别是：

1、拆解问题
2、找到问题的核心数据指标
3、数字化/自动化地收集核心数据

拿减肥来说，如果你基于收集到的信息，发现你的朋友主要是运动太少，那么你就可以把减肥问题拆解成「控制摄入」和「提高代谢」两个角度。

但不同的情况下，拆解问题的角度应该不一样。如果你的朋友是因为心情抑郁暴饮暴食，那么问题就应该围绕心理健康展开拆解。如果你的朋友是因为肥胖症，那么又应该从这个病症的专业治疗角度，展开拆解。

再举一个例子：iOS 开发水平应该如何提高的？我的拆解是：输入和输出两个角度。

输入方面：我们可以拆解成阅读博客，阅读图书，看相关的视频，听相关的分享，参加相关的会议，找同事请教等。
输出方面：我们可以拆解成写总结的文章，代码练习，分享等。
- 代码练习又可以分成：工作上的代码优化、面试题目代码的练习、开源项目的参与等。

我之前也是基于上面的拆解，坚持写了好多年的技术分享，最终出版了《iOS 开发进阶》。

拆解完问题之后，我们需要将拆解完的指标量化。

拿减肥的案例来说，我们就应该收集每日摄入的卡路里和身体的代谢率指标。
拿 iOS 提高的案例来说，我们就应该量化输入和输出的周度、月度、年度目标。

有了量化的指标，如果我们能够将其数字化记录到系统中，甚至自动化收集它就更好了。

拿减肥的案例来说，我们用一个软件记录每天的卡路里摄入和代谢率，就很好。
拿 iOS 提高的案例来说，我们用统计工具记录自己代码练习量，就很好。

【练习】假如我们的问题是：如何找到男/女朋友呢？如果你的信息收集发现，问题主要出在自己太害羞，应该如何拆解问题和量化指标？

第 3 步：信息判断

执行完第 1 步和第 2 步，你还不能解决问题，因为前面只是帮你分析了数据，找到了关健的一些指标，具体怎么做并没有解决。

所以，在第 3 步，你需要根据前面的信息，做判断和决策，制定自己解决问题的「执行方案」。

拿减肥的案例来说，你需要制定每日控制卡路里摄入和代谢率的具体方法。
拿 iOS 提高的案例来说，你需要制定输入和输出的具体每日任务目标，以及做合理的时间规划等。

如果我们在面对一些创新性的问题，因为可供参考借鉴的案例不多，在制定执行方案的时候，应该尽可能打开思路，用第一性原理去思考。比如：别人造电动车没有电池就放弃了，马斯克的执行方案却是用 7000 多节松下的 18650 电池拼成一个大电池包。

第 4 步：策略迭代

你的执行方案不一定靠谱，当你发现过一段时间，关键数据指标并没有变好的时候，就说明你应该停下来思考一下了。在这一步应用 PDCA 环，可以很好地帮助你优化自己的方案。

PDCA 包括：

策略制定（Plan）
策略实施（Do）
检查过程，保障策略能够实施到位（Check）
获得策略数据反馈，调整（Act/Adjust）

有关键数据做指导，你做的任何调整都能带来正反馈（指标变好）或者负反馈（指标变差），这样你很快就能从中总结经验，对问题有更加深入的理解，从而优化自己的执行方案。

本框架的局限

本框架有三个局限：

只适合解决有原始数据的问题
只能保证策略尽可能对，不能保证执行到位
个体的思考和判断是解决问题的核心

所以，没有银弹，本框架只能帮你尽可能接近真相，真正要解决问题还是得靠你自己的思考、判断和执行。

以上。更多内容请看：《第一性原理思考：解决问题的通用框架(续)》

如何在抖音直播卖货

唐巧的博客

作者唐巧

2024年9月1日 14:52

引言

随着抖音日活破 8 亿，短视频和直播已深入我们每一个人的生活。其中，直播电商作为抖音商业化重要的一环，成为很多品牌销售工作的重点。

我之前写过一篇科普效果广告的文章，帮助很多非广告行业从业者理解效果广告，很多人很喜欢。于是，我想接着这个主题，分享一下抖音直播卖货的基础，如果你没有从事过相关工作，本文可以让你对直播电商有一个基础认知。

核心流程

直播卖货的核心流程分成两步。

第 1 步：在信息流中投放你的种草短视频素材（或直播间画面），引导用户点进你的直播间。
第 2 步：在直播间中，完成产品的介绍、答疑，并引导用户下单。

我们接下来会拆开这两个环节分开介绍。

短视频素材

介绍

我们日常在抖音上刷短视频，大概刷 10 条左右，就会出现一条是广告商投放的种草短视频。这个短视频会在右侧有一个直播的效果（如下图），短视频中的口播也会引导你进去直播间。

除了种草短视频外，广告商也可能将直播画面投放到你的信息流中，引导你进去直播间（如下图）。

种草短视频的类型

在我们所处的教育行业，一般种草短视频有以下几种类型：

身临其境真实感受。例如：“最近我家孩子…”
附加身份激发认同。例如：“作为一个海淀妈妈…”
消费观念透传实惠。例如：“不到一顿饭的钱…”
第一人称情节发展。例如：“直接产品使用视频…”
软蹭热点放大痛点。例如：“最近 xxx 新闻大家都看到了…”
制造噱头营造稀缺。例如：“不好意思，活动即将结束了…”

要做好这些短视频，有一些基础的要求：

需要符合平台和相关的法规。比如不能虚假宣传，不能恶意制造焦虑，不能诋毁竞争对手。
风格要多样。比如同样的口播文案，在车里拍可能就比在办公室拍效果好很多。但如果大家都在车里拍，你出一个在飞机上拍，效果可能又不一样。总之，风格不要雷同，不然前 5 秒的完播率会很差。

除了风格尽可能多样外，我个人认为，一个好的种草短视频还是应该尽量讲产品，把产品的核心卖点讲清楚，即便用户当下不买，那么他也会对产品有一个较为清晰的了解，这对品牌来说，可以积累长期的势能。

利润模型

如果你了解广告系统，你应该能够理解。每一个种草短视频都是基于 ECPM 进行竞价，本质上你需要尽可能提高自己的广告转化效率，否则你就无法给出市场公允的一个千次展示成本。

在抖音平台上，千次展示成本大概在 50 - 200 元之间。我们假设你的平均千次展示成本是 100 元，视频点击率是 10%，直播间的支付转化率是 10%，客单价是 100。那么:

1000 次展示（成本 100 元），能够给你带来：1000 * 10% = 100 次点击。
100 次点击能够带来 100 * 10% = 10 次成交转化。
10 次转化能够带来 10 * 100 = 1000 的收入。

如果你的商品成本是 50 元，那么你每花 100 元广告费，就有 1000 元的收入，扣除 500 元的商品成本和 100 元的广告费，就还有 400 元的利润。

这就是一个极简的直播利润模型，后面我们会继续完善它。

直播间

说完短视频素材，我们再说说直播间。

循环是直播带货的基本形式

直播间最基本的功能，就是面对不断进入直播间的用户，完成从产品讲解到引导下单的整个流程。由于每个用户在直播间的停留时间并不长（通常为 1-5 分钟），所以我们需要在非常短的时间内完成从产品讲解到引导下单的过程。而直播间，其实就是在不断循环这个过程。

我们来看看前一段时间很火的李一舟的直播间是怎么卖人工智能课的（下图）：

李一舟为什么要讲这么简洁？因为如果你随便看一个直播间的在线人数，你就会发现，每一分钟，都有超过 20% 的人离开，又会有超过 20% 的人新进入直播间。下图是一个案例，在该案例中，实时在线只有 22 人，但是每分钟进出直播间的人数分别达到了 18 人和 15 人。

假如你在线下经营一个“超级卖场”，每 1 分钟会进来 1000 人，同时上 1 分钟进来的 1000 人会离开，你应该怎么办？如果你需要 3 分钟才能讲清楚你的产品，那么不好意思，前面进来的人等不到你讲完就走了，后面进来的人，因为只听到你讲的后一半，不知道你在讲什么。

你只能抓住这仅有的 1 分钟时间，迅速完成需求挖掘，产品介绍，引导下单的过程。从这个角度看，李一舟的直播话术还挺高效的。但是，李一舟不应该撒谎，“仅有 10 个名额”这个说法对用户是一种欺骗，其实有更好的处理方式。

流量是直播的生命之源

直播间的主播讲得不管多么好，没有观众也不行。流量在很多别的平台就是付费广告，但是在抖音，还有一大部分是“自然流量”。下图是某个直播间的流量图，可以看到，它有将近一半的自然流量，这部分流量是不需要给抖音付费的。

那么如何获得自然流量呢？自然流量其实是抖音给直播间的奖励，当抖音的算法认为当前的直播间具备下面任一一个优点的时候，算法就会给与奖励。

优点一：这个直播间看起来很有趣。
优点二：这个直播间看起来很挣钱。

我们先说优点一。抖音算法认为，优质的内容应该分发给更多人。所以，如果抖音算法觉得你的直播间很有趣，被很多人喜欢，那么就会把你的直播间分发给更多人。

什么样的行为代表有趣呢？关注、互动、点赞、评论、停留。

所以，大家有没有看过这样的直播间行为：

某直播间，主播不停在说，新进直播间的朋友们，麻烦给我点个关注，送个粉丝灯牌。
某直播间，发福袋。领福袋的要求是关注+发一条指定语言的评论。

下图是小猿学练机的直播间福袋，就是一个典型的用福袋增加关注、互动、停留的例子。

我们再说说优点二：这个直播间看起来很挣钱。为了衡量挣钱的能力，抖音有一个叫做 GPM 的指标。GPM 指：平均每一千个观众下单的总金额，常用来衡量直播间卖货能力。

举个例子，如果直播间每进来 1000 个用户，就有 100 个用户下单，客单价是 200，那么你的 GPM 就是 100 * 200 = 20000。

我们知道，抖音对所有平台的交易都有抽佣的，抽佣常见的比例是 2% - 5%。所以，你的 GPM 越高，抖音得到的抽佣也就越多。如果你的 GPM 是 20000，抽佣比例是 5%，那么每 1000 个用户平台可以得到抽佣 20000*5% = 1000 元。

这样，当平台的广告流量有富余的时候，算法就会把流量给那些 GPM 高的直播间作为奖励。平台本身也会得到更多的佣金。

成本模型

我们在最初的时候提到了一个极简的成本模型：

如果你的商品成本是 50 元，那么你每花 100 元广告费，就有 1000 元的收入，扣除 500 元的商品成本和 100 元的广告费，就还有 400 元的利润。

其实，实际核算下来，你还需要付出以下的成本。

退货成本

商品都会有一定的退货率，当退货发生的时候，虽然你收回了商品，但是平台不会退还你已经付出的广告费的。所以，还是刚刚那个模型下，如果你的退货率是 30%，那么你的收入变成了 700，商品成本变成了 350，广告费 100，你的利润下降到了
700 - 350 - 100 = 250 元。

平台佣金

平台通常会抽取 5% 的交易佣金。所以，刚刚那个模型还需要减掉 700*5%=35 元。利润下降到了 215 元。

运营人员成本

直播间的主播和场控，运营都是要发工资的。根据城市不同，主播的工资为 100/小时 - 300/小时不等。场控的工资约为 50 元/小时。下图是在成都的某个直播间在微信群上发的招聘的信息。

所以，如果刚刚那个 1000 的销售额是在 0.5 小时达成的业绩，主播+场控的小时工资为 200 元。那么，你还需要付出 200*0.5=100 元的成本。利润下降到了 115 元。

GMV 提点

如果我们直播代运营公司，我们通常还需要支持 5% - 10% 的 GMV 提点。在本例中，如果我们支付 5% 的提点，则成本为 700*0.05=35 元。利润下降到 80 元。

税

如果我们售卖的是实物商品，我们需要支付 13% 的增值税。增值税只需要交“增值”的部分，我们的售价与成本的差价是 350 元，所以我们需要交 350*13%=45.5 元的税。利润下降到 34.5 元。

其它

其它成本还包括：

短视频素材的制作成本。通常情况下，一个直播间每月需要制作 40 - 80 条左右的短视频，平均每条素材的制作成本约为 500 元，月成本为 2-4 万元。
投放提点。如果我们找第三方代投公司帮我们投放，我们通常需要支付 3% - 5% 的投放提点。在本例中，我们需要支持 3-5 元。如果我们不找第三方代投公司，则需要招聘投放人员，成本可能更高。
运费险。
客服成本，提供售前和售后支持。

结束

抖音直播卖货的核心工作是短视频素材的制作和直播间的转化。
一个看起来很挣钱的直播间，在计算上退货、投流成本、商品成本、运营成本、第三方提点、税收、客服成本后，其实利润就微乎其微了。

以上。