CSP-J 三句话复习

作者：云斗官方教研团队 花老师

本章共分为两部分：知识和知识以外。

知识

这部分知识是 CSP-J 的复赛全考纲，但你如果发现自己还有很多知识不会，不要慌。一般而言，J 组的 T1/T2 不需要你掌握任何高难度知识点，200 分够很多地区的省一了。这一部分会在下一章节细讲。我们先一起进入知识的复习——

栈

最新插入的最先删除用栈，可以看出栈往往是在维护一种具有实时性质的讯息，Last In First Out。使用时要注意栈的边界问题，STL 中 !stk.empty() 别忘判，手写的也要注意栈顶 tp > 0 。

队列

最新插入的最后删除用队列，可以看出队列往往是在维护一种类似于“排队”性质的信息，时间上先来的先服务、后来的后服务。使用时也需要注意边界问题，因写法不同有以下几种情况：!q.empty() 、 head = 0, tail = 0 ; while(head < tail) 或者 head = 0, tail = 0 ; while(head <= tail) 。

接下来的两个话题：图和树在 J 组登场率较低，一般考察也只会放在 T4 考察，所以大家量力而行。

贪心

贪心不存在标准的流程，反而更像一种指引：在满足了“局部最优的并是全局最优”的条件下，你可以通过你自己的构思，来获得某个问题的最优结果。

建议正在备考的大家回顾一下自己做过的所有贪心问题，重新思考一遍问题，重新构思一遍代码。

递推

往往是类似 f[n] = f[n - 1] + f[n - 2] 的形式，建议从找规律和数学推到两方面考虑。勤算一算样例，不要忘了边界条件（例如 f[0])。

递归

函数自己调用自己，本质上是在求一个“大问题”的答案时，需要“小问题”的答案。同样是需要注意边界值。能记忆化的需要记忆化。

二分

满足单调性的问题可以二分。具体的二分有多种写法，下面是我喜欢的写法：

int l = 1, r = n, mid, ans = -1 ; 
while (l <= r){
    mid = (l + r) / 2 ; 
    if (check(mid)) ans = mid, l = mid + 1 ; 
    else r = mid - 1 ; 
}
if (ans == -1) //。。。
else //。。。

高精度

放心，出题人他不敢考的。你要是开心的话就背一背。

排序

需要掌握 sort 的用法。假设我希望将数组下标 begin ~ end 的位置排序，规则是从大到小，那么：

bool comp(int A, int B){
    return A > B ; 
}
//...
sort(a + begin, a + end + 1, comp) ; 

要注意 sort 需要让截止位置 +1。最常见的对 a[1]~a[n] 从小到大排序：

sort(a + 1, a + n + 1, comp) ; 

深度优先搜索 (dfs)

逻辑是搜到不能搜为止，撞了南墙（走到边界）再回头。从树的角度来讲，dfs 是不断地从根走到叶子节点，回溯时看能不能从任何中间节点出发继续走到另一个叶子节点。

这一部分强烈建议同学们重写几道过去曾经做过的 dfs 题，加强手感。

广度优先搜索 (bfs)

逻辑是一层一层地搜索。从树的角度来讲，我们从根节点出发，深度一致的节点会被我们放在连续的几步一块解决。实现时需要用到队列。

这一部分同样强烈建议同学们重写几道过去曾经做过的 bfs 题，加强手感。

动态规划

动态规划是 J 组里最难的考点。建议的做题步骤如下：

