Codeforces Round #364 (Div. 2)

http://codeforces.com/contest/701

題目：
pA : http://codeforces.com/contest/701/problem/A
pB : http://codeforces.com/contest/701/problem/B
pC : http://codeforces.com/contest/701/problem/C
pD : http://codeforces.com/contest/701/problem/D
pE : http://codeforces.com/contest/701/problem/E
pF : http://codeforces.com/contest/701/problem/F

My solutinos :
pA : http://codeforces.com/contest/701/submission/19329561
pB : http://codeforces.com/contest/701/submission/19331053
pC : http://codeforces.com/contest/701/submission/19333717
pE : http://codeforces.com/contest/701/submission/19878556
pF : http://codeforces.com/contest/701/submission/19885355

題解：

pA :
題目大意：給你n個數字(2<=n<=100，n是偶數)，請你找出n/2個配對(兩個數字為一個配對)，使得這n/2個配對總和一樣(題目保證有解！)。

那就隨便唬爛一下就好啦XD。看你要開陣列存 or 開set or O(N^2)解，都可以。

pB :
題目大意：現在有一個n*n (1<=n<=10^5)的棋盤，以及m (1<=m<=min(n^2,10^5) 個城堡(相當於中國象棋的 車(ㄐㄩ))。每當下一個城堡時，問說有多少個格子不會被攻擊到。

這題有很多解法。我的作法是：紀錄現在有多少個row和col是有被城堡佔領的。之後再用數學解即可。

pC :
題目大意：給你一個序列(只包含大寫字母、小寫字母)，請求出最短的長度，使得這個長度包含所有出現的字元。

使用爬行法(two pointers)！就okay囉！

pD :
聽說有數學解，可是我看不太懂。有好心人士願意告訴我的話，歡迎在下面留言 ^_^。

pE :
題目大意：給你一棵大小n(2<=n<=10^5)的樹。這其中有2*k個點是大學。你現在要把這些點連接起來，使得經過的路線總和最大！

有一個很神奇的想法是說：有一條邊，把樹分成兩半：一半有s個大學，另外一半就有2*k-s個大學，其中，這一條邊一定會經過min(s,2*k-s)次(有點greedy的想法，大概就是走越多越好的概念)。基於這個想法，我可以DFS整棵樹，在過程中，我就維護子樹有大學的數量，在求出答案，就okay了~~。

pF :
題目大意：給你一張有權重的無向圖(不保證強連通，可能有重邊、自環)，v個節點(1<=v<=1000)，e條邊(1<=e<=30000)，以及兩個點s,t (s!=t)。現在你可以清掉c個邊(0<=c<=2)，使得s不能走到t且清除的邊中，權重和最小。

分成三種case討論吧！

case 1 : c=0 --- 直接輸出答案即可！代表在圖中s走不到t。

case 2 : c=1 ： 那你先找出任一一條s到t的路徑(看是要BFS or DFS皆可，總之想辦法用到O(E) )，接下來，找出圖中的割邊( 使用 low 函數)，如果割邊是在那條路徑上的話，那就有可能是答案。

case 3 : c=2 ： 先試著移除掉你找過那條路徑上的任意一個邊，然後再從新的圖中，再找出一條s到t 的路徑，然後再找一次割邊，跟case 1一樣。

期望複雜度：O(n * m)，我寫的複雜度：O(n*m*lgn)