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é)的方法就直接暴力即可,當(dāng)f[i]=f[1]&&f[i-1]=f[0],i-1必是一個(gè)循環(huán)的長(zhǎng)度。算出A數(shù)組以后，其實(shí)就是對(duì)于字符串的操作了。比賽的時(shí)候用后綴數(shù)組算出來了，但是沒想到O(n)的操作。賽后看到AC說是o(n)的DP，堅(jiān)定復(fù)雜度后想到，在算出height數(shù)組后，用當(dāng)前位置表示為最低位置，然后向左向右擴(kuò)展到第一個(gè)比當(dāng)前位置低的地方，并bl[],br[]數(shù)組記錄這個(gè)最左和最右，幾乎就是o(n)的。

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

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

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

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

G. MiniSum
dp[i][j]表示當(dāng)只考慮前i個(gè)物品時(shí)，要準(zhǔn)備加入第i+1個(gè)物品時(shí)，X[i+1]前面的系數(shù)為j時(shí)的函數(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][?]取個(gè)最大的。

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

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

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