2014 ACM/ICPC 北京邀請賽

http://acmicpc.info/archives/1703
http://www.cnblogs.com/kuangbin/p/3744817.html

Problem A. Matrix

Analysis:

【貪心】【遞歸】【生成鏈】
比較容易寫錯。
。。。不難歸納生成矩陣的性質。
1. 每行的數單調遞增。(。。。因為每個格子的數只有可能減小,且最大的數一定出現在行末尾)
2. 每行的 size 單調遞減。。。(因為下方的數,總是被後出現的較小的數頂下去的。。)

觀察一些數據。。。

4 3
2 1 3
1 2
1 4 

。。這個顯然是 4 2 1 3 。。。。

。。。考慮定位當前最大的數在 輸入序列 中的位置。。
。。為了得到逆序字典序最大。。我們希望它可以儘可能的往後。。
。。。我們從 4 開始。。向上剝開生成 4 的鏈 1-2-4 。。。但是發現此時 1 並不是其所在行的最末尾數。。。
。。因此 3 必須在這條鏈之後插入。。。。於是我們優先遞歸 3 。。。

於是就是兩個函數。。。
bool gao(); 從大到小枚舉沒有定位的數,將它們一次 bao() 開。。。
bool bao(int ii); 遞歸嘗試剝開 ii 。。C[ii] 表示 ii 所在的行號,-1 表示已經定位。。。
這樣不需要二分。。。總的複雜度是 O(n) 、。。。

Problem B. Beautiful Garden

Brief description:

。。。給定一組序列,修改最少的元素,使得該序列排序後是一個等差序列。

Analysis:

觀察一些數據。。
1 4 6 100 1000 10000
結果是。。
1 *2 *3 4 *5 6

。。。最終序列的首位置一定可以是原序列中的某個數(因為修改的任意性,你可以儘可能的放到後面。)
。。除此之外,還可以至少有一個數不修改。。。枚舉這兩個數。。。
。。。再枚舉公差 dd。。

(。。。注意這一步不需要枚舉所有可能的公差。。
。我們只需要枚舉這兩個數之間包含的數的個數。。
..。而這個值不會超過 n-2 。。)

注意:
。。long long ?(這種題目數據是 int 但是運算過程中有可能是 long long 的要尤為小心。。
dd = 0
n <= 2

Problem C. Champions League

Brief description:

。。。。這個題真是相當之贊。。。
。。不妨先來看一種 naive 的做法。。。。

。。。對每一個 group。。。枚舉 2^3 種情況。(考慮 0-1, 0-2, 0-3 、、。。)。。。
。。每次,得到 6 對數,對每對數取 max 得到這一天的最大得分。。。
。。排序後取前綴和。。就可以得到容量 1~66 個 物品。。。然後外圍 0/1 背包。。。

。。不幸的是。。這個做法是只能保證 group 內沒有衝突的。。。

1

。。。。這樣一來我們似乎需要加維來描述這種結對信息。。。。。但是稍作嘗試後我們發現這樣處理討論起來會過於複雜。。。
。。不如直接暴力 1<<6 狀態壓縮 DP 來的有效。。。。

。。。但是這樣會 TLE。。我們發現其實只需要保留最大的 6 個小組即可。
。。 (把多有 a[][] 塞到一個 vector 里從大到小排序比較。。)。。。
。。(因為我們只會取 6 天。。最差情況。如果每個 group 只轉播一場。。也只需要用到前 6 個小組。。)
。。。。

External link:

https://gist.github.com/lychees/e6ea2af33bac01288cc8