栗子栗子

2017南京大学计算机开放日机试题解

A

题目大意

给定一棵n层的满二叉树,不存在的节点用-1表示,同时给定一个sum,问从根到叶子节点有哪些路径,使得点权和为sum。多条路径从左向右输出。

做法

DFS即可,或者层序BFS,但需要注意重新排序。

B

题目大意

给你n个非负整数,每个数表示从当前这个数可以跳跃的最远距离,一开始你在最左边的点,问是否能跳到最右边的点。

做法

考虑维护当前能跳到的最右端点r,用能跳到的范围内的a[i]+i与r取最大值更新即可,初始r=a[1]+1。

C

题目大意

给定你IF,THEN,ELSE,BEGIN,END构成的一组语句,问你该组语句是否合法。

做法

简单判断包括IF和THEN一定要相邻且成对出现。

难点在于BEGIN和END,以及ELSE的情况。

我们可以维护一个栈,用来表示当前的嵌套关系。

需要注意的是最后可以把所有的IF和THEN弹出,但仍然需要判断是否有BEGIN剩余。