作者的 short editorial
250 --- RobotOnMoon
題意：有一個 $n * m$ 地圖，有些格子被障礙物擋住了，有一個機器人並給你他初始位置，你可以設計一些指令讓他行走，若指令叫他往某個方向走，那個方向卻被障礙物擋住，那機器人不會移動。若執行那個指令會走出地圖外，那他就走出地圖外了 0.0 這機器人壞壞的，所以每個指令他都有可能會不小心 miss，現在我們要設計最長的上下左右的指令讓機器人無論 miss 了任何 subsequence 都一定不會走出地圖外。
數據範圍：小小的
tag : [ adhoc ]
- - - - - - - - - - - - - - -
看完題目後立刻想到若上下左右的某個方向直直走會被擋住，那就可以設計一個無限長的那個方向的指令。並且很容易相信這是僅有的答案為 -1 的 case，至於答案不是 -1 的 case 嘛...，其實我最剛開始猜的是上下左右最長的長度，可是看了一下 Sample，發現所有 Sample 都會對而且都是以這個做法來說很極端的 case... (要碼答案是 -1 要碼四個方向長度非 0 的只有至多一個方向)。就覺得答案一定不是這樣，在花幾秒後就想到正解而且發現可以輕易證明它了。不過說真的 ...這種題目若測資太強就太容易猜答案結果就不好玩了 XD
500 --- FoxConnection3
題意：平面座標上有 $n$ 個點，要上下左右移動它們，使得它們變為連通，並且這 $n$ 個點的移動步數和最小。每次移動都只能上下左右選其一移動一格，並且 always 不能有兩個點重疊。
數據範圍： $n \leq 6$，座標絕對值不超過 $10^9$。
tag：[ 枚舉 ] [ 數學 ]
- - - - - - - - - - - - - - -
類似題其實蠻常見的，最常見的就是在一維空間上做同樣的事，二維空間的類題我也立刻想到一題 HOJ84。不能重疊的什麼根本不用管這個條件，我以前思考過類似的事情了。最後再看到 $n$ 最大只有 $6$。顯然可以暴力枚舉所有連通圖的點塊的樣子。所以說這題我讀完題目瞬間就知道這麼做了，只是 code 似乎不夠好寫就是了。但 Petr 好厲害寫好快 0.0 到底怎麼辦到的 ...
1100 --- FoxAndSouvenir
題意：有 $n * m$ 的矩陣，有些位置有值有些沒有，有 $q$ 組詢問，第 $i$ 個詢問給你一個矩形，問你這個矩形內有幾種選數值的方法使得這些數值的總和為 $v_i$，答案 mod $10^9 + 9$。
數據範圍： $1 \leq n, m \leq 50$, 矩陣內數值總和 $\leq 2500$。
tag：[ 傅立葉 ]
- - - - - - - - - - - - - - -
SRM 久違的傅立葉題...，但這題我看完第一個想到的是這題：Good Bye 2014 --- New Year Shopping，把它變成 2D版，所以我就一直往 D & Q 加 根號類算法下去想了 ...然後還自以為想到但後來發現某個地方複雜度搞錯了。
其實我應該要特別注意到 $10^9 + 9$ 這個數字的，向來當題目不 mod $10^9 + 7$，而是 mod $10^9 + 9$，通常都有特殊用意，所以看到這個數字就可以先往很數學的方向想少陷入些坑坑洞洞，不過我對傅立葉還不熟就是了，過高級的應用不太可能在一兩個小時內想到...。
- - - - - - - - - - - - - - -
下一場 SRM 要等到 3/9 了 ...，不要一直壞掉啦 OAQ
沒有留言:
張貼留言