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 將它插入到解集中。