A.Amicable Pair
親和數(shù)，先暴力算出數(shù)據(jù)，然后打表之。

B.A New Sequence Problem
先YM一下AC。根據(jù)題目里的公式，先生成A數(shù)組。算A[0]需要通過fibonacci找循環(huán)節(jié),找循環(huán)節(jié)的方法就直接暴力即可,當f[i]=f[1]&&f[i-1]=f[0],i-1必是一個循環(huán)的長度。算出A數(shù)組以后，其實就是對于字符串的操作了。比賽的時候用后綴數(shù)組算出來了，但是沒想到O(n)的操作。賽后看到AC說是o(n)的DP，堅定復雜度后想到，在算出height數(shù)組后，用當前位置表示為最低位置，然后向左向右擴展到第一個比當前位置低的地方，并bl[],br[]數(shù)組記錄這個最左和最右，幾乎就是o(n)的。

C.Coin Puzzle
給出一個多邊形和兩個圓，問兩個圓能不能放在多邊形里，并且兩圓不相交。
求出兩個圓的圓心的合法范圍，是兩個多邊形，然后求兩個多邊形的最遠距離

D.Tree Game
能構(gòu)成一顆生成樹當且僅當邊數(shù)不少于n-1條；如果能構(gòu)成一種生成樹，那么能構(gòu)成任意類型生成樹

E.Swap
發(fā)生在兩個環(huán)間的交換會將兩個環(huán)合并，發(fā)生在同一個環(huán)的交換會將這個環(huán)拆成兩個環(huán)。
如果不考慮奇偶性，那么每個環(huán)之間相互獨立，互不影響，現(xiàn)在若一個環(huán)里同奇偶性，例如全是奇數(shù)，那他肯定要和其他的環(huán)發(fā)生接觸，也就是和其他環(huán)合并，這里選擇全是偶數(shù)的環(huán)顯然不會更差。
如果沒有了偶數(shù)環(huán)，那就只能選擇和剩下的既又奇又有偶的環(huán)合并了。
最后可以證明一個環(huán)里既又奇數(shù)又有偶數(shù)時，最快將它完全拆開需要n-1步。

F.JinYueTuan
用隔板法可以知道答案是C(m+n-1, n) * n!. 但是數(shù)據(jù)量非常大，直接算乘積超時，加上一個剪枝瞬間出解：如果發(fā)現(xiàn)在邊乘邊模的過程中答案變?yōu)?，就可以跳出了。

G. MiniSum
dp[i][j]表示當只考慮前i個物品時，要準備加入第i+1個物品時，X[i+1]前面的系數(shù)為j時的函數(shù)最小值。
轉(zhuǎn)移就是dp[i][j] + j * (-Li) --> dp[i+1][j - Li]
 dp[i][j] + j * ( Li) --> dp[i+1][j + Li]
向后更新，最后答案就是dp[n][?]取個最大的。

H.Urban planning
題目十分費解，受不了了。。。
正確的理解就是給N個點，每個點有個權(quán)值，以及每兩個點之間有邊權(quán)，單向的。求出一個包含特定點（假設編號為1）的點的集合滿足：
1、這個集合元素要盡量多。
2、集合中的元素之間差異不能超過V。
3、在每個集合中選出邊，使特定點到其他點都有路可達，并且邊權(quán)之和要最小。
4、如果兩個集合元素個數(shù)相同，取較大的邊權(quán)。

首先，如果給出滿足條件的點集，我們知道每兩個點之間都有邊，只要求出一顆最小生成樹就行了，鑒于有向，所以求出從特定點的樹形圖就行了（關于根確定的最小樹形圖，參考劉朱算法）。所以只要找到這個滿足條件的集合就行了，注意到集合之中的元素最大差異不能超過V，而且V也很小，所以可以枚舉集合的權(quán)值區(qū)間[lo，lo+V]，所有權(quán)值落在這個區(qū)間中的點都滿足條件，由于任兩個點之間都有邊，所以一定存在樹形圖，最后求下最小樹形圖，然后判斷下就行了。。。
I.Air Strike
離線操作，把刪除和查詢都保存起來。把刪除保存后排序并unique，查詢也進行排序，然后從小到大查詢，看當前是否被刪除，刪除的話跳過當前這個點往后移一個，驚訝于最后代碼40行以內(nèi)。

J.MiniCost
題目意思就是給出一個括號序列，每次可以選擇改變特定點上的括號方向，并且改變有權(quán)值。求出最小的改變權(quán)值和，使這個括號序列合法。
暫時只會O（N^2）算法。
注意到如果一個括號序列要是合法的話，任意位置一定是左括號數(shù)大于等于右括號數(shù)，所以以此定義狀態(tài)dp[i][j]，表示前i個符號中，左括號比右括號多j個。只要根據(jù)當前的符號轉(zhuǎn)移就行了。。 初始條件dp[0][0] = 0 。。最后答案dp[N][0] 。。。