Codeforces Round #366 (Div. 2)

http://codeforces.com/contest/705

最近好久沒po CF詳解了，因為最近都在刷UVA。之後有空會慢慢補上之前的，並且會盡力AC全部的題目。 ^_^

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

我AC的code：
pA : http://codeforces.com/contest/705/submission/19688112
pB : http://codeforces.com/contest/705/submission/19698156
pC : http://codeforces.com/contest/705/submission/19697521
pD : http://codeforces.com/contest/705/submission/19726277

題解：

pA :
題目大意：n=1 : I hate it. n=2 : I hate that I loveit. n=3 : I hate that I lovethat I hate it. n=4 : I hate that I lovethat I hate that I loveit. 以此類推

solution :
當n%2==1時，輸出I hate ，n%2==0時，輸出I love 。之後再處理一下that 跟 it。
可以看code理解一下喔。

pB :
簡化版題目大意：給你n個數字(1<=n<=10^5)，對於某個大於1的數字，你可以選擇把那個數字分解成p , x-p (1<=p < 某個數字)，誰先不能做出動作，誰就輸了。

solution :
可以想像的事說，我們可以想像：美個數字 - 1 之後，代表這個數字還可以被分解的次數！因此，我們可以維護 (每個數字-1) 的和，用%2去判斷輸贏！

注意一點，如果sum沒有 long long 維護，也是okay了(overflow時奇偶性是對的)！

pC :
題目大意：你有q個手機app，每個手機app一次都會發出一個通知(notification)。現在你要支援3件事情：1. 某個應用程式x 發出一個通知 2.你讀了應用程式x的所有通知 3. 你讀了前t個通知 。每筆操作過後，都要輸出目前有多少通知是沒有被讀到的(unread)。

solution :
我這題是用deque做，複雜度是 均攤O(N) 。
對於每個deque[i]，你就維護第i個應用程式中，未讀的編號！然後你還要順便紀錄第三筆測資的t做到哪裡。還要順便紀錄第x個通知有沒有被使用過、以及第i個通知是由哪個app發送的。

那，對於操作1，你就deq[x] . push_back(cur_id)，順便其他的紀錄一下。對於操作2，你就把deq 給 clear掉就好，順便紀錄哪個被用過。對於操作3，你就均攤O(N)掃過即可。詳細的話，認真看我的code吧 XD。

pD :
題目大意：你要完成一個給定起點、終點的Hamilton Path，每個Path都有不同的weight。你要使得weight的和最小。圖是一張完全圖。

solution :
看code吧~。

主要就是說：每次當你要多一個點時，你就很greedy的找一個最好的，之後破壞掉(重建)！