Codeforces Round #154 (Div. 2)

<a target="_blank" href="http://codeforces.com/contest/253">點選打開連結codeforce#154</a>

A

思路：水題

分析：題目要求‘B’和‘G’是交替出現，是以應該要注意判斷一下男生和女生的數量，然後是先B還是先G。

代碼：

<a target="_blank" href="http://codeforces.com/contest/253"></a>

B

分析：

1 先注意一個事實就是不能夠從後面和前面找，然後找到num[i]*2 &gt;= num[j]滿足了就認為是ans。

2 這種思想是錯誤的，正确的思路就是枚舉每一個可能的起始值，然後求目前要删除的個數，最後得到最少的值即可。

3 那麼我們就應該要先排序，然後是一個有序的序列，我們可以利用維護一個指針j，j是不用回溯的，因為随着i的增大，num[i]*2 &gt;= num[j]肯定是滿足的。是以複雜度完全可以接受。

C

思路：bfs 或 枚舉中間行

1 bfs的時候要注意判斷什麼時候不滿足

2 枚舉中間行的做法應該注意如果從r1-&gt;i-&gt;r2後現在沒有改變目前所在的列那麼應該是c1-&gt;c2，這個地方注意。

D 

題意：

1 給定一個n*m的矩陣每個格子有一個字母，現在要求有多少的子矩陣滿足四個角的字母相同并且這個子矩陣的字母的個數不大于k

1 首先利用o(n*m)的時間求出每個點到左上角這個矩陣字母'a'的個數

2 枚舉子矩陣的起始行和末尾行，如果直接枚舉列總的時間複雜度是O(n^2*m^2)效率肯定是不行的。我們需要把時間優化到O(x*n^2*m)，x是常數。

   我們利用vector記錄每個字母在每一行中的位置，然後對于同一行來說越後面總的子矩陣的'a'的個數越來越多，我們可以利用二分，最後總的時間複雜度為O(logm*n^2*m)

E

1 有一個列印機每秒鐘隻能列印一頁，現在有n個任務，每個任務有一個到來的時間t，以及這個任務要列印的頁數s，還有列印的優先級p

2 現在我們知道n-1任務的優先級，還有一個不知道，但是這個不知道的任務我們知道它完成列印的時間T，問這個不知道的認為的優先級

1 對于給定的優先級，我們可以求出所有的任務的結束時間。

2 我們已經知道了n-1個任務的優先級，那麼我們可以利用二分來求未知任務的優先級，然後根據結果進行判斷。

3 求所有任務的結束時間，我們隻要維護一個優先隊列即可。