# 1001 degree 題解
沒有圈 (cycle) 的簡單圖 (undirected simple graph)，等價於由多顆樹 (tree) 組成的森林 (forest)。這裡用 $V$ 代表點的數量，$E$ 代表邊的數量 (取代題目中的 $N$ 以及 $M$)，$C$ 代表森林中樹的數量。
## $K = 0$ 的 case
不妨先化簡一下題目，在 $K = 0$ 的狀態下要達到 degree 最大化，可以貪心的把森林中所有樹各自接一條邊到已知 degree 最大的點上。答案是 ```C + 已知最大的 degree - 1```。
## $K \ge 0$ 的 case
回到原題，題目中規定一定要在添加邊之前把拔邊的操作作完，但是實際上任意調換添加邊以及拔掉邊的順序不會影響最後的結果。
考慮貪心添加完邊的樹，可以多拔掉一條邊再重新接上的效果等價於把答案 $+1$，要注意的是如果答案已經到達最大值 $V-1$ 的話，那拔邊再接上並不會影響答案。
所以答案為```min(V - 1, K + C + 已知最大的 degree - 1)```。
## 樹的數量 C = V - E
由於給定的圖是面數 (face) 為 $1$ 的平面圖 (planar graph)，所以根據平面圖的公式 $V - E + F = C + 1$ 整理後 $C = V-E$。另外一個證明：圖中每個 connected component 都是由樹所組成，也就是說每個 component 中邊數會是點數 - 1，直接可推得 $C = V - E$。
有了 $C = V - E$ 後，答案就變成 ```min(V - 1, K + V - E + 已知最大的 degree - 1)```。也就是，我們其實不用真正的寫出計算 connected component 的算法，只要統計 degree 最大的點有多大就可以計算出答案了。
整體時間複雜度為 $O(V)$，注意這題中有 $O(V) = O(E)$。
# 1002 hex 題解
這題是倍增法 RMQ 跟位元 DP 的組合。本題解會先討論化簡成一維陣列後的題目，再討論倍增法在六邊形中要如何操作。
## 一維的 case
假設本題發生在一維的矩陣上，也就是說，輸入從六邊形的結構變成一個一維的矩陣，每一個詢問都給定一個矩陣上的連續區間。
假設矩陣的長度為 $N$，可以利用 $O(N \log N)$ 的時間預處理，把 ```對於每個起點，長度為 2 的冪次 的區間的答案算出來```，之後對於每個查詢可以用 $O(1)$ 的時間處理。
### 表達顏色集合的方法
對於一個區間，我們可以用一個 $64$ 位元的整數來代表這個區間包含有哪些顏色，假設這個區間有第 $i$ 種顏色，那這個整數第 $i$ 個 bit 就為 $1$，反之則為 $0$。如果要對兩個區間的顏色取交集的話，把代表兩個區間的整數取 ```bitwise or``` 即可。最後要找出真正的答案時，就計算這個整數有幾個 bit 為 $1$ 即可，這一步可以做到 $O(\log 64)$ (這邊的 $64$ 為整數的位元數)，但是因為 $64$ 是常數，在本題解裡將會把這步視為 $O(1)$。
### 預處理
對於每個 ```2 的冪次``` 的長度，枚舉每一個起點去計算其答案。當長度為 $2^0 = 1$ 時，答案為自己本身有的顏色。而對於長度為 $2^i$ 時，每個起點的答案可以藉由兩個 $2^{i-1}$ 的區間取交集求出。對於一個特定的長度所花的時間為 $O(N)$，而我們總共有 $\log N$ 種長度 (因為是 2 的冪次)，所以預處理的時間為 $O(N \log N)$。
### 求解答
對於一個區間的詢問，假設此詢問長度為 $X$，第一步是找出小於等於 $X$ 的最大的 2 的冪次 $Y$ (例如小於等於 $7$ 的最大 2 的冪次為 $4$)。然後再把這個區間分成兩個區間，這兩個區間的長度皆為 $Y$，其中一個的起點跟詢問的區間一樣，另外一個的終點跟詢問的區間一樣，注意這兩個區間有可能有重疊。分出來的兩個區間有一個性質，就是其交集會跟原始詢問的區間一致，所以對於詢問的答案就可以用這兩個區間的答案 (已經預處理完了) 來取交集。
## 原始題目
六邊形上面也可以用倍增法！但是在預處理 $2^i$ 的時候，我們要考慮 $6$ 個長度為一半 $2^{i-1}$ 的子六邊形，以及最中心的一個點，共 $7$ 個地方，才能完整覆蓋長度為 $2^i$ 的六邊形。因為 $7$ 依然是常數，所以預處理的時間複雜度還是 ```起點數量``` 乘上 $\log L$。而在對詢問求答案的時候只要考慮 $6$ 個長度為最大的 2 的冪次子六邊形即可完整覆蓋詢問的六邊形，也是可以在 $O(1)$ 內作完！
整體時間複雜度為 $O(L^2\log L + Q)$。
## 另解
也可以使用 $2L-1$ 個線段樹，每次詢問時走訪每一個線段樹，這樣時間複雜度為 $O(QL\log L)$。
# 1003 odds 題解
這題是在樹 (tree) 上的一個問題，對於每一個葉節點 (leaf node) 要給出一個答案。這題可以在走訪 (traversal) 樹的過程中維護一些資料來求出解答。
## $P$$\times$ $Q^{-1}$ $mod$ $(10^9 + 7)$
答案要求輸出一個整數 $V = P \times Q ^ {-1} \ mod\ (10^9 + 7)$，其中 $P / Q$ 為所求答案的最簡分數。這可以看作是一個避開浮點數評測問題的方法。因為模運算的緣故，我們可以只維護一個整數，這個整數在乘上一個浮點數的時候，直接乘上浮點數的分子再乘上浮點數分母的乘法反元素就好了。相似的，要除上一個浮點數時，可以乘上浮點數的分母，再乘上浮點數分子的乘法反元素即可。
至於找出乘法反元素的算法，網路上可以找到詳細的說明，這邊就不贅述。值得注意的是，這題中只會用到最大為 $2 \times 10^5$ 的反元素，先建表的話有機會可以節省一點點點時間。
以下我們將假設只需輸出浮點數來討論，以精簡題解的內容。
## 單一一個葉節點
對於單一一個葉節點，我們要做的事情其實是貪心的選擇從根 (root) 到此葉節點的路徑 (path) 上最有"效益"的 $M$ 個節點，在此路徑上某個非葉節點 (non-leaf node) 對於在路徑上的那條邊的"效益"，指的就是這個非葉節點通往所有孩子 (不限定在此路徑上) 的邊的權重最大值除以在此路徑上的那條邊的權重，也就是說，如果在路經上的邊就已經擁有最大的權重的話，那效率就是 $1$，反之，我們都可以藉由選擇此節點交換邊來增加通往葉節點的機率。
我們可以在讀入輸入的時候就以 $O(N)$ 的時間預處理，找出每個節點通往所有孩子的最大權重，所以對於一個單一節點的答案，就等價於找出這條路徑上前 $M$ 大的效率值，再乘上原本到達這個葉節點的機率，即為答案。有一個小細節是，假設這條路徑不滿 $M$ 個非葉點，那最好的狀況就是對每個非葉節點都進行操作，多出來的操作次數是沒有意義的。
## 一次處理所有葉節點
如果我們對於每個葉節點分開處理，那時間複雜度顯然會過高。一個可行的改進方法就是作一次深度優先的樹走訪，再走訪的過程中維護到目前這個節點為止，前 $M$ 大的效率值。
在維護這 $M$ 個值的時候，我們可以使用類似 ```c++ stl``` 中 ```multiset``` 的結構。在通過一條邊的時候，把此節點對於這條邊的效率值丟進 ```multiset``` 中，此時如果 ```multiset``` 中超過 $M$ 個值，則把最小的值踢出，要注意此值要存起來。每當離開一條邊的時候，我們要把此節點對於這條邊的效率值從 ```multiset``` 中搜尋後移除，要注意不要一口氣把所有等於這個值的元素從 ```multiset``` 中移除，而是只能移除一個；並且，如果進入此節點時有剔除值，那這時就要把剔除的值加回去，以把 ```multiset``` 還原回進入此邊之前的樣貌。
此外要注意的是，在移除跟塞入值的時候，我們同時要維護前 $M$ 大的值的乘積，不然對於每個葉節點都重新花 $O(M)$ 的時間重算的話，複雜度也是不太行哦。
## 效率無限大的節點
在這題中有一個陷阱，也就是會存在權重為 $0$ 的邊，這些節點的效率值會因為除以零的關係變成無限大。理論上我們的確是要最優先的選取這些邊，因為在路徑上只要有任一一條邊權重為 $0$，那到達此葉節點的機率也跟著是 $0$，但是，在維護 $M$ 的乘積的同時會遇到一個麻煩，就是假如前 $M$ 大的值有一個是無限大的話，乘積也就跟著為無限大，另外，假設一開始到達某葉節點的機率為 $0$，那後來乘上無限大的話，值就不知道怎麼算了。
因此，解決方法就是，在維護前 $M$ 大的值的乘積的時候，我們把所有無限大的分母換成 $2 \times 10^5$ 再乘進去，這麼做的原因是，當我們選擇這條邊時，通往葉節點的機率將會從 $0$ 變成其權重除以 $2 \times 10^5$；並且，必須另外計數，維護到現在為止乘了幾個 (原來的) 無限大。同樣的，在計算一開始到達某葉節點的機率時，遇到權重 $0$ 的邊，也不是直接乘進去，而是維護到底這個葉節點經過了多少條 $0$ 的邊。到達某個葉節點的時候，如果這個葉節點的 $0$ 邊數大於乘積中應有的無限大數量時，那到達這個葉節點的機率就還是 $0$，而如果這兩個計數相等，那機率就會是維護的乘積乘上到達這個葉節點的機率，因為每一條原來為 $0$ 的邊都剛好被替換掉了。注意並不會有無限大的數量大於 $0$ 邊的數量，大家可以想想為什麼。
整體時間複雜度為 $O(N\log N)$。
# 1004 p1m2 題解
這題可以使用二分搜尋的技術來尋找最大值。在這個題解裡，我們用 $\min(A)$ 來表示一個陣列 $A$ 中元素的最小值，$\max(A)$ 來表示最大值。當 $0 \le \min(A)$ 且 $\max(A) - \min(A) \le 1$ 時，我們稱陣列 $A$ 為穩定的。我們只討論 $N > 1$ 的狀況。
## 二分搜尋
給定一個初始陣列 $A$，可以證明本題的答案 $V$ 一定存在。這個 $V$ 滿足：
1. $\min(A) \le V$。
2. 對於任意的整數 $0 \le v \le V$ 都可以找到一個可由 $A$ 到達的穩定陣列 $A'$ 使得 $\min(A') = v$。
3. 對於任意的整數 $V < v$，不存在任何可由 $A$ 到達的穩定陣列 $A''$ 使得 $\min(A'') = v$。
因此，我們可以透過這個性質來對答案二分搜！
## 判斷答案 $v$ 有沒有辦法達成
對於原始陣列裡面的每個 $>v$ 的元素 $x_i$，都可以貢獻 $\lfloor(x_i - v) / 2\rfloor$ 次的減法機會，而對於每一個 $<v$ 的元素，都需要 $v - x_i$ 次的加法。只要需要的加法的次數比減法的機會少 (或相等)，那 $v$ 就可以被達成。
### 但是還有沒有用完的減法次數怎麼辦呢
如果還有沒有用完的減法次數，我們會達到一個可能不穩定的 $A'$，配合上面的第 1. 點，已知此 $A'$ 會有一個至少為 $\min(A') = v$ 的答案 $V'$，再配合上面的第 2. 點，此 $A'$ 一定可以達到答案為 $v$ 的穩定的陣列。
## 證明答案 $V$ 一定存在且 $\min(A) \le V$
如果原始陣列 $A$ 不穩定的話，持續進行把最大的數減二，並且把最小的數加一的動作。這樣的操作不會讓最大值上升，也不會讓最小值下降，因此最後一定會收斂到一個至少為 $\min(A)$ 的答案。
## 證明對於小於答案 $V$ 的非負整數 $v$ 都可以被達成
以下證明：對於一個穩定的陣列 $A$ 並且 $\min(A) > 0$，一定可以達成一個穩定的陣列 $A'$，並且 $\min(A') = \min(A) - 1$。在這個證明中我們簡寫 $\min(A)$ 為 $m$。
首先考慮對於固定的兩個元素，分別各加減一次，結果會是這兩個元素各自被減一。
* 對於偶數的 $N$，我們可以把 $A$ 的元素兩個一組，每個都減一，就可以達成目標。
* 對於奇數的 $N$，$A$ 中的元素兩兩一組相減後，至多會留下一個元素其值為 $m+1$，也至少會有一個元素其值為 $m-1$，這時把前者減二後者加一，就變為 $m - 1$ 以及 $m$，也可以達成目標。
整體時間複雜度為 $O(N\log\max(X))$，其中的 $X$ 為原始給定的陣列。
# 1005 ratio 題解
這份題解將會描述兩種 $O(N)$ 解法 。在開始之前，假設讀者已經充分了解：經過 $O(N)$ 的 ```prefix sum``` 預處理後，可以用 $O(1)$ 的時間求出一個起點開始到某個 $0$ 時會取出的值。
## 解法 A
考慮到給定的值有範圍的限制，累加的和也只會是線性的成長，所以當公比大於 $1$ 或小於 $-1$ 時，等比級數能維持的長度是有所限制的，因此，我們可以枚舉陣列的每個地方當作起點，暴力找出這個起點可以有多長的等比級數即可。
這個解法中，因為公比為 $1$ 或 $-1$ 時，還是有可能造成很長的等比數列，因此當我們找了三項後發現公比為 $1$ 或 $-1$ 的話，就要特別判斷。首先，有一個性質為：只要找到原始陣列中連續的三個 $0$，也就是輸出陣列中的連續三項，無論首項具體的值是多少，因為第二項減去第一項的差，以及第三項減去第二項的差都是固定的，因此公比也就確定了。因此當我們發現某個起點最長的等比數列超過 $3$ 項、公比為 $1$ 或 $-1$ 時，原始陣列除了倒數兩個 $0$ 之外，其餘的起點公比也只能是 $1$ 或 $-1$，因此可以一併處理掉。
## 解法 B
相較於解法 A 中枚舉每個起點的做法，我們可以改由枚舉第一個 $0$ 的位置再往前找合適的起點有幾個。
延續上面觀察到的性質 (只要找到原始陣列中連續的三個 $0$，也就是輸出陣列中的連續三項，公比就確定了)。我們可以發現兩個不同公比的最長等比數列最多只會重疊兩項，因此可以對於每個可能的連續三個 $0$，我們都可以把公比算出來，並且往後找到同公比最長可以延伸到的位置，再這個區間中暴力的找有幾個起點可以滿足要求。算完一個區間後，我們只要把起點放到此區間的倒數第二個 $0$ 再找新的區間即可。
因為這些區間彼此最多只會相交兩項，所以最多只會有 $O(N)$ 個區間，這些區間的長度總和也只會是 $O(N)$。所以整體時間複雜度也會是 $O(N)$。這個解法比較麻煩的點是可能要另外計算長度為 $1$ 跟 $2$ 的等比數列。
## 固定三項間的差，求公比
假定 ```prefix sum``` 中對於真實首項的 offset 為 $\beta$，令 ```prefix sum``` 中三項的值分別為 $v_1 = x + \beta$, $v_2 = \alpha x + \beta$, $v_3 = \alpha^2 x + \beta$，而已知的差為 $A = v_2 - v_1 = x(\alpha -1)$ 跟 $B = v_3 - v_2 = x\alpha(\alpha - 1)$，因此公比 $\alpha$ 即為 $B/A$。要注意的是，如果$A=B=0$ 則公比為 $1$，如果 $A$ 跟 $B$ 中恰有一項為 $0$，那這三項 ($v_1$, $v_2$, $v_3$) 不構成本題合法的等比數列。
整體時間複雜度為 $O(N)$。
# 1006 rect 題解
這題是一個求最小值的問題，使用貪心法來解決。以下給出一個思路：
1. 最短的線段一定是這個點跟矩形四個邊平行/垂直的四個線段中最短的那一條。
2. 貪心的把每個點都選擇最短的線段，因為題目保證 $x$ 跟 $y$ 座標彼此不重複，所以這些線段彼此不會交叉。
3. 因此答案即為 $\sum_{i=1}^N \min(x_i, MX-x_i, y_i, MY-y_i)$。
題目中輸出的部分寫明答案為整數，可以做為一個小提示。
整體的時間複雜度為 $O(N)$。
## 1001 度度熊拼三角
**难度 0/5**
我们可以贪心地考虑这个问题。
先找到长度最长的三根木棒。
如果它们能构成三角形，那么答案就是它们的长度和。
否则我们会发现，最长的木棒过于长了，没有任何木棒能和它拼。
那么我们直接将其删除，不会影响答案。然后重复此流程即可。
最终做法即是：对木棒进行从大到小排序，每次检验连续的三根，若能构成三角形即为答案。时间复杂度$O(N \log N)$。
嘻嘻，样例是一个生日哦~
## 1002 度度熊学队列
**难度 1/5**
由于有频繁的连接操作和前后插入，显然要用双向链表来模拟此题。
选手可能会被“翻转”限制住思路，而尝试去写启发式合并的log做法，或者是带翻转标记的链表做法。
其实对于每一个“双端队列”，我们可以直接无脑开一个双向链表（无须记录谁前谁后），同时记录一下首和尾指针的位置。每次合并的时候直接 $O(1)$ 暴力“对接”即可。
时间复杂度为$O(Q)$。
## 1003 度度熊剪纸条
**难度 2/5**
这是一道比较简单的签到题，有不同的做法。
这里给出一个较为严谨的做法。
首先，对于一段连续的$1$，在中间剪是没有意义的。
进一步思考，每次必然会剪在一段$1$的两侧。
值得注意的是，有一些情况需要特殊判断。
具体地，对于中间一段连续的 $1$ ，我们剪两次才能把它剪下来（头和尾），不妨把代价记为$[1,1]$。
如果一段 $1$ 在开头，它的头是不用剪下来的，不妨把代价记为 $[0,1]$。
同理，如果一段 $1$ 在结尾，它的尾是不用剪下来的，可以把代价记为$[1,0]$。
最后还有一个问题：
在我们拼出的最终态中，最后一个$01$串不要求全$1$。
换句话说，我们可以把最多一个代价为$[x,y]$的段改成代价为$[x,0]$。
现在，我们要在这些集合里挑选一些段，使得中括号里代价和不超过$K$。
分情况讨论一下，排序后从大到小选即可。
复杂度为$O(N \log N)$
## 1004 度度熊看球赛
**难度 3/5**
此题有两种做法，这里介绍一种比较精妙的DP做法。
先把一组情侣的两个人看做是相同的（最后方案数要乘上$2^N$）。
设 $f_{i,j}$ 表示，一共有 $i$ 对情侣，且正好有 $j$ 对是挨着坐的。
每次考虑把第 $i+1$ 对情侣放进去：
（1）这对情侣合在一起放。
①放在某一对挨着的情侣中间（拆散他们）：$F_{i+1,j}+=F_{i,j} \times j$
②放在情侣之间的空隙里：$F_{i+1,j+1}+=F_{i,j} \times (2 \times i-j+1)$
（2）这对情侣分开放。
①他们各自都拆散了一对情侣：$F_{i+1,j-2}+=F_{i,j} \times (j \times \frac{(j-1)}{2})$
②只有一个人拆散了一对情侣：$F_{i+1,j-1}+=F_{i,j} \times (2 \times i-j+1) \times j$
③没有情侣被拆散：$F_{i+1,j}+=F_{i,j} \times ((2 \times i-j+1) \times \frac{2 \times i-j}{2})$
这样我们就能在 $O(N^2)$ 的时间里预处理出所有情况。
对于每一组询问，我们只要 $O(N)$ 扫一遍计算一下答案即可。
## 1005 度度熊玩数组
**难度 4/5**
每次使一个点失效，可以倒过来做，变成每次使一个点生效，然后询问所有有效区间权值和最接近K的值。
区间 $[l,r]$ 的权值和 $=S_r-S_{l-1}$，$S$ 为前缀和数组。
区间 $[l,r]$ 的权值和也 $=H_l-H_{r+1}$，$H$ 为后缀和数组。
可以预处理前缀和 $S$ 和后缀和 $H$，开两个 $set$ ，分别存放该区间内的 $S$ 和 $H$ 数组。
每次使一个点生效时，相当于合并两个区间。计算答案的时候可以像启发式合并一样枚举小区间的每个点作为区间的其中一个端点，然后在 $set$ 里询问并把 $set$ 启发式合并。
也可以开两棵主席树，在树上询问最接近的值。
复杂度$O(N \log^2 N)$
## 1006 度度熊算算术
**难度 5/5**
先考虑是一条链的情况。
因为有乘积不好处理，而数据可以认为是随机的，那么我们可以把每次的乘积取log后进行操作。
取log比较慢可能会影响复杂度，所以我们要预处理 $1$ ~ $10000000$ 的对数。注意可以利用对数的性质，只在质数出求。
这样我们可以快速写出一个$N^2 \times K$的DP。
设$f[i][j]$表示考虑前i个数，选了j段的最大乘积的对数。
每次我们枚举$k<i$，用$f[k][j-1]+log(sum[k+1..i]))$来更新$f[i][j]$。
注意到这个DP是有决策单调性的，理论上我们可以做到$N \times K$，但是采用比较方便的 $NK \log N$ 也行。
现在只需知道环怎么做就行了。
先考虑一些特殊情况，比如$K \leq 10$和 $K=N$ 的情况。
$K \leq 10$时，因为只划成常数块，我们枚举每一个开头做一遍链即可。
$K=N$ 时，因为划成了 $N$ 块，其实我们随便选一个点当开头都等价，做一遍链的情况即可。
那么我们不禁想到：$K$ 小的时候暴力做，K大的时候直接随机一些位置当起点做即可（因为合法的起点个数有 $K$ 个）
假设每次随机 $\lfloor \frac{N}{K} \rfloor \times G$个点（ $G$ 是一个小常数）。
对于所有情况打个表，发现 $N \leq 1000$ 时，如果取 $G=10$，那么能随机到某一个合法起点的概率是99.9%。
如果非酋不放心，可以取 $G=15$，此时正确率就是99.997%了，必然能通过此题。
最后的复杂度就是 $O(N^2 \times G)$ 或是 $O(N^2 \times G \times \log N)$，常数较小。
## 1001 调查问卷
**难度 1/5**
枚举所有可能的保留问题集合，检查是否至多有 $\frac{n(n-1)}{2}-k$ 对问卷在去掉集合外的问题之后是相同的。
## 1002 子串查询
**难度 1/5**
不难发现，$A[l,r]$ 中字典序最小的非空子串一定是由单个最小的字符构成，也就是说，只需要查询 $A[l,r]$ 中最小的字符及其出现次数。
## 1003 整数规划
**难度 3/5**
构造一个完全二分图 $K_{n,n}$，左边第 $i$ 个点和右边第 $j$ 个点之间连一条权值为 $a_{i,j}$ 的边，那么 $x_i$ 和 $y_j$ 满足用 Kuhn–Munkres algorithm 求解最小权匹配过程中的顶标的定义，
现在就是要计算最大顶标和，而这正好就是最小权匹配，使用正确实现的 KM 算法求解即可。
## 1004 点集划分
**难度 4/5**
先任意选定一个点 $u$，然后再找出一点 $v$ 连出一条直线，使得直线两侧均有 $n-1$ 个点，不难证明这样的 $v$ 一定存在，
现在以点 $u$ 为旋转中心让直线逆时针旋转直到碰到某个点 $w$，然后以点 $w$ 作为新的旋转中心继续让直线逆时针旋转，
由于可以轻微扰动直线，考虑在直线经过两个点 $u$ 和 $v$且两侧均有 $n-1$ 个点的时候枚举 $u$ 属于直线的哪一侧，那么 $v$ 在直线的另一侧，就得到了一个满足条件的划分，但是这样枚举出的划分可能有重复，可以使用 Trie 或者字符串 Hash 进行去重，
可以证明这个过程中每个点都能作为旋转中心，因此枚举出的划分去重后就是所有可能的划分，并且在旋转过程中直线左侧点数减去右侧点数只可能是 $-2,-1,0,1,2$，更具体地说，在直线经过两个点时只可能是 $-2,0,2$，所以在不超过 $6n$ 次改变旋转中心之后就会进入循环。
## 1005 序列计数
**难度 3/5**
记 $dp_{i,j}$ 为长度为 $i$ 的以 $p_j$ 为结尾的上升子序列个数，那么有 $dp_{i,j}=\sum_{k<j \land p_k<p_j}{dp_{i-1,k}}$，
如果按照 $j$ 从小到大的顺序递推，求和式中 $k<j$ 这一项条件自然满足，只需要对所有满足 $p_k<p_j$ 的 $k$ 求 $dp_{i-1,k}$ 的和，可以使用树状数组或者线段树维护，
由于输入的排列是随机选出的，一个有用的结论是最长上升子序列的长度期望是 $O(\sqrt{n})$。
## 1006 三原色图
**难度 2/5**
满足条件的 $k$ 条边必然包含一个由红色边和绿色边构成的最小生成树或者一个由蓝色边和绿色边构成的最小生成树，
不难证明一个图中所有最小生成树的边权集合是相同的，于是可以对两种情况分别求出一个最小生成树，再按照边权从小到大的顺序加入不在最小生成树上的边。
Problem Analysis - Astar 2017
by iSea Jul-15^2017
Arithmetic of Bomb
表达式的最大长度只有1000, #后面只会是一位的数字，也就是最大展开9次，因此直接展 开的最大长度不会超过9000,所以按照规则直接处理即可。
难度：2/5
Arithmetic of Bomb II
和i比，这个题目升级了很多
1.1<=length(NumberinBombterm)<=l0,所以无法直接展开
2. 包含+,-,*等复杂运算
一个可行的思路是把所有的操作都变成矩阵运算，即用当前结果与一个矩阵相乘，表示一种 操作。操作包含
1. 在当前表达式末尾添加一个数字
2. 在当前表达式末尾添加一个运算符：+,-,*
那么一次bomb操作就相当于对一个矩阵求幂。推导过程需要一些矩阵知识，以及比较复杂 的演算，可以参考标程。
难度：5/5
Pokemon GO
一个可行的思路是考虑三个子问题
1. 全部走完2*N个格子的方法总数DP[N]
2. 全部走完2*N个格子并且起点是最左边的两个格子之一的方法总数DP2[N]
3. 全部走完2*N个格子并且起点和终点分别是最左边的两个格子的方法总数DP3[N]
组合2和3的答案就可以得到1 了。
难度：2.5/5
Pokemon GO II
轨迹要么一直扩大，要么一直缩小，记录四个维度的极值，模拟Pok^mon的轨迹并判断是 否有覆盖情况出现。
一个更简单的做法需要发现一个几何性质：第一次覆盖一定是与轨迹上的前8段（或者更 少）中的某一段。
难度：3/5
Valley Number
非常经典的数位DP,可以将状态设计成四维
•当前数字长度len •最后一位数字digit •是否已经在递增序列里increased •是否和当前前缀相同same_prefix
转移时处理好这些状态就好了。
难度：2/5
Valley Number II
题目看上去是一道图论，然而问题并不像是二分匹配这种经典问题一样有一个多项式解法， 只能借助题目数据的特性使用集合DP解决。由于高的顶点个数只有最多15个，记录这些点 的匹配状态进行DP。并且数据规模较大，可能需要优化一些写法。
难度：2.5/5
##1001：
由于一把铲子不能挖掘同种颜色的金克拉，我们只要线性扫描序列即可。
按照贪心思想，若当前颜色种类的金克拉已经在挖掘范围内，我们只能迫不得已地换一把铲子，此时答案$+1$。
同时我们需要$O(nlogn)$的时间将所有颜色离散化，因为它也可以是负数。$(|C|<=2000000000)$
接下来是一个线性做法：考虑到每一次换铲子都需要更新计数数组，为了不超出时限，我们需要记录每次挖掘进行的初始位置bottom，这样每次clear 【bottom至当前位置】即可，每块金子计数一次，被清空一次，复杂度$O(2*n)$。
注意扫描完了也要记得将最后一段挖掘序列清空。
当然，这道题做法多种多样，有的同学一眼过去是个DP，有的同学用各种数据结构或STL做，都是可以的。
##1002：
这题更多算是想法题，有脑洞的同学可以各种乱搞。将问题转化成：求去掉$K$位数字后，不含前导零，且数字和是否能被三整除。按照预测，这里应该会汇聚本场最多的hack点。
我们设$S0$、$S1$、$S2$分别为原串上$mod 3=0$、$1$、$2$数字的个数。
我们假定删除取模后为$0$、$1$、$2$的数字各$A$、$B$、$C$个，则显然有$0<=A<=S0,0<=B<=S1,0<=C<=S2$且$K=A+B+C$且$Sum$ $mod 3=(A*0+B*1+C*2)mod 3=(S0*0+S1*1+S2*2)mod 3=bias$。
枚举$C$的值，我们可得$B mod 3=(bias-C*2)mod 3,A=K-B-C$。如果有若干组$A,B$不逾界，可知这些$(A,B,C)$是在模意义下合法的解，但不一定满足没有前导零。
所以，对于【大于$0$的数】我们贪心地从后往前删除，对于$0$我们贪心地从前往后删除。
需要统计出：$a3$=第一个【$mod 3=0$且非$0$的数】前$0$的个数（如果$mod 3=0$且非$0$的数不存在，那么$a3$就取所有零的个数），$E1$=【第一个$0$前是否存在$mod 3=1$的数】，$E2$=【第一个$0$前是否存在$mod 3=2$的数】。
则以下情况满足任一种都能保证无前导零：$A>=a3$。$B<$$S1$且$E1$。$C<$$S2$且$E2$。
##1003：
假设第$i$个位置出现的字母变换$a_i$次之后能变回自身，那么答案为$lcm(a_1,a_2,......,a_n)$，显然可以证明取值不同的$a_i$是不多的，最多只有六个。
令$f[i]$为变换$i$次之后能变回自身的字母的个数，那么我们可以枚举所有不同的$a_i$是否出现来确定它对答案的贡献。
那么问题就转化为：有一个长度为$n$的序列，每个位置都有$26$种取值，给定了一些不相交的集合，要求每个集合中至少存在一个元素出现过，求方案总数。令$Ans=$总方案数减去所有不合法方案数，这可以用容斥解决。
最终复杂度为$O(2^6*logn+3^6)$
##1004：
首先把限制转化成“和谐集合”中的所有元素两两相乘小于等于零。
考虑meet-in-middle，把问题分成两部分。求出一个子集元素的和以及两两相乘的和，假设前一半为$Ai$、$Bi$，后一半为$Cj$、$Dj$。
那么在合并的过程中，问题便转化成了：对于每个$i$，要求出有多少个$j$满足$Ai*Cj+Bi+Dj$≥$0$。
现在，若把$(Cj,Dj)$视为平面上的点，那么要求的就是一条直线上方的点数。
最后利用$k-d$ $tree$优化即可。
最后希望有尽可能多的选手AK这场比赛！
