Codeforces Round #153 (Div. 2)

<a target="_blank" href="http://codeforces.com/contest/252">點選打開連結cf #153</a>

A

思路：暴力

分析：

1 題目給定n個數 n&lt;=100，要求一個區間内做^能夠得到的最大值

2 n最大為100，暴力枚舉區間即可。

代碼：

B

法一

1 題目問能否找到兩個不同的位置i , j.使得i 和 j交換後序列不是有序的。如果找不到輸出-1

2 很明顯n&lt;=2時是不可能找到的，輸出-1；還有一中特殊的情況就是num[1]=num[2]=...=num[n]，這種也是輸出-1.

3 接下來就是暴力枚舉i個j的值，然後找到滿足的即可。

4 注意如果沒有找到應該輸出-1，這裡不能漏了。

法二

思路：分類模拟

1 題目要求找到兩個位置交換這兩個位置的數，使得序列不是單調的。如果沒有輸出-1

2 如果n&lt;=2，肯定是不可能找到滿足的位置的。

3 那麼我們可以通過分析序列總共有幾個不同的數字。

   如果隻有1個就是類似1 1 1...這樣的肯定找不到輸出-1；

   如果是2個那麼我們一個for循環找到num[i] != num[i-1]，然後交換它判斷是否滿足即可。2個的情況可能會有不滿足情況，如果都不滿足那麼就輸出-1；

   如果是大于等于3個，那麼我們隻要找出三個不同的數然後交換。但是這三個數原先的排列情況有4種(/，/\，\，\/ 表示增減)。那麼我們隻要去判斷最大值的位置就可以。有三個不同的數那麼肯定是可以找到兩個位置的。

C

思路：1 枚舉起點，維護一個末尾指針。2 另外一種做法是把維護的指針 j 改成二分查找

1 題目給定一個n個數的有序序列，要求找到最多的方法滿足題目要求。

2 我們知道一個有序的序列是很特殊的，假設現在我們的起點是num[i]，那麼我們維護一個指針j，使得num[j]-num[i] &gt; d。那麼我們知道[i,j)就有j-i-1個數，是以知道了起點那麼滿足的個數就是C(j-i-1,2){組合公式}。那麼我們接下來起點變成了num[i+1]，這個時候正常的做法是j 從 i+2開始，但是由于這個序列是有序的序列有num[i]&gt;num[i-1]，那麼肯定 j 之前的數都滿足num[j-1]-num[i+1] &lt;= d，是以 j 不用回溯這樣就不是O(n^2)而是接近O(n)的複雜度。

3 注意：假設int n = 100000 ， long long  ans = n*(n-1)*(n-2)；這個運算實際是得不到ans的，由于n是int,是以運算的時候超出了int範圍，是以得到的ans是錯誤的。應該注意ans是long long 的情況下 n 也要改為 long long.  

4 對于一個有序的序列進行二分的時候是可以利用STL的lower_bound() 和 upper_bound()函數的。

D

1 題目的意思給定一個序列p初始為1,2,3....n。再給定一個序列q和一個序列s，做k次的變換

2 每一次的變換有兩種可能，第一種是生成一個新的序列p且newp[i] = p[q[i]]，第二種是生成一個新的序列p且newp[q[i]] = p[i]

3 現在題目要問的是把初始化的序列p做k次的變換，能否前k-1次都沒有出現序列s，最後一次序列正好為s

4 根據第2點，我們可以推出第一種變換和第二種變換是逆的。也就是說做一次的第一種和一次的第二種變換得到的原來的序列。

5 如果我們執行m1次第一種變換可以使得序列p等于序列s，那麼我們先執行(k - m1) / 2次的(第一種變換、第二種變換)組合，再執行m1次第一種變換 即可。

   如果我們執行m2次 第二種變換可以使得序列p等于序列s，那麼我們先執行(k - m2) / 2次的(第一種變換、第二種變換)組合，再執行m2次第二種變換即可。

   是以隻要求出其中的m1、m2再判斷一下k - m1，k - m2是否是偶數就行了。