第一次寫網(wǎng)絡(luò)賽的題解，福州賽區(qū)網(wǎng)絡(luò)賽作為我第一年ACM最后一次網(wǎng)絡(luò)賽醬油，畫了一個(gè)很像逗號(hào)的句號(hào).....好吧，還得為北京現(xiàn)場(chǎng)賽準(zhǔn)備啊準(zhǔn)備.......
這次醬油打的很犀利，貌似出第一題很快，之后節(jié)奏就總比師兄們慢一步.....囧死了，名次很順利的入手，就沒啥了，寫下題解吧。
題目鏈接
第一題：A Card Game
坑爹的題目敘述，仰慕杰哥非常犀利的YY出題意，ans = a[1] / N......好吧，現(xiàn)在證明一下啊。
首先，我們假設(shè)取牌的順序是一個(gè)序列，我們考慮可行序列存在的情況：對(duì)于序列中任意一個(gè)數(shù)i的后面一個(gè)數(shù)j，必然要放在第i堆里面，因?yàn)橹禐閕的數(shù)有a[i]個(gè)，所以在i后面的數(shù)也恰好有a[i]個(gè)，所以a[i]數(shù)放在了第i堆，符合題目約束了。
由于游戲從第一個(gè)堆開始，第一個(gè)數(shù)是沒有前驅(qū)的，所以，如果最后一個(gè)數(shù)不是1，那么第一堆必然是a[1] ＋ １個(gè)數(shù)了，與約束不符合。而且，如果最后一個(gè)數(shù)不是１，記為ｉ的話，就只有a[i] - 1個(gè)后繼了。
所以，綜上，只有最后一個(gè)數(shù)為1，那么堆容量a[i]才會(huì)符合約束，而我們能根據(jù)序列構(gòu)造一種符合情況的分?jǐn)偤腿∨品桨福裕}目變?yōu)榱耍篘個(gè)數(shù)的全排列，其中最后一個(gè)是1的概率.....
先從a[1]個(gè)1里面取一個(gè)1，有a[1]種方案，之后剩下N-1個(gè)數(shù)全排列(N-1)!，符合結(jié)尾是1的方案數(shù)是a[1] * (N-1)!種，所以解就是a[1] / N。
第二題：Abalone
這游戲....沒玩過啊.....膜拜華中科技大斬殺此題并且是FB啊.....
第三題：Aircraft
一道計(jì)算幾何的問題，和VIJOS上面的一道DP題WALL挺像的，不過那個(gè)是正方形，這個(gè)是圓形。
首先很容易想到就是最短路了，因?yàn)镹范圍很小，枚舉所有圓的交點(diǎn)，之后你要么過圓心，要么過交點(diǎn)，之后最短路，不過有個(gè)trick，就是很多圓排列那種情況，可以不過任何交點(diǎn)圓心直接到達(dá)。所以，對(duì)于那種情況，分段判斷一下這個(gè)線段是否整個(gè)在園中就行了。這個(gè)判斷是相當(dāng)繁雜的，先求出線段與圓的所有交點(diǎn)，之后對(duì)這些點(diǎn)排序，判斷相鄰兩個(gè)點(diǎn)之間的線段是否在圓上就OK了....
第四題：Carcassonne
達(dá)哥犀利的AC了此題，我們都知道是DP，但是我比賽的時(shí)候怎么也沒想出轉(zhuǎn)移方程....好吧，插頭DP咱不會(huì).....
賽后想到了高中時(shí)候?qū)戇^的多米諾，和這個(gè)很像，兩個(gè)解法，狀態(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)時(shí)，上一行圖案和下一行圖案。
第五題：Catan
非常犀利的一道題，卡掉了華中科技大AK全場(chǎng)的機(jī)會(huì)，而且，這個(gè)游戲我沒玩過，也就沒看題了.....
第六題：Random Sequence
一道數(shù)學(xué)題。
結(jié)論：我們?cè)O(shè)序列a是長(zhǎng)度為i所有情況的綜合（就是不除以那個(gè)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，得解。
下面論證一下這個(gè)YY式子出的式子是對(duì)的.....
首先，我們可以知道a[i] >= a[i-1] * 2，因?yàn)閕-1序列長(zhǎng)度增加了，解的種類增加，而且上限也增加了，這就是為什么會(huì)大于，由于長(zhǎng)度存在奇偶性質(zhì)，所以奇位和偶位增加一位的情況有一樣了......
之后....具體的.....我也說不清楚了.....總之，數(shù)學(xué)歸納法出來的是對(duì)的，而理論上.....我不是數(shù)學(xué)家。。
第七題：Random Maze
這道題看了，沒寫，因?yàn)榈任铱粗李}的時(shí)候，已經(jīng)馬上收?qǐng)隽?....看完這道題后我淡定地打開了數(shù)獨(dú)......
說一下思路吧，改變每條表的權(quán)值為a-b，添加一條終點(diǎn)指向起點(diǎn)的特殊邊，這樣保證里每個(gè)點(diǎn)出入度相等的條件，之后找出所有負(fù)向環(huán)正向，如果環(huán)中沒有那個(gè)特殊邊，就是impossible，不過對(duì)于搜環(huán)和重邊的問題，我還真沒有啥好方法.....SPFA吧......
下面是來自Starvae的解題：最小費(fèi)用最大流(膜拜)
下面是直接建圖的方法。
我們的答案保存在sum中。
初始時(shí)每個(gè)點(diǎn)的in[] out[] 都為0, in[i] 表示第i這個(gè)點(diǎn)需要in[i]條指向i的邊才能滿足i這個(gè)點(diǎn)的入度平衡。
對(duì)于每條邊，如果a <= b 那么建 v->u的邊，流量為1， 權(quán)值為b-a。 sum+= a;
此時(shí)， u->v 被翻轉(zhuǎn)， 所以in[v] ++, out[u] ++.
否則 建 u->v的邊， 流量為1， 權(quán)值為a-b。 sum += b;
此時(shí), u->v 沒有被翻轉(zhuǎn)， 所以in[] out[] 不改變
然后添加一條終點(diǎn)指向起點(diǎn)的邊， 直接in[s] ++; out[t] ++;
然后新建超級(jí)源匯S,T。
對(duì)于每個(gè)點(diǎn)i， 如果in[i] > out[i] . 建邊S->i, 權(quán)值為0， 流量為in[i] – out[i];
否則的話 建邊 i->T ,權(quán)值為0， 流量為out[i] – in[i];
然后跑一次最小費(fèi)用最大流。
如果最后從S出去的邊沒有滿流的話 就是impossible。
否則答案即為sum+ mincost.
第八題：SanguoSHA
呃，很暴力的一道題，6！* 6!真心能接受啊......
全排列自己的武將，和對(duì)方全排列的比，如果完勝，輸出，不完勝，下一個(gè)排列。
next_permutation函數(shù)很好用。
第九題：Squiggly Sudoku
模板題吧.....算是吧......強(qiáng)大的Dancing Links，高中為了玩數(shù)獨(dú)，弄了它好久....而且現(xiàn)在也沒弄明白，讀入比較特殊，DFS一下，之后果斷十字鏈表......
第十題：War
又是一個(gè)游戲題......
題目很短，而且開場(chǎng)被FB，之后我果斷讀題，YY了兩個(gè)題意，先殺死時(shí)間最長(zhǎng)的或者先殺死需要最少了，師哥看了數(shù)據(jù)果斷否定了我第二個(gè)YY，之后開始敲，一個(gè)sort，出解，感覺速度挺快了....可是就這樣還被落在了第二頁，仰慕眾神牛隊(duì)的速度啊......
總結(jié)：這次網(wǎng)絡(luò)賽，背景都是游戲，還都是我沒玩過的游戲.......三國(guó)殺除外......我了個(gè)去啦，在中國(guó)，是吧，主流游戲就是三國(guó)殺，WOW，DOTA，SC2，您老倒好，弄些外國(guó)的游戲......好吧，不吐槽了，感覺題挺好的，難水分明.....網(wǎng)絡(luò)流那道我真TM的沒看出來是網(wǎng)絡(luò)流啊......還有那兩個(gè)我題都懶得看的題......我老懷疑有時(shí)候我不是在打ACM比賽，我像在考GRE.....第一次寫這么全的題解報(bào)告，大家多批評(píng)吧......
而且，這次網(wǎng)絡(luò)賽醬油打的很好，很專業(yè)，打出了國(guó)際水平~~~~~