A.Nth Largest Value
PKU 3781 http://poj.org/problem?id=3781
水題，求10個數中第3大的數。
B.Equal Sum Partitions
PKU 3782 http://poj.org/problem?id=3782
題意：給定一個M(M <= 10000)個元素的序列，將它切割成K塊，每塊的和相等，求最大的K。
題解：枚舉。
首先，切成K塊，每塊和相等，那么這個和必定是M個元素總和的一個因子，那么可以枚舉第一個塊的長度（M種），判斷當前塊的和是否能被所有數的總和整除，如果可以，順序判斷可行性，看似復雜度是O(M^2)，但是能否整除這個剪枝可以篩選掉絕大部分情況。
C.Balls
PKU 3783 http://poj.org/problem?id=3783
題意：給定B (B <= 50) 個一樣的球，從 M (M <= 1000) 層樓上一個一個往下扔，存在某個樓層K，使得低于它的樓層往下扔球，球不會碎，在第K層扔下去會碎。求最壞情況下，需要扔幾次才能確定這個K。
題解：動態規劃。
令DP[i][j]表示總樓層為i，持有j個球時，最壞情況需要的次數；
那么如果從k ( 1 <= k <= i) 層進行扔球，有兩種情況：
1) 如果球不碎，則還需要進行DP[i-k][j]次測試（向更高的樓層進發）；
2) 如果球碎，那么還可以進行的次數為DP[k-1][j-1] （損失了一個球）；
由于要考慮最壞情況，所以每次測試必須取(1) (2)中的大者+1，每次選定一個樓層，使得這個樓層往下扔球的結果的最大值最小，也即狀態轉移方程為：
DP[i][j] = Min( DP[i][j], Max(DP[i-k][j], DP[k-1][j-1]) + 1 );
Pku上有道和這題想法類似的題：http://poj.org/problem?id=1243
D.Running Median
PKU 3784 http://poj.org/problem?id=3784
題意：一個長度為M(M <= 9999)的序列，每次奇數位的數讀入的時候計算前面整個序列的中位數。
題解：二分 + 樹狀數組。
由于數字是int32范圍，所以首先需要將所有數離散到下標，枚舉每一個數字讀入，將對應位的數字下標插入到樹狀數組中，每當讀到奇數個的時候，利用樹狀數組的成端求和的性質，如果要找第K大的數，那么就二分一個答案，然后查詢樹狀數組，如果求和大于等于K，表示是一個候選解（因為要保證大于等于K的數最小，才是第K大的數），反復二分，直到找到最小的值V滿足sum(V) >= K，時間復雜度O(2 *M * log(M) )。
E.The Next Permutation
PKU 3785 http://poj.org/problem?id=3785
題意：給定一個可重復元素的排列A[i]，求下一個排列。
題解：從后往前掃描，對于第i個元素A[i]，如果能夠找到一個j，使得A[j] > A[i]，并且滿足A[j]是繼第i位之后最小的數，那么將A[i]和A[j]進行交換，然后將A[i+1]到末尾的元素進行一次不降序排序，最后得到的串就是解。
F.Adjacent Bit Counts
PKU 3786 http://poj.org/problem?id=3786
題意：求長度為n的二進制整數中，相鄰兩個1的對數有k對（可重復使用）的整數個數。
題解：動態規劃。
令長度為n，相鄰1的對數為k的數的個數為DP[n][k]，其中以0結尾的為DP[n][k][0]，以1結尾的為DP[n][k][1]，那么 DP[n][k] = DP[n][k][0] + DP[n][k][1]；
并且有如下狀態轉移方程：
1) 長度為n-1的二進制數在末尾加上一個0，相鄰1的對數不變，所以有：
DP[n][k][0] = DP[n-1][k][0] + DP[n-1][k][1];
2) 長度為n-1的二進制數在末尾加上一個1，相鄰1的對數取決于，第n-1位是0還是1，當第n-1位是1，相鄰1的對數+1；當第n-1位是0，相鄰1的對數不變，所以有：
DP[n][k][1] = DP[n-1][k][0] + DP[n-1][k-1][1];
并且初始狀態下DP[0][0][0] = 1, DP[0][0][1] = 0
G.Convex Hull of Lattice Points
PKU 3787 http://poj.org/problem?id=3787
題意：凸包。
題解：Graham掃描法求解即可。
H.Interior Points of Lattice Polygons
PKU 3788 http://poj.org/problem?id=3788
題意：給定一個凸多邊形，求它內部所有的水平線段。
題解：從多邊形第一個點的y坐標開始，遞減枚舉水平線段的y坐標，分別和多邊形的n條邊進行求交點；
1) 如果水平線段和多邊形某條邊共線，說明正好到了多邊形的邊緣，無須往下枚舉，跳出循環。
2) 如果水平線段和多邊形小于一個交點，那么當y軸再次減小的時候，必然沒有交點，也無須繼續枚舉。
3) 否則，將左端點坐標取上整x1，右端點取下整x2，如果x1 <= x2 將它插入到解集中。