Codeforces Round #138

这场 D、E 都没人能出。。。
D:。。欧几里得空间中给定一个一般多边形,支持两种移动方式。(沿着多边形的边或者垂直降落。。问多边形墒两点之间的最短距离(。。 E: 给定一副。边点连通度均 > 1 的平面图。每次询问一个圈。。问有哪些点在这个圈内部。。

Brief description:

A. Bracket Sequence
给定一组由 “()[]” 组成的括号序列,求含 ‘[‘ 最多的一个合法子序列。
(用栈扫描一遍得到与每个右括号唯一匹配的左括号位置,用这个信息做动态规划

B. Two Strings
给定串 s 和串 t。。问是否 s 串的每一个位置的字符。。
都可以在一个匹配 t 串的子序列之中。
(对 s 串的每个位置 si,记录其左起和右起分别能在 t 串中匹配到的最远位置,要使如果该位置合法,
则必须有这个区间含有交集,之后在看在 t 串中这个交集所在区间中是否包含有 si

C. Partial Sums
经典问题,求 k 阶 Partial Sums。
(组合数。。。

External link:

http://www.codeforces.com/contest/223