SRM 501 Div 1 Easy + Medium

剛好這次SRM撞在吃飯的時間，沒打。不過題目是清一色動態規劃，則有點兒那個…

Easy: 一開始計數器 $C$ 置0。你可以做兩種操作。操作A: $C := C + P_A$ ；操作B﹕ $C := C\times P_B$ 。你只可以使用兩種操作分別為 $N_A$ 和 $N_B$ 次，操作可按任意順序，問最大值可以是多少？ 注意 $P_A$ 和 $P_B$ 皆可以是負數(不然你早就知道答案是 $C_{\max} = N_AP_AP_B^{N_B}$ )。

秒殺類動態規劃。設 $F_{\max}(i, j)$ 和 $F_{\min}(i, j)$ 為經過 $i$ 次操作A和 $j$ 次操作B之後得到的最大及最小值。除基本情況下狀態轉移方程則是

\[F_{\max}(i, j) = \max\{F_{\min}(i-1, j), F_{\max}(i-1, j), F_{\min}(i, j-1), F_{\max}(i, j-1)\}+ P_A\]
\[F_{\min}(i, j) = \min\{F_{\min}(i-1, j), F_{\max}(i-1, j), F_{\min}(i, j-1), F_{\max}(i, j-1)\}\times P_B\]


$O(N_AN_B)$ 的就是做。

另外，留意到我說全部都是正數的情況嗎？其實另有一個挺簡單的算法。
假設 $S_A = N_AP_A$ ，我們則只需取 $\max_{0 \le i \le N_B}\{S_A \times P_B^i\}$ 即可。
原因是很簡單的，我們可以真的不用乘 $P_B$ 剛好 $N_B$ 次，如果想乘剛好 $k$ 次的話，餘下的 $N_B-k$ 次則可以先在 $C = 0$ 的時候用 $N_B - k$ 次操作B抵銷掉。至於為何這種模式的操作次序為何保証答案最優，則可以考慮情況再作分析即可。

Medium: 一個 $N$ 個元素的數列 $A$ 是美麗的數列，若且僅若以下條件成立﹕

1. $A_i \le \frac{\sum_{j=1}^{i-1}A_j}{i-1}, i > 1$


2. 沒有連續三個元素使得 $A_{i-1} > A_i > A_{i+1}$


3. $0 \le A_i \le 40$

給定的數列的能帶-1。現在問，如果為這些帶-1的元素取代成0至40之間的整數，問有多少個構成的數列是美麗的數列？答案取模 $10^9+7$ 。

