A.Nth Largest Value
       PKU 3781 http://poj.org/problem?id=3781

水題，求10個數(shù)中第3大的數(shù)。

 

B.Equal Sum Partitions
       PKU 3782 http://poj.org/problem?id=3782

       題意：給定一個M(M <= 10000)個元素的序列，將它切割成K塊，每塊的和相等，求最大的K。

       題解：枚舉。

       首先，切成K塊，每塊和相等，那么這個和必定是M個元素總和的一個因子，那么可以枚舉第一個塊的長度（M種），判斷當(dāng)前塊的和是否能被所有數(shù)的總和整除，如果可以，順序判斷可行性，看似復(fù)雜度是O(M^2)，但是能否整除這個剪枝可以篩選掉絕大部分情況。

 

C.Balls
       PKU 3783 http://poj.org/problem?id=3783

題意：給定B (B <= 50) 個一樣的球，從 M (M <= 1000) 層樓上一個一個往下扔，存在某個樓層K，使得低于它的樓層往下扔球，球不會碎，在第K層扔下去會碎。求最壞情況下，需要扔幾次才能確定這個K。

題解：動態(tài)規(guī)劃。

令DP[i][j]表示總樓層為i，持有j個球時，最壞情況需要的次數(shù)；

那么如果從k ( 1 <= k <= i) 層進(jìn)行扔球，有兩種情況：

1) 如果球不碎，則還需要進(jìn)行DP[i-k][j]次測試（向更高的樓層進(jìn)發(fā)）；

2) 如果球碎，那么還可以進(jìn)行的次數(shù)為DP[k-1][j-1] （損失了一個球）；

由于要考慮最壞情況，所以每次測試必須取(1) (2)中的大者+1，每次選定一個樓層，使得這個樓層往下扔球的結(jié)果的最大值最小，也即狀態(tài)轉(zhuǎn)移方程為：

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)的序列，每次奇數(shù)位的數(shù)讀入的時候計算前面整個序列的中位數(shù)。

       題解：二分 + 樹狀數(shù)組。

       由于數(shù)字是int32范圍，所以首先需要將所有數(shù)離散到下標(biāo)，枚舉每一個數(shù)字讀入，將對應(yīng)位的數(shù)字下標(biāo)插入到樹狀數(shù)組中，每當(dāng)讀到奇數(shù)個的時候，利用樹狀數(shù)組的成端求和的性質(zhì)，如果要找第K大的數(shù)，那么就二分一個答案，然后查詢樹狀數(shù)組，如果求和大于等于K，表示是一個候選解（因?yàn)橐ＷC大于等于K的數(shù)最小，才是第K大的數(shù)），反復(fù)二分，直到找到最小的值V滿足sum(V) >= K，時間復(fù)雜度O(2 *M * log(M) )。

 

E.The Next Permutation
      PKU 3785 http://poj.org/problem?id=3785

題意：給定一個可重復(fù)元素的排列A[i]，求下一個排列。

題解：從后往前掃描，對于第i個元素A[i]，如果能夠找到一個j，使得A[j] > A[i]，并且滿足A[j]是繼第i位之后最小的數(shù)，那么將A[i]和A[j]進(jìn)行交換，然后將A[i+1]到末尾的元素進(jìn)行一次不降序排序，最后得到的串就是解。

 

F.Adjacent Bit Counts
      PKU 3786 http://poj.org/problem?id=3786

題意：求長度為n的二進(jìn)制整數(shù)中，相鄰兩個1的對數(shù)有k對（可重復(fù)使用）的整數(shù)個數(shù)。

題解：動態(tài)規(guī)劃。

令長度為n，相鄰1的對數(shù)為k的數(shù)的個數(shù)為DP[n][k]，其中以0結(jié)尾的為DP[n][k][0]，以1結(jié)尾的為DP[n][k][1]，那么 DP[n][k] = DP[n][k][0] + DP[n][k][1]；

并且有如下狀態(tài)轉(zhuǎn)移方程：

1) 長度為n-1的二進(jìn)制數(shù)在末尾加上一個0，相鄰1的對數(shù)不變，所以有：

DP[n][k][0] = DP[n-1][k][0] + DP[n-1][k][1];

2) 長度為n-1的二進(jìn)制數(shù)在末尾加上一個1，相鄰1的對數(shù)取決于，第n-1位是0還是1，當(dāng)?shù)?/span>n-1位是1，相鄰1的對數(shù)+1；當(dāng)?shù)?/span>n-1位是0，相鄰1的對數(shù)不變，所以有：

DP[n][k][1] = DP[n-1][k][0] + DP[n-1][k-1][1];

并且初始狀態(tài)下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
     題意：給定一個凸多邊形，求它內(nèi)部所有的水平線段。

題解：從多邊形第一個點(diǎn)的y坐標(biāo)開始，遞減枚舉水平線段的y坐標(biāo)，分別和多邊形的n條邊進(jìn)行求交點(diǎn)；

1) 如果水平線段和多邊形某條邊共線，說明正好到了多邊形的邊緣，無須往下枚舉，跳出循環(huán)。

2) 如果水平線段和多邊形小于一個交點(diǎn)，那么當(dāng)y軸再次減小的時候，必然沒有交點(diǎn)，也無須繼續(xù)枚舉。

3) 否則，將左端點(diǎn)坐標(biāo)取上整x1，右端點(diǎn)取下整x2，如果x1 <= x2 將它插入到解集中。