某島

… : "…アッカリ~ン . .. . " .. .
June 30, 2012

Codeforces Round #127

Brief description:

Problem A. Clear Symmetry
。。一個 01 矩陣被稱之為:
Clear: 如果沒有 1 相鄰。
Symmetrical: 如果在 旋轉90度 的作用下不變。
要求在滿足上述性質的情況下,構造一個階數最少的有 x 個 1 的 01 矩陣,求這個階數。

Problem B. Guess That Car!
給定一個 N×M 的格點,每個點有一個全值 Aij,當人站在某個交點位置時將對每個格點產生一個代價。
定義為 Aij 乘以距離的平方。問站在哪個位置時,所有格子產生的代價最少。

Problem C. Fragile Bridges
給定一排要石,要石與要石之間有一座橋,每個橋有一個耐久度 Ai,當往到達 Ai 次的時候,
橋會坍塌,問能移動的最長步數。(可從任意位置開始。。

Problem D. Brand New Problem
給定 n 和一個長度為 l 的數組,構造一個大小為 n 的子序列,使得其構成 1, n 的一個重排,且逆序數儘可能小。
( n ≤ 15, l ≤ 500000 .. .)

Problem E. Thoroughly Bureaucratic Organization
已知有一個長度為 n 排列,但不知道每個位置分別是多少,每次詢問可以確定其中至多 m 個槽位有哪些數。。
(但不能確定具體的位置)。。問最少多少次詢問可以還原之。。。

Analysis:

Problem A. Clear Symmetry
。。。首先觀察注意到偶數情況下 bug (還沒有較小一階的奇數優。。
…然後製作 int r(x); 表示階數為 x 的時候最多能產生多少個 1 。
。。。然後稍微構造一下發現比這個數小情況都是可以構造出來的。。(除了 3 階,特判一下就交了。。

Problem B. Guess That Car!
考慮到公式是可以對 x 軸和 y 軸分離的。。於是 O(n) 拖出來做兩次預處理即可。。

Problem C. Fragile Bridges
。。SB 動態規劃,定義左右兩邊以及能否返回四個狀態。。。
(參見。。。http://acm.uestc.edu.cn/problem.php?pid=1649

Problem D. Brand New Problem
定義 dp[s][i] 表示使用的數字集合為 s, 逆序數為 i 時,在文本中所處的位置。。(。最左邊那個。。
。然後製作輔助數組 p[i]][j] 表示第 i 個位置開始出現 j 的最靠左的位置。。就能轉移了。。╮(╯_╰)╭

Problem E. Thoroughly Bureaucratic Organization
對於任意兩個數 i, j, 為了區分兩個數字的位置。。
則至少存在一組詢問只包含 i 或只包含 j 。。。。

於是問題等價於 SRM 484 的 1000 。。。

(對於每次不必用填滿 m 個數的問題。。發現對問題不構成太大影響。只是再 m > n / 2 時,取 m = n / 2 即可。。。

Code:

A B C D E

External link:

http://codeforces.com/contest/201/room/5