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. 之后考虑设计状态。往往是“什么作为限制”就把“什么”设为状态。例如背包要求“ nn 个物品最多选体积 VV ”,所以状态就是 f[i][j]f[i][j] 表示前 ii 个物品选了 jj 体积的最大价值。再比如过河卒问题,问从 (0,0)(0,0) 走到 (n,m)(n,m) 、每次只能向下走或者向右走的方案数——因为二维的空间坐标“限制”了卒的行动,所以 f[i][j]f[i][j] 表示走到 iijj 列的方案数。
  3. 之后考虑转移。这一部分需要根据设计的状态来考虑。核心的思路是考虑“一步转移”,也即考虑不同状态之间的“最小变化”是怎么产生的。例如,背包问题就是考虑某一个物品拿或者不拿,从而写出转移方程的。再比如,过河卒问题正是因为卒子每一步只能向右走或者向下走,所以才以此为基础设计的转移:f[i][j]=f[i][j1]+f[i1][j]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 ;
}

0 comments

No comments so far...