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 個槽位有哪些數。。
(但不能確定具體的位置)。。問最少多少次詢問可以還原之。。。

ゆっくり読んでください …

【套題】GSS 系列

Brief description:

序列 a 的 l, r 之間的最大子段和 (Maximum subsequence sum) 定義為:
Query(l, r) = Max {a[i]+a[i+1]+…+a[j] ; l ≤ i ≤ j ≤ r}.

GSS 系列是 SPOj 上的一組數據結構習題,一共 6 題,大部分是和最大欄位和有關。

GSS1: 只有詢問。GSS3:單點修改。
GSS5: 詢問時,限定區間兩端點 i, j 的取值範圍。
GSS2、GSS4:相對的獨立問題。。
GSS6: 加入插入和刪除操作。
GSS7: 樹上 GSS 問題。

ゆっくり読んでください …

SRM 547

Brief description:

Problem 250. Pillars
。。要在兩面牆之間架一個梯子,兩面牆高度皆為整數,均勻選自 [1, A] 和 [1, B] 之間。
。中間距離為 w,問梯子期望的長度。
(。。1 ≤ A, B ≤ 100, 000 。。。)

Problem 500. RectangularSum
給定一個逐行逐列依次填 {0, 1, 2, 3, 4, … nm-1} 的 n × m 矩陣。。
。。。問所有和等於 S 的子矩陣中,面積最小的是多少。
(。。1 ≤ n, m ≤ 100, 000 。。。1 ≤ S ≤ 100, 000, 000, 000。。。)

Problem 1000. MaximalTriangle
問正 n 邊形的三角剖分中,有多少種剖分是可以產生一個面積最大的大三角形的。
(。。3 ≤ n ≤ 444 。。。)
ゆっくり読んでください …

Codeforces Round #125

Brief description:

Problem A. About Bacteria
… 培養皿中的 x 只細菌下一秒會繁衍出 kx+b 只細菌。。(。。。
問如果初始培養皿中有 t 只細菌,至少多少秒才可以繁衍出不少於 z 只細菌。
。。。z 為初始為一隻細菌時,繁衍 n 秒的細菌總數。。。(。。。
(略,算術題。。不要把 z 真給算出來即可。。

Problem B. Jumping on Walls
一個忍者在一個坑裡, 左右各有一面牆,牆上有一些障礙,初始在最下角。
每秒鐘可以上下移動一格,或者跳到對面牆的恰好 +k 位置。。
。。問最終能出跳出這個坑。。
(略, Hash Dp 或者 BFS() 都行。。。。

Problem C. Delivering Carcinogen
給定一顆行星坐標 (xp, yp),軌道半徑 R,圍繞恆心運轉的線速度 vp,
以及一個飛船坐標 (x, y),飛船速度 v。。問到達 p 星球的最少時間。。
。。飛船運行過程中距恆星的距離不得低於 r。。(r ≤ R) …

Problem D. Cube Snake
給定一個 n 階立方體,要求構造滿足下列性質的路徑:
對任意的 k < n, 存在至少 2 個 k 階子立方體, 滿足其中的數字取自一段連續區間。 Problem E. Gripping Story 空間中有一堆吸盤。 。。每個吸盤用 (xi, yi, mi, pi, ri) 表示。。。 。。自身坐標,重量。。。能抓起來的最大物品的重量,以及作用範圍。。。。 。。現給定飛船初始坐標。。(x0, y0)。。初始吸盤(p0, r0)... 問最多可以收集多少個吸盤。。。 (。。一旦得到一個吸盤以後以後就可以無限更換使用。。 (。。。注意注意飛船本身不動不動不動!。。並且吸盤吸到飛船里才能使用。。。OOrz。。 ゆっくり読んでください …