DevTang | 唐巧的 RSS 预览

CSPJ 教学思考：二分查找

2025-01-25 22:19:44

概述

二分查找的基础逻辑很简单：我们小时候都玩过猜数字游戏，心里想一个数字（数字范围是 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。
因为 lower_bound 有可能返回的不是目标值，所以最后要判断一下。

CSPJ 教学思考：动态规划

2025-01-05 18:03:48

引言

动态规划是 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-01-05 10:28:04

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

以上。

2024 年个人总结

2025-01-01 10:41:17

一、工作

财务视角

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:53

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

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

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

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

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

以下是一些感悟。

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

雷军的 “极致性价比” 的想法来自 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:30

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

DevTang | 唐巧修改

DevTang | 唐巧的 RSS 预览

概述

基础模版

另一种模版

lower_bound

upper_bound

二分答案

教学和练习题目

P3853 路标设置

P1678 烦恼的高考志愿

P2440 木材加工

P2678 跳石头

P1182 数列分段 Section II

教学思考

小结

引言

动态规划解题的核心问题

教学题目

例题代码

P2842 纸币问题 1

P1216 数字三角形

P2840 纸币问题 2

P2834 纸币问题 3

P1048 采药

P2196 挖地雷

P1434 滑雪

P1115 最大子段和

作业代码

P4017 最大食物链计数

P2871 Charm Bracelet S

P1802 5 倍经验日

P1002 过河卒

P1064 金明的预算方案

P1077 摆花

P1164 小A点菜

P2392 考前临时抱佛脚

1、概述

2、sort 函数

3、教学题目

4、例题代码

P2240 部分背包问题

P1223 排队接水

P1803 凌乱的yyy

按开始时间排序贪心

按结束时间排序贪心

P5019 铺设道路

一、工作

财务视角

产品视角

斑马童书

二、读书和写作

三、爱好

四、理财

五、24 年的目标回顾

六、25 年的目标

七、个人 Milestone

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

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

小米如何做第一辆车

终局思维

小米曾经犯的错误

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

品牌

1、模版记忆

2、关于结构体的使用

3、教学题目

4、例题代码

B3625 迷宫寻路

迷宫寻路加强：求步数

迷宫寻路加强：求路径

P1443 马的遍历

P1135 奇怪的电梯

P1162 填涂颜色

P1506 拯救oibh总部

P1825 Corn Maze S

P1451 求细胞数量

P1331 海战

P1141 01迷宫

P1746 离开中山路