應該算是比較簡單的 Div 2 的 Round
P.S. 一直寫下去後發現變成我在抱怨題目太簡單 XD
CF 293 Editorial 連結
Problem A --- Vitaly and Strings
題意：給兩個同長度的字串 $s$ 和 $t$ ，已知 $s$ 字典序小於 $t$，請給出一個長度和 $s$ 一樣的字串且字典序大於 $s$ 且字典序小於 $t$，無解請輸出 No such String。
數據範圍：小小的
tag：[ 字典序 ]
= = = = = = = = = = = = = = = = = = = =
這題比我想像的還要多人寫假解，我寫完第三題後才看 score board 觀察有沒有題目可以 hack，並發現這題非常多人被 hack，但是我這個 room 已經被 hack 光了。
我看到有一個人用python寫，直接把 s 和 t 轉成 26 進位的整數，再看看是否為相鄰兩個整數來判斷有沒有解 XD 若題目變成給兩個整數問他們之間有沒有整數應該是國小程度的東西？
Problem B --- Tanya and Postcard
題意：給兩個由大小寫字母構成的字串 $s$ 和 $t$，$t$ 的長度 $\geq s$。請從 $t$ 中取出一些字母重新排列組合成和 $s$ 長度一樣的字串，使得 1. 相同字母且相同大小寫的位置盡可能多 2. 若前者一樣多，再使相同字母但大小寫可以不同的位置盡量多。只要輸出兩種情況相同的字母數即可。
數據範圍：字串長度不超過 $2*10^5$
tag : [ greedy ]
= = = = = = = = = = = = = = = = = = = =
直覺想法就是有完全一樣的字母就先擺上去，都擺完後，再繼續把大小寫不一樣的相同字母擺上去，剩下的就隨便亂擺。很巧的這一定是對的。
Problem C --- Anya and Smartphone
題意：有個手機有 $n$ 個 icon，每個 page 有 $k$ 個 icon，若要使用第 $x$ page 的 icon，就必須滑 $x$ 次，每次滑完後，該 icon 的位置就會和位置在他前面的相鄰 icon 互換 (若沒有比他此 icon 則位置維持原樣)，給原本所有 icon 的位置，以及一序列的操作，問總工必須滑幾次？
數據範圍：所有數字不超過 $10^5$
tag：[ 模擬 ]
= = = = = = = = = = = = = = = = = = = =
我非常懷疑這題放在第三題只是因為他比較難讀懂 ...？有沒有人可以告訴我這題的特別要注意的地方在哪，有哪裡可以想歪？還是說交換位置的實作對初學者來說可能有困難？(嗯...若是第一次使用陣列大概有困難吧？)
Problem D --- Ilya and Escalator
題意：有 $n$ 個人在排隊等電梯，每一秒有 $p$ 的機率有一個人進去，另外 $1-p$ 的機率會沒有動靜，問 $t$ 秒後進去電梯裡的人數的期望值？(電梯容量無限大，進去的人就永遠在裡面)
數據範圍：$1 \leq n, t \leq 2,000$， $0 \leq p \leq 1$
tag：[ DP ]
= = = = = = = = = = = = = = = = = = = =
DP狀態很直覺，現在經過幾秒以及進去了多少人，轉移就如題目所述只有兩種。這提竟然值兩千分 =口=，我覺得是 rating 爆漲的現在，使得 Div. 2 的難度變更低了...?
Problem E --- Arthur and Questions
題意：給 $n$ 個數的數列，有些數尚未決定，用問號來表示，現在要把問號都填入數字，使得每連續 $k$ 個數的和所形成的數列為嚴格遞增數列，並且所有數的絕對值總和最小，要輸出解，若多組解，輸出任一組皆可。
數據範圍：$1 \leq k \leq n \leq 10^5$
tag：[ 數學 ] [ greedy ]
= = = = = = = = = = = = = = = = = = = =
把不等式列出來就會發現，嚴格數列的那個條件其實等價於，在原數列中取出任意間隔恰為 $k$ 的子數列，也都為嚴格遞增。把每個子序列分開作後，我們就把問題簡化為：給一個有些位置值還位給定的數列，請給定值使得絕對值總和最小，至於要怎麼給值呢？愈靠近零總是愈好吧？剩下的就是從貪心的角度切入加上一點點數學證明了。
Problem F --- Pasha and Pipe
題意：給一個 $n * m$的盤面，要在上面放一條至多轉兩次九十度的管子，並且不能碰到某些格子(詳細條件請看原題)，問有多少種可能
數據範圍：$1 \leq n, m \leq 2,000$
tag：[ dp ]
= = = = = = = = = = = = = = = = = = = =
我讀完題目的直覺就是不轉彎，轉一次彎，轉兩次彎這三種情況分開討論。其中只有轉兩次彎的情況要稍為複雜一點點的 dp (但其實也只是很常見的手法)。
雖然這樣說 ...，但轉兩次彎的情況我寫爆了 XD。把他想的太簡單了，沒有去考慮轉兩次彎的中間那部分有沒有通過不可以走個格子 ...
沒有留言:
張貼留言