2小時，3道編程題，還是挺有難度的。

編程題：

• 第一題

題意：有n組數(shù)據(jù)，每組數(shù)據(jù)給出m，j，k，表示參加比賽的人數(shù)（m=2的冪次，m<=2000）、觀眾想看的2個人的分?jǐn)?shù)排名。接著給出m個人的比賽順序（每輪比賽兩兩進(jìn)行，分?jǐn)?shù)高的人獲勝，直到最后誕生冠軍），m個人的分?jǐn)?shù)。如果在所有比賽中，分?jǐn)?shù)排第j的人和分?jǐn)?shù)排第k的人進(jìn)行了比賽，輸出YES，否則輸出NO。

題解：用隊列按題意模擬即可。

• 第二題

題意：給出s串、t串和正整數(shù)k（len(s)<2e5，len(t)<10，k<2e9）。求s中有多少子序列等于t，同時滿足子序列中所有相鄰字符的距離≤k，對1e9+7取模。

樣例：

• 輸入：soovood svd 2 輸出：1（s和v的距離為2）
• 輸入：soovood svd 1 輸出：0

題解：dp[i][j]表示，子序列結(jié)尾為t[i]，尾部間隔為j的子序列數(shù)量，轉(zhuǎn)移更新公式如下。在遍歷s串時，假如當(dāng)前字符c==t[i]，則使用第一條更新公式；每遍歷一個字符，之前子序列的間隔就會增加1，使用第二條更新公式。

??dp[i][0] = sum(dp[i-1][0].......dp[i-1][k])

??dp[i-1][j+1] = dp[i-1][j]

為了維護(hù)第一種轉(zhuǎn)移，需要區(qū)間求和和單點(diǎn)修改，可以使用線段樹或樹狀數(shù)組。為了維護(hù)第二種轉(zhuǎn)移，需要對dp數(shù)組進(jìn)行滑動處理。總復(fù)雜度為O(2e5*10*log)。

• 第三題

題意：給出n，m，k（均為≤1e6的正整數(shù)）。在二維坐標(biāo)系上，有(1，1)到(n，m)這n*m個點(diǎn)，每個點(diǎn)權(quán)值為橫坐標(biāo)與縱坐標(biāo)的乘積。求所有點(diǎn)的權(quán)值中第k大的值。

題解：二分答案。枚舉橫坐標(biāo)的值，除法得到縱坐標(biāo)的范圍，進(jìn)而得到比當(dāng)前mid大的值有多少。復(fù)雜度為O(n*log)。