第一次寫網(wǎng)絡賽的題解，福州賽區(qū)網(wǎng)絡賽作為我第一年ACM最后一次網(wǎng)絡賽醬油，畫了一個很像逗號的句號.....好吧，還得為北京現(xiàn)場賽準備啊準備.......

這次醬油打的很犀利，貌似出第一題很快，之后節(jié)奏就總比師兄們慢一步.....囧死了，名次很順利的入手，就沒啥了，寫下題解吧。

題目鏈接 

第一題：A Card Game

坑爹的題目敘述，仰慕杰哥非常犀利的YY出題意，ans = a[1] / N......好吧，現(xiàn)在證明一下啊。

首先，我們假設取牌的順序是一個序列，我們考慮可行序列存在的情況：對于序列中任意一個數(shù)i的后面一個數(shù)j，必然要放在第i堆里面，因為值為i的數(shù)有a[i]個，所以在i后面的數(shù)也恰好有a[i]個，所以a[i]數(shù)放在了第i堆，符合題目約束了。

由于游戲從第一個堆開始，第一個數(shù)是沒有前驅(qū)的，所以，如果最后一個數(shù)不是1，那么第一堆必然是a[1] ＋　１個數(shù)了，與約束不符合。而且，如果最后一個數(shù)不是１，記為ｉ的話，就只有a[i] - 1個后繼了。

所以，綜上，只有最后一個數(shù)為1，那么堆容量a[i]才會符合約束，而我們能根據(jù)序列構(gòu)造一種符合情況的分攤和取牌方案，所以，題目變?yōu)榱耍篘個數(shù)的全排列，其中最后一個是1的概率.....

先從a[1]個1里面取一個1，有a[1]種方案，之后剩下N-1個數(shù)全排列(N-1)!，符合結(jié)尾是1的方案數(shù)是a[1] * (N-1)!種，所以解就是a[1] / N。

第二題：Abalone 

這游戲....沒玩過啊.....膜拜華中科技大斬殺此題并且是FB啊.....

第三題：Aircraft

一道計算幾何的問題，和VIJOS上面的一道DP題WALL挺像的，不過那個是正方形，這個是圓形。

首先很容易想到就是最短路了，因為N范圍很小，枚舉所有圓的交點，之后你要么過圓心，要么過交點，之后最短路，不過有個trick，就是很多圓排列那種情況，可以不過任何交點圓心直接到達。所以，對于那種情況，分段判斷一下這個線段是否整個在園中就行了。這個判斷是相當繁雜的，先求出線段與圓的所有交點，之后對這些點排序，判斷相鄰兩個點之間的線段是否在圓上就OK了....

第四題：Carcassonne

達哥犀利的AC了此題，我們都知道是DP，但是我比賽的時候怎么也沒想出轉(zhuǎn)移方程....好吧，插頭DP咱不會.....

賽后想到了高中時候?qū)戇^的多米諾，和這個很像，兩個解法，狀態(tài)壓縮DP和矩陣乘法....后者我忘了....

狀態(tài)壓縮DP：狀態(tài)就是每行下面連成的圖案狀態(tài)（最多3^12狀態(tài)數(shù)）

轉(zhuǎn)移方程f[row][next_line] = sum(f[row - 1][pre_line])其中，pre_line和next_line是該行合法狀態(tài)時，上一行圖案和下一行圖案。

第五題：Catan

非常犀利的一道題，卡掉了華中科技大AK全場的機會，而且，這個游戲我沒玩過，也就沒看題了.....

第六題：Random Sequence

一道數(shù)學題。

結(jié)論：我們設序列a是長度為i所有情況的綜合（就是不除以那個2^n），b序列是b[i] = a[i] - a[i-1] * 2，觀察b數(shù)列我們可以特出，如果是i偶數(shù)，那么b[i] = 2 * b[i-1]，如果是i奇數(shù)，那么就等于C((i+1)/2)(i+1)（i+1里面取一半....）b序列有了，a也就有了，除以2^n，得解。

下面論證一下這個YY式子出的式子是對的.....

首先，我們可以知道a[i] >= a[i-1] * 2，因為i-1序列長度增加了，解的種類增加，而且上限也增加了，這就是為什么會大于，由于長度存在奇偶性質(zhì)，所以奇位和偶位增加一位的情況有一樣了......

之后....具體的.....我也說不清楚了.....總之，數(shù)學歸納法出來的是對的，而理論上.....我不是數(shù)學家。。

第七題：Random Maze

這道題看了，沒寫，因為等我看著道題的時候，已經(jīng)馬上收場了.....看完這道題后我淡定地打開了數(shù)獨......

說一下思路吧，改變每條表的權值為a-b，添加一條終點指向起點的特殊邊，這樣保證里每個點出入度相等的條件，之后找出所有負向環(huán)正向，如果環(huán)中沒有那個特殊邊，就是impossible，不過對于搜環(huán)和重邊的問題，我還真沒有啥好方法.....SPFA吧......

下面是來自Starvae的解題：最小費用最大流(膜拜)

下面是直接建圖的方法。

我們的答案保存在sum中。

初始時每個點的in[] out[] 都為0, in[i] 表示第i這個點需要in[i]條指向i的邊才能滿足i這個點的入度平衡。

對于每條邊，如果a <= b 那么建 v->u的邊，流量為1， 權值為b-a。 sum+= a;

此時， u->v 被翻轉(zhuǎn)， 所以in[v] ++, out[u] ++.

否則 建 u->v的邊， 流量為1， 權值為a-b。 sum += b;

此時, u->v 沒有被翻轉(zhuǎn)， 所以in[] out[] 不改變

然后添加一條終點指向起點的邊， 直接in[s] ++; out[t] ++;

然后新建超級源匯S,T。

對于每個點i， 如果in[i] > out[i] . 建邊S->i, 權值為0， 流量為in[i] – out[i];

否則的話 建邊 i->T ,權值為0， 流量為out[i] – in[i];

然后跑一次最小費用最大流。

如果最后從S出去的邊沒有滿流的話 就是impossible。

否則答案即為sum+ mincost.

第八題：SanguoSHA

呃，很暴力的一道題，6！* 6!真心能接受啊......

全排列自己的武將，和對方全排列的比，如果完勝，輸出，不完勝，下一個排列。

next_permutation函數(shù)很好用。

第九題：Squiggly Sudoku

模板題吧.....算是吧......強大的Dancing Links，高中為了玩數(shù)獨，弄了它好久....而且現(xiàn)在也沒弄明白，讀入比較特殊，DFS一下，之后果斷十字鏈表......

第十題：War

又是一個游戲題......

題目很短，而且開場被FB，之后我果斷讀題，YY了兩個題意，先殺死時間最長的或者先殺死需要最少了，師哥看了數(shù)據(jù)果斷否定了我第二個YY，之后開始敲，一個sort，出解，感覺速度挺快了....可是就這樣還被落在了第二頁，仰慕眾神牛隊的速度啊......

總結(jié)：這次網(wǎng)絡賽，背景都是游戲，還都是我沒玩過的游戲.......三國殺除外......我了個去啦，在中國，是吧，主流游戲就是三國殺，WOW，DOTA，SC2，您老倒好，弄些外國的游戲......好吧，不吐槽了，感覺題挺好的，難水分明.....網(wǎng)絡流那道我真TM的沒看出來是網(wǎng)絡流啊......還有那兩個我題都懶得看的題......我老懷疑有時候我不是在打ACM比賽，我像在考GRE.....第一次寫這么全的題解報告，大家多批評吧......

而且，這次網(wǎng)絡賽醬油打的很好，很專業(yè)，打出了國際水平~~~~~