1. 先判断是不是 dp。这要看能不能贪心、是不是二分答案等。
2. 之后考虑设计状态。往往是“什么作为限制”就把“什么”设为状态。例如背包要求“ $n$ 个物品最多选体积 $V$ ”，所以状态就是 $f[i][j]$ 表示前 $i$ 个物品选了 $j$ 体积的最大价值。再比如过河卒问题，问从 $(0,0)$ 走到 $(n,m)$ 、每次只能向下走或者向右走的方案数——因为二维的空间坐标“限制”了卒的行动，所以 $f[i][j]$ 表示走到 $i$ 行 $j$ 列的方案数。
3. 之后考虑转移。这一部分需要根据设计的状态来考虑。核心的思路是考虑“一步转移”，也即考虑不同状态之间的“最小变化”是怎么产生的。例如，背包问题就是考虑某一个物品拿或者不拿，从而写出转移方程的。再比如，过河卒问题正是因为卒子每一步只能向右走或者向下走，所以才以此为基础设计的转移：$f[i][j] = f[i][j-1]+f[i-1][j]$，前者是向右走，后者是向下走。
4. 最后考虑能不能优化时间或者空间复杂度，以及反思转移和状态设计的合理性。这通常可以被样例数据检测。如果不合理，就返回第二步。

总之，dp 是信息学竞赛从 J 组到国家比赛里最有魅力、最有区分度、最需要练习的一个分支。因此，对于 J 组选手，其实建议大家量力而行：不一定非要追求考场上的高分。

碍于篇幅，一些基本的 dp 模型的状态和转移就不再列举了。大家可以有针对性地复习自己曾经做过的动态规划题目。

图

这部分一般不会太难。如果你是 J 组高手，需要掌握的大致有两块：

存图与建图

邻接矩阵 a[i][j]，链式前向星 struct, void add(int i, int j) ，vector G[i].push_back(j) 。记得区分是单向边还是双向边。

遍历图

一般而言就是 dfs 和 bfs 两种方式。需要注意，除非限定了是有父子关系的树或者 DAG（有向无环图），否则一定要用一个 bool check[] 来防止点的重复访问。图的遍历细节跟存储方式有关。

树

n 个点 n-1 条边，存储的方式几乎跟图没有区别，但遍历的方式多了一种从根节点开始的 dfs。以下是一种链式前向星存图，求树上每个点的深度的部分代码，或许对你会有参考价值：

const int N = 100010 ; 

struct Edge{
    int to, next ;
}E[N] ;
int cnt ;
int dep[N] ; 
int head[N] ;

void add(int u, int v){
    E[++ cnt].to = v ; 
	E[cnt].next = head[u] ; 
	head[u] = cnt ;
}
void dfs(int x, int fa){
	dep[x] = dep[fa] + 1 ; 
	for (int k = head[x] ; k ; k = E[k].next)
		if (E[k].to != fa) 
			dfs(E[k].to, x) ; 
} 

知识以外

J 组的同学要时刻铭记一个信条：J 组拿奖靠的不是你懂了多么丰富的知识和技巧，而是靠你能把多少东西以代码的形式表达出来。因此，我们更需要注意一些考试技巧以及写代码时候的细节：

策略

部分分真的很重要！T2~T4，你就放心吧，每道题至少有 20 分是很简单就能拿到手的，所以一定要打满 3.5 个小时，不要轻言放弃。

读题真的很重要！读对题目是得分的前提，要时刻记住：一遍读不懂就多读几遍，结合样例和样例解释手算几遍。

检查真的很重要！头文件、freopen、变量名（例如不能写 x1,y1）……

数组

要注意长度（不要卡着开，至少多个 5），要注意空间（也不能太长，记住 128MB 是 3300 万个 int)，要注意定义域（如果定义成了局部变量，记得要清空）。

函数与作用域

要注意定义域（全局还是局部），要注意传的参数类型（会用 & 引用和 * 指针就用，不会也没必要强求，总有你会的、更简单的实现），要注意递归的边界。

结构体

要理解结构体是一种和 int 类似的“类型”，要注意结构体声明时右大括号 } 后的分号 ;。

各种运算符

一句话：勤加括号。涉及到位运算 &,|,^ 或者是逻辑运算 &&,|| 时，多加括号准没错。

文件输入输出

#include <cstdio>
//....
int main(){
    freopen("xxx.in", "r", stdin) ; 
    freopen("xxx.out", "w", stdout) ; 
    //注意 fclose 不可与关闭流同步一起写 ios::sync_with_stdio(false);
    fclose(stdin) ;
    close(stdout) ;
    return 0 ;
}