Retrospect only, some algorithms may be wrong...
Warning : 劇透慎入...
Andrew Stankevich's Contest #1
Chinese Girls' Amusement
推結(jié)論直接算
Reactor Cooling
有上下界的環(huán)形流
New Year Bonus Grant
經(jīng)典的樹形DP
Matrix Multiplication
化簡一下推結(jié)論
Nice Patterns Strike Back (Recommend)
狀態(tài)壓縮DP后用matrix來優(yōu)化，或者用上次monthly時(shí)LK的方法。
Get Out! (Recommend)
可以用那個(gè)生成環(huán)的基的DFS,類似japan那道題。
Beautiful People
最長蝦米序列，8過稍微有個(gè)細(xì)節(jié)要想
Cracking' RSA (Recommend)
求bool方程組的解數(shù)。。。也就是求下自由變量個(gè)數(shù)
Andrew Stankevich's Contest #2
Non Absorbing DFA
記得是個(gè)很正常的DP。
The Towers of Hanoi Revisited
經(jīng)典的n個(gè)塔的hanoi，記得要DP...
Hyperhuffman
就是huffman問題吧，已經(jīng)排好序，可以O(shè)(n)的。
Little Jumper (Recommend)
不錯(cuò)的物理題
首先可以想象成兩只青蛙一起從兩邊跳。
主要問題就是計(jì)算給定一個(gè)v后的青蛙可達(dá)區(qū)間。
取到最值只有3種情況：從上面擦過，從下面擦過，45度起跳（如果可以）
Quantization Problem
又是一個(gè)正常的DP...
Roads
經(jīng)典問題了。
生成樹上的權(quán)值必定是減少，其他邊上的權(quán)值必定增大，設(shè)其分別為ai, bj
然后對任意一條不在生成樹上的邊，加入到生成樹上形成一個(gè)環(huán)，然后這條邊的權(quán)值應(yīng)當(dāng)>=環(huán)上所有邊的權(quán)值。
然后我們可以列出一堆形如ai + bj >= 一個(gè)正數(shù)的不等式。。。然后。。。km算法的標(biāo)頂~~~
詳情可以看km算法的證明~~~
Robbers
首先令k[i] = m * x[i] / y，取下整，然后可能k[i]的和不到m，要增加一些k[i]，當(dāng)然是，每次找增大后delta最小的~~~
主要是，似乎可以用heap優(yōu)化為O(nlogn)。。。
Toral Tickets (Recommended)
比較神奇的Polya
Andrew Stankevich's Contest #3
Areas (Recommended)
我的做法是基于半平面交的，對每條直線，枚舉使用它左邊的半平面還是右邊的半平面，最后如果是一個(gè)有限平面則返回。。。
注意搜索過程中當(dāng)半平面被切空后就可以return，由于最后只有O(n^2)塊，所以復(fù)雜度是O(n^4)的（使用O(n^2)的半平面交）
SGU上時(shí)限很寬，ZJU上這么做時(shí)間有點(diǎn)緊（我0.95s AC的-_-bbbbbbb）
Beloved Sons
按偏愛程度從大到小找增廣路跑max_match就可以了。。。
Strange Counter
構(gòu)造
維護(hù)這么一個(gè)性質(zhì)兩個(gè)2之間至少有一個(gè)0。。。然后。。。討論。。。
Data Transmission (In List)
據(jù)說是預(yù)流 + 使勁優(yōu)化...(by Lunarmony)
Strong Defence
嗯，首先顏色數(shù)不會(huì)超過任何一條路的長度是把。。。所以顏色數(shù)至多就是最短路的長度。
然后我們跑dijstra的時(shí)候把邊著上顏色就是了。。。
Weird Dissimilarity
經(jīng)典的DP
PL/Cool
據(jù)說是模擬(from oibh)。。。
Royal Federation (In List)
據(jù)說是構(gòu)造, not AC yet.
Two Cylinders
寫出積分式后romberg.
Andrew Stankevich's Contest #4
The Smart Bomb
簡單的推一下。
I Just Called ...
模擬，要用Trie樹。
Order-Preserving Codes
模仿huffman那樣，只是每次merge相鄰的。
More Divisors
經(jīng)典的DP, f[i][j]用前i個(gè)素?cái)?shù)得到j(luò)個(gè)約數(shù)的最小數(shù)。。。
Long Dominoes
狀態(tài)壓縮DP
The Magic Wheel
應(yīng)該選擇第一個(gè)點(diǎn)，然后尋找下一層的兩個(gè)方向最近的都試一下就行了。O(N)
Cracking SSH
DP...
Periodic Tilings
好像某年final有類似的題。應(yīng)該有結(jié)論的說。
Not AC yet
Trade (In List)
Not AC yet, 可以看看
Counting Triangulations (Recommended)
一道還算不錯(cuò)的DP題，8過題目描述好像有點(diǎn)不清我記得。
Unfair Contest
搜索+模擬
Andrew Stankevich's Contest #5
Unique Attack (Recommended)
判斷最小割是否唯一的題，就是用兩種方法構(gòu)造是否一樣。
Burning Bridges
ms是很經(jīng)典的用橋來作的題
Circles
經(jīng)典的平面圖歐拉公式題
Linear Programming Dual
好象是線性規(guī)劃，Not AC yet
DVD (In List)
相當(dāng)容易寫錯(cuò)的DP題。
Think Positive
記得可以O(shè)(n)掃描的。
Ranking
麻煩的模擬題。
Driving Straight
也是很經(jīng)典的思路了，先DP(或曰BFS)。然后走一遍，在滿足有解的前提下盡量往那個(gè)方向走。
Andrew Stankevich's Contest #6
Ackerman's Function (Recommended)
可以認(rèn)為是找規(guī)律
The Minimal Angle
記得要O(n)，取平均數(shù)還是什么都可以。
Yellow Code
我記得還是比較容易YY一個(gè)構(gòu)造的。。。
Yet Another Digit
DP吧。
Graduated Lexicographical Ordering (In List)
類似于vietnam的那道題。。。相當(dāng)麻煩。。。建議實(shí)現(xiàn)下。。。
GSM
高精度開方題。或者打表～
Warehouse Keeper (In List)
KM,8過我記得容易T?
Don't Go Left
記得又是一個(gè)狀態(tài)機(jī)的BFS題
Railroad Sort
很有意思的構(gòu)造，大體思路是每經(jīng)過一個(gè)station，留住后一半，放行前一半。。。n個(gè)正好給2^n個(gè)數(shù)排序。
Andrew Stankevich's Contest #7
Little Brackets
經(jīng)典的dp, NOI隕石的秘密簡化版。。。
f[n][k] = n對括號(hào)，<=k層
f[n][k] = sigma(f[m][k] * f[n - m - 1][k - 1])，輸出f[n][k] - f[n][k - 1]
就是每次添加一整個(gè)括號(hào)塊。
Under Control (In List)
轉(zhuǎn)換坐標(biāo)離散化吧
類似思路有道超級復(fù)雜版
Soldier
Holidays (In List)
Not AC Yet
Laboratory
記得列出式子調(diào)整下就行了。時(shí)限嚇人的～
Maps
Crazy Painter
Puzzle
沒記錯(cuò)的話BFS一下吧。。。
Quest
經(jīng)典的狀態(tài)壓縮BFS，輸方案有點(diǎn)麻煩。。。
Stable Sets