Codeforces Round #367 (Div. 2)

http://codeforces.com/contest/706

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

My Solutions :
pA : http://codeforces.com/contest/706/submission/19788234
pB : http://codeforces.com/contest/706/submission/19790222
pC : http://codeforces.com/contest/706/submission/19797359
pD(1) : http://codeforces.com/contest/706/submission/19806189
pD(2) : http://codeforces.com/contest/706/submission/19823423

題解：
pA :
題目大意：給你一個固定點(a,b)以及n個(1<=n<=100)其他的點(xi,yi)。請求出其他點到固定點的最小距離。

那你就開一個計算距離的函式，認真維護距離一番。記得輸出答案的時候，要指定輸出的位數：(1) #include <iomanip>中，cout << fixed<<setprecision(位數) << num<<endl; (2) printf("%.位數f", num);

pB :
題目大意：給你n個數字(1<=n<=10^5)，q比詢問(1<=q<=10^5)，求有多少個數字小於等於mi。

求upper_bound或lower_bound即可XD。用法可以參考我的code

pC :
題目大意：現在有n個字串(1<=n<=10^5)，你可以對字串i做出反轉這個動作，可是每當你反轉，就要花費ci。現在你需要把這n個字串按照字典序排好(C++ string中的大於&小於)，請求出最少的花費。

那你就開一個兩條dp陣列(dp[2][MAX_N])，初始值是INF(無限大)，dp[0][i]的意思是說以沒有反轉的i為結尾的最小cost，dp[1][i]是有反轉的。

遞迴的方式：dp[0][i] = min(dp[0][i] , dp[1][i-1] if valid , dp[0][i-1] if valid) , dp[1][i] = min(dp[0][i-1] + c[i] if valid, dp[1][i-1] + c[i] if valid)。

pD :
題目大意：維護一個很像multiset的資料結構：支援(1)插入 (2)刪除 (3)查詢，查詢是指給你一個數字i，求出max(i ^ j) ，其中j是在mutliset裡面，^是XOR運算。一開始multiset就有0

第一份solution的解法：用treap維護multiset。接下來，對於"查詢"，先有一個greedy的概念：如果可以在越高的位元XOR成1，那就在越高的位元XOR成1。又因為數字範圍在1~10^9之間，所以位元最多只有lg 10^9 = 32次，對於每個位元，我把它分成0和1的部分，進行query，有比較高的XOR值，就先往那裏走，走到最後，就是答案了。複雜度 O(q lg q lg 10^9)

第二份：用trie存multiset，然後按照trie認真走即可 <(_ _)>