Codeforces #68

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

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

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

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



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

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

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

D: 待補。

SRM 499 Div 1 Easy + Medium

又一場不太難的srm呢…或許是srm 500暴風雨的前夕。沒做，其後問GG題目，的確很快想出算法，practice room passed。

250: 給了N個兔子的詢問，代表有多少兔子跟牠同一顏色，假設牠們都是說真話，求最少有多少隻兔子。

不難留意，一個詢問若得出K的話，那麼至少有K+1隻兔子。至於要得出最少答案，不難想象貪心地把最多K個兔子，其詢問都是K的「同化」一下。數式地表示就是求所有(C[K]+K)/(K+1) * (K+1)的和，當中C[K]是指有多少隻兔子的詢問是K。

550: 給了最初空的文件，你可以做以下操作。
1) 找一行插入空格。
2) 找一非空行按下Delete
3) 找一行按下Enter。此時該行會變成兩行且擁有相同的空格數量。

給定最終N行要求的空格數，求最少要多少操作。

留意三個操作疑可看作﹕1) 找一個元素+1 2)找一個元素-1 3)找一個元素分裂成兩個且保持元素數值不變

最直觀的想法就是想用類似最小生成樹的概念去「生成」要求的文件。即每次都找一個最小元素，然後按其最接近已生成的元素求最小的費用(分裂+增加)，並加入生成集之中。由此不難看出是貪心且操作2)好像沒甚麼用…而且比較難証明貪心是正確的。因此很快會想到N^3的動態規劃。假定要生成第x~y的元素，那麼就是取其中一個元素來生成，假設是x<=i<=y，然後問生成 x~i-1 和 y~i+1之間的元素最少費用是多少，然後在所有i之間取最少值。
有趣的是，細看這道題的提交，有不同的動態規劃。Petr等高手用的應該是N^4動態規劃，我想這個model是出題者本來預期的答案吧？還有N^3、N^2和種種不同的貪心。最神奇的是三行的代碼﹕

int res = lines[0] + (int)lines.size()-1;
REP(i, N-1) res += max(0, lines[i+1]-line[i]);
return res;

這種貪心，有趣得很。大意就是從左到右以lines[0]為首的連續上升元素，才需要增加用以操作1)的費用，其餘的一律不用。對的原因，我大概想的是，這個序列覆蓋了所有比它小的離散序列的增長費用，因此可以生成這個序列旳時候「順便」生成其他離散的小序列，額外費用只需要憑3)的操作，因此res最初被加上憑3)分裂成其餘N-1個元素的費用。

--
最近兩次SRM題目都很不錯，雖然550是否值得還是很有爭議，但我覺得直覺和經驗相比，總是比較難判斷。

Codeforces #25 E Test

題意﹕給了三個字串，求最短能包含所有字串的長度。

做法﹕暴力枚舉，每次融合一個新字串的時候，考慮三件事。

1) 相互包含。KMP檢測。
2) 字串A前置字串B。A的後綴可以與B的前綴重叠。檢測重叠的方法也是KMP，構造B$A的失敗函數，取其函數最後位的數值即表示前後綴重叠長度。
3) 字串B前置字串A。做法與(2)一致。

需要cut case。即如現在融合字串長度超於最佳長度則中斷枚舉。

Codeforces #17 D Notepad

題意﹕求。
看似簡單，但。普通的Repeated Squaring完全不行。
看了一下rng_58的代碼，發覺有一個除了用中國餘式定理以外的做法。

留意﹕若，則有。因此可以用Honor's Rule來算答案。

另，把也是必須的，這步也可以用Honor's Rule來算。

假設，則有，，然後根據這個轉移方程算出，若答案為0則直接輸出。

對於用字串的來算，則找出從最右邊的數位第一個不是0的數位，把它減一，然後把其後的數位取代成9即可。