某島

… : "…アッカリ~ン . .. . " .. .
September 19, 2012

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