又是動態規劃題。今次的狀態是這樣定義的﹕ $F(i, v, d, s)$ 。 $i$ 是指當前第幾個元素， $v$ 是指當前第 $i-1$ 個元素是甚麼， $d$ 是指 $v$ 是第幾個嚴格遞降元素， $s$ 是指 $s = \sum_{j=1}^{i-1}A_j$ 。那麼可以轉移的合法狀態是甚麼呢？設能轉移的合法狀態是 $F(i+1, v', d', s')$ 。則有

1. $0 \le v' \le 40$


2. $d' = \begin{cases} 0 & \text{ if } v' \ge v \\ d+1 & \text{ otherwise } \end{cases}$ 而且 $d' \ne 2$


3. $s' = s + v'$


4. $i\times v' \le s $

只要按這些參數枚舉，則可以把所有合法的 $F(i+1, v', d', s')$ 更新成 $F(i+1, v', d', s') := F(i+1, v', d', s') + F(i, v, d, s) $ 。最底層則是 $F(0, 0, 0, 0) = 1$ 。可以根據上述的條件限制一定的枚舉範圍避免超時。答案就是 $\sum_{v, d, s} F(N, v, d, s) \bmod{10^9+7}$ 。

Codeforces #71

趕paper的關係，加上不知道三天前莫斯科時區改變了，所以沒有註冊。不過挺好的，以後CFBR都提早一小時，省得要兩三時才捨得去睡。

A: 給出長度為 $N$ 的字串 $S$ ，只有當 $N > 10$ 的時候把除首尾字元外移去並寫成其移去的長度，即 $N-2$ 。有做軟件開發的應該聽過 internationalization => i18n 這回事吧。秒殺題。

B: 一個顯示進度的顯示塊，分成 $N$ 等分。 每等份的顏色深度最多為 $K$ 。現在問進度為 $0 \le t \le 100$ 的情況下每個進度顯示塊的顏色深度是多少。設進度塊的顏色深度是 $a_1 \le a_2 \le \cdots \le a_N$ ，則必需滿足

\[\frac{\sum_i a_i}{NK} \le t < \frac{\sum_i a_i + 1}{NK}\]

只需枚舉 $\sum_{i} a_i$ 的值即可。注意別忘記該值最多可以是 $NK$ 。

C: 問在一圓形上均勻分佈 $N$ 點，每點可以是紅色或綠色，問有沒有在一綠色連成正 $K \ge 3$ 邊形。直接想法就是給定一正 $N$ 邊形結構，只能構造正 $k$ 邊形若且僅若 $k | N$ 。因此枚舉 $N$ 的因數然後直接查找有無正 $K$ 邊形即可。一個 $m | N$ 相隔的點連通可以構造成 $\frac{N}{m}$ 邊形。注意不可枚舉 $\frac{N}{m} \le 2$ 的情況(考慮 $N = 4$ )。

D: 給了 $N \times M$ 張樸克牌，當中有至多兩隻鬼牌，你可以把鬼牌任意換成輸入的樸克牌中沒有的牌，但牌沒有重複。問有否存在兩個互不重疊的 $3 \times 3$ 的正方形，每個必須覆蓋其中9張牌，使得每個正方形所覆蓋的牌中，必須保証同花或者數字互不相同。然後按題目描述輸出。

好麻煩的數據處理題。總之寫得小心點即可。留意如果只有一張J2牌不要誤輸出為J1牌，有兩張鬼牌的話需要搞清次序。

E: 題目是給了 $N$ 個整數 $A_1, \cdots A_N$ ，每個不太於100。問能否通過劃分並取和後得出另外給定的 $K$ 個整數 $B_1, \cdots B_K$ ，同樣的，每個不多於100。數據範圍是 $1 \le K \le N \le 17$ 。如果能找到解必須輸出如何劃分，為使題目變得更「有趣」，出題者把數字變成化學元素，取和就是進行核融合(這真是抽了日本一把)。

我的做法是動態規劃。記 $f_{b, k}$ ，當前劃分過的數字以一集合 $b$ 表示，並且它們都可以表達了首 $k$ 個數，而 $f_{b, k}$ 僅表示這個情況能否實現，1代表能夠，0則代表不能。轉移方程則是

\[f_{b, k} = \bigvee_{b': b' \subseteq b\text{ and }s_{b-b'}=B_k} f_{b', k-1} \]
\[f_{\emptyset, 0} = 1,\quad f_{\emptyset, k} = 0 \text{ for }k > 0\]

其中

\[s_b = \sum_{i \in b} A_i\]

可預先用 $O(n2^n)$ 動態規劃計算。
麻煩的是計算 $f_{b, k}$ 的運算量最壞可以是 $O(n2^{2n})$ 。
我用了一點優化的技巧還是過了。首先，對於 $f_{b, k}$ 的計算，只需要預計算所有 $s_{b-b'}=B_k$ 即可，無需所有集合都試一次。另外，計算 $f_{\cdot, k}$ 的時候已有哪些 $b$ 使得 $f_{b, k}$ 是可行的，假設集合 $S'$ 包含這些子集 $b$ 。下次計算 $f_{\cdot, k+1}$ 時則只需從集合 $S$ 內的子集取 $f_{b, k}$ 計算即可。通過這種優化則可以在最遲2.5秒左右跑完數據。

Codeforces #70 C Lucky Tickets

題意﹕若有一對數 $(p, q)$ 使得 $p\times q = \hat{p} \times \hat{q}$ ，當中 $\hat{x}$ 是指把 $x$ 的十進制倒置並消去前導零，我們則稱 $(p, q)$ 為幸運對。給定 $X_{\max}, Y_{\max}$ ，求一 $x, y$ 對使得對於任意 $1 \le i \le x,\quad 1 \le j \le y$ ， $(i, j)$ 是幸運對的數量至少為 $w$ 。求最小的 $x\times y$ 使得條件成立。

首先需要注意的是若 $(p, q)$ 是一幸運對的話，則有如下公式


\[\frac{p}{\hat{p}} = \frac{\hat{q}}{q}\]


另，只要任意 $p'$ 使得 $\dfrac{p}{\hat{p}} = \dfrac{p'}{\hat{p'}}$ ，則 $(p', q)$ 也是幸運對。因此我們先要留意把 $\dfrac{p}{\hat{p}}$ 化至最簡。設 $\acute{p}$ 和 $\grave{q}$ 為 $\dfrac{p}{\hat{p}}$ 和 $\dfrac{\hat{q}}{q}$ 的最簡化分數，若 $C_{\acute{p}}$ 和 $D_{\grave{q}}$ 分別包含所有 $i$ 使得 $\acute{i} = \acute{p}$ 和 $j$ 使得 $\grave{j} = \grave{q}$ ，則對於任意的 $i \in C_{\acute{p}}$ 和 $j\in D_{\grave{q}}$ ， $(i, j)$ 必為幸運對，而且一共有 $|C_{\acute{p}}||D_{\grave{q}}|$ 個。

因此先計算所有 $|C_x|$ 的值。這個可以在 $O(X_{\max}\log X_{\max})$ 時間內完成。然後先從 $x = X_{\max}, y=1$ 開始，在不斷減少 $x$ 的同時，提升 $y$ 使得總幸運對至少為 $w$ 。留意每增加一次 $y$ ，便會相應增加了 $|C_{\grave{y}}|$ 組幸運對。並且同一時間統計 $D_{\grave{y}}$ 。當再增加 $|C_{\grave{y}}|$ 組幸運對時超過了 $w$ 則停止統計，並更新答案。這個時候已知再增加 $y$ 不會令答案變得更好，因此可以考慮減少 $x$ 。但減少了 $x$ 將會對原本計算現有多少組幸運對有影響。 $x$ 自身可以和 $|D_{\acute{x}}|$ 個數組成幸運對，因此當 $x$ 減少了一的時候，相應的幸運對的數量須減少$|D_{\acute{x}}|$ ，同時為 $C_{\acute{x}}$ 移去 $x$ 。

這個算法可以在 $O((X_{\max} + Y_{\max})(\log X_{\max}Y_{\max}))$ 時間內完成。

Codeforces #54 D Writing a Song

題意﹕給定 $N$ 和 $K$ ，現在有一長度為 $L_P$ 的字串 $P$ 和一長度為 $N - L_P + 1$ 的01字串 $B$ ，並依 $B$ 構造一長度為 $N$ 的字串 $R$ 。若 $B_i$ 為1，則子字串 $R_{i\cdots i+L_P-1}$ 必須要等於字串 $P$ 。若 $B_i$ 為0則該子字串必須不能等於 $P$ 。另，只能使用首 $K$ 個小寫英文字母。問能否存在此字串並輸出答案。

顯然易見的是某些位置該於甚麼字元是固定的。先把那些地方寫好固定的字元。然後檢測有否沖突。如果有衝突的話則必無解。

但，如無衝突的話，可能存在未固定字元的位置，那麼該放甚麼呢？首先理解的是不能亂放。可以參考題中第二樣例。
如果允許字元只有 $\{a, b\}$ 而且 $P = a$ 、 $B = \underbrace{10\cdots 01}_{N-2\text{ zeros}}$ 。那麼除固定首尾為a之外，其餘位置必須放置b。如果隨機放的話，只有 $\frac{1}{2^{N-2}}$ 機會判斷正確。那麼，當 $N$ 很大的時候幾乎沒有可能找到正確(且唯一的)解。那麼是不是代表亂放不奏效？又未必！

其實大可以想想以下一個有可能錯的算法﹕對於未固定位置，枚舉可放置的字元，找到第一個能放的字元又不引起衝突即可。這個算法，相信大家很快找到反例﹕某一個位置首先找到的字元，可能會令往後的任意放置變成無解。於是，先放置甚麼字元就顯得比較重要了。來到這裡，可以問一個問題了﹕能不能應用隨機算法？似乎可行。每次枚舉未固定位置前，先為可用字元隨機取一排列 $\sigma$ ，然後按 $\sigma$ 的順序嘗試。把這個過程重複 $T$ 次，估計誤判沒有解的機會很小。我的算法甚至取 $T = 1$ 都可以安然通過。

至於為甚麼能找到解的機會很高？這個我沒法証明…

另，正確的解法是動態規劃。

Codeforces #23 C Oranges and Apples

題意﹕給了$2N-1$個箱子，每個箱子分別載有 $A_i$ 和 $O_i$ 個蘋果和橙。要求選出 $N$ 個箱子使得蘋果和橙的總數至少為總數的一半。 $A_i, O_i \ge 0$ 。

設蘋果和橙的總數為 $A$ 和 $O$。換句話說，就是求一集合 $\mathcal{I}\subseteq \{1\cdots 2N-1\},\, |\mathcal{I}| = N$ 使得

\[\sum_{i\in\mathcal{I}}A_i \ge \frac{A}{2},\quad \sum_{i\in\mathcal{I}}O_i \ge \frac{O}{2}\]

我的做法比較不確定，就是任意隨機取一排列 $\sigma$ 使得首 $N$ 個箱子符合條件。

正確的做法應該是這樣。不失一般性下假設

$A_1 \le A_2 \cdots \le A_{2N-1}$

把奇數項設為 $Q$ ，偶數項設為 $P$ ，則有

$Q_1 \le P_1 \le Q_2 \le P_2 \cdots P_{N-1} \le Q_N $

定理 1﹕ $\sum_i Q_i \ge \frac{A}{2}, \sum_i P_i + Q_N \ge \frac{A}{2}$ 。

對於 $ 1 \le i \le N-1$ , 皆有 $Q_{i+1} - P_i \ge 0$ 。因此 $Q_1+\sum_{i=1}^{N-1}Q_{i+1}-P_i \ge 0$ ，故 $\sum_i Q_i$ 至少為 $A$ 的一半。

另外，對於 $ 1 \le i \le N-1$ 則有 $P_i-Q_i \ge 0$ 。因此 $Q_N+\sum_{i=1}^{N-1}P_i-Q_i \ge 0$ ，故 $Q_N + \sum_i P_i$ 至少為 $A$ 的一半。

因此，把箱子依數量排序則有兩種取法使得其蘋果數的總和至少為 $A$ 的一半，而且它們皆取了第 $2N-1$ 個箱子。那麼這兩種取法的橙的數量分別有 $X = \sum_{i=1}^{N} O_{2i-1}$ 和 $Y = \sum_{i=1}^{N-1} O_{2i}+O_{2N-1}$ 。

設 $Z = Y - O_{2N-1}$ 。因為 $X + Z = O$ 。若 $X < \frac{O}{2}$ 則有 $Z \ge \frac{O}{2}$ ，反之亦然。而 $Y \ge Z$ ，因此在結論中可把 $Z$ 替換成 $Y$ 。因此按這個方法去選取箱子則保証答案永遠存在。

Codeforces #69

題目不太難，只是有些題目比較難讀懂，遲開始了，最後得分比較低。

A: 在三維空間的原點上有一物件。應用了次矢量為的力後，問最終物件是否原地不動。
答案﹕檢查 $\sum_i\vec{F_i} = \vec{0}$ 即可。

B: 一條長度為的跑道上有個section。每個跑手會在個section進行賽跑。假設個section每次賽跑都是分開進行的，若在某section裡下注了第跑手贏出而真的贏出的話，則得到元。每人每section賽跑時間都是。不能在沒人跑的賽道中下注，不能在沒有某參賽者不賽跑的section向其下注，問最多可以贏到多少錢？

好煩的題目。但只是直接枚舉每個section，在有人跑的回報裡取最大值，然後總和就是答案。

C: 給了種神器的原材料名稱，和種神器所需要的原材料及其數量。現在有個玩家和次採購。每次採購皆說明是哪位玩家買了甚麼原材料。
保証每次採購後只會有最多一種合作神器可以作成，問最後每人手上每種神器的數量，和有多少種神器。

直接就是做，比賽時沒過是因為我以為輸出的是玩家名稱，而不是神器的數量…

D: 在某座標上放了一隻棋子。兩個玩家輪流玩遊戲。每次可選取個之中的一個矢量然後加到該棋子上，保証矢量非零並且數值非負。除移動外，另可以選擇應用反射，即，但每位玩家只能在遊戲中應用一次。玩家不能把棋子移離原點距離以外。問若兩個玩家皆采取最佳策略，問誰會勝出。

經典的動態規劃題。但可以留意反射是沒有作用的，因為對方可以再應用一次反射抵銷。
另可以用SG定理，注意需處理SG函數為0的位置。

E: 給定一數組和，詢問對於，之間出現僅一次的元素的最大值，不存在的話則輸出"Nothing"。

直接的單調隊列題。大部分選手都用STL的set，我則用了Priority Queue來做，幸好沒有超時。主要做法是當需要處理新的元素時，把最舊的元素統計減1，然後把新元素的統計加1，若是新出現的元素則放到隊列內。每次輸出時把第一個隊列置頂的元素輸出，且其需要符合統計數為1。若不合資格則把它移除。

Codeforces #68

比賽題目較為簡單，但是仍然表現得不夠好。

A: 問給了4個互相不同的數，給了範圍，問當中有多少個數，使得在至少7種的不同排列中，該數在取模的順序下仍然保持不變。看了之後都不用懷疑，直接就暴搞了。但留意一下取模順序本來就是符合交換性的，即，因此只需對一種排列(例如輸入中的排列)下試了所有數看看是否在取模順序下不變即可。省卻了24!的排列。
然而，本題有的算法。假設，可知保持取模下不變的數只能在，即，其餘取模是多餘的。因此答案即是。

B: 給定個整數，定義操作，使得操作後。給定，問經過若干次操作後，能使得的話，它們的數值最多為多少。

直接的想法就是二分答案。設為經過若干次操作後最終每個數的一致值，定義



不難看出是總供給量，是總需求量。若則表示經過若干次操作後所有數皆等於。若則表示供過於求，即太低；若則表示供不應求，即太高。應用二分法求最大的使得供求相符即可。

C: 給了一個有向無環圖，最多6個頂點，而且是完全圖。每條邊有要求流量最少最多值，和啟動值。設在邊流量是，啟動值，則費用是。求一個可行的網絡流，源是點1，匯是點，需要符合上下限，要求流量最小，其次則要求費用最大。上下限最多是5，啟動費用最多是6。若沒有流量則毋需計算啟動費用。

明顯地數據範圍極小，可以考慮暴試。設為第點的注入量。對源點則有。DFS狀態為，當中。此程序會嘗試從點抽取之間的注入量，加到之中，然後按情況嘗試。當達到即可中止。但嘗試量最多是，肯定會超時。要應用一些prunning技巧。首先，當在狀態的時候，若已經大於最小流量值則中止嘗試。另，嘗試的時候，應直接取走其注入量，並留意是否，若否則中止搜索。

D: 待補。