上周日，上午我沒吃早飯參加了 10:30 ～ 12:00 的 leetcode 周賽，下午又沒吃午飯參加了 12:00 ～ 17:00 codeforces 的 202011 月賽。
晚上 19:00 的牛客練習賽實在是做不動了，遂放棄。
這次 codeforces 的月賽相當殘暴，出了 13 道題。
平常 acm 賽制都是 3 個人一起 5 個小時做 13 道題的。
這個人賽做 13 道題，時間變得特別緊湊。
下面就來看看這 13 道題吧。
A. Games on c++題意：給 10 個求三個數字最大值的代碼，問哪些代碼是正確的。
思路：
1）調用系統的最大值函數，正確。
2）調用系統的最小值函數，錯誤。
3）調用系統的最大值函數，先求後兩個數字的最大值，然後再與第一個數求最大值，正確。
4）自己實現最大值函數，最大值通過第一個參數返回，正確。
5）自己實現最小值函數，錯誤。
6）函數不是引用，永遠返回第一個數字的值，錯誤。
7）實現的最小值函數，錯誤。
8）實現的最大值函數，正確。
9）函數不是引用，永遠返回第一個數字的值，錯誤。
10）自己實現最大值函數，正確。
當然，一種簡單的方法是使用 lamba 表達式包裝 10 個函數，使用3 個數據來測試是否符合預期，符合預期了就滿足要求。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/A.cc
題意：給兩個數組，數字互不相同。
分別在兩個數組取一個數字，形成一對數字。求一對數字異或後，值依舊在這兩個數組內方案數的奇偶性。
思路：暴力的複雜度是O(n^2)，會超時。
我本想使用字典樹來優化，後來發現極端情況下字典樹依舊會超時。
賽後發現這道題想複雜了。
題目是求組數的奇偶性的，那完全可以分析數組來找規律。
假設 a在 A 序列，b和c在 B 序列 ，存在a^b=c, 則肯定存在a^c=b。
由此可以得到，每次可以得到兩組答案，最終得到的答案也是偶數個。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/B.cc
題意：給一個圖，問是否可以通過操作聯通圖上的兩點，使得圖的權值等於目標權值。
操作總結下就是可以選一個點加一，另一個點減一。
由此可以得到所有權值之和不變。
如果目標權值之和與輸入的相等，那麼肯定可以到達目標，否則不可到達。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/C.cc
題意：通過最小交換相鄰字母的次數，使得字符串變成回文串。
沒思路，不會做。
E. 串串題意：給一些字符，問可以構造的定長字符串中，不同的回文子串數量最少的字符串個數。
題目有點繞。
1、構造一個定長字符串。
2、構造的字符串會存在若干回文子串，最少的回文子串個數假設為 K。
3、問可以構造出回文子串為 K 的字符串有多少個。
分別枚舉計算前 5 個可以發現規律。
長度為 1 時，任意組合得到的回文子串都是 1 個。共有 62 種情況。
長度為 2 時，任意組合得到的回文子串都是 2 個。共有 62 * 62 種情況。
長度為 3 時，任意組合得到的回文子串都是 3 個。共有 62 * 62 * 62 種情況。
長度為 4 時，可以組合出回文子串的最少是 3 個，此時是染色問題，左右不相等即可，即重複的abcabcabc...。
原始碼:
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/E.cc
題意：給一個圖，問可以拆分為多少個獨立的鏈路，來覆蓋所有的頂點，並使鏈路的長度和最小。
思路：據說是歐拉路徑問題。
G. 吃吃吃題意：小 A上學期間每周的七天吃不同的炒菜，周幾吃什麼菜都固定。
但是過節日的時候會破例換一個菜吃。
上學時間有上學期和下學期。
問指定日期範圍內，小 A每個菜都吃了多少次。
思路：模擬題，一天天判斷即可。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/G.cc
題意：走樓梯問題，每次最多可以走 k 階樓梯，k 不大於 10。
問走 n 階樓梯的方案數，n 最大是 10^9。
思路：經典的動態規劃問題。
但是 n 比較大，需要使用矩陣冪來優化。
為什麼可以使用矩陣冪優化呢？
因為矩陣相乘滿足結合律。
比如狀態轉移方程簡化為 f(2) = f(1) * k。
那麼 f(n) = f(1) * k^ (n-1)。
這樣，本來是 O(n) 的複雜度，轉化為 O(log(n))的複雜度了。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/H.cc
題意：給一個數組，問是否可以挑選一個集合，使得集合裡的任意個元素異或不為 0。
思路：據說是線性基問題，都沒聽過這個詞。
十、J. 後綴自動機題意：給若干個不同的字符串。
每個字符串可以使用自己的某個前綴代替，但是前綴不能重複。
問所有前綴長度之和的最小值。
思路：一開始以為排序或者字典樹貪心即可。
後來發現有反例，比如ea erb era，最優前綴是ea e er。
標準的做法是枚舉下一個前綴選擇哪個字母，所有裡面選擇最優值。
例如還是上面那個反例，枚舉e分配給ea前綴或者er前綴，哪個更優。
原始碼周末會提供。
十一、K. 校門外的樹題意：一排樹，只能從一端開始砍樹。
砍樹可能增加金錢，也可能降低金錢。
允許金錢為負，問最大金錢是多少？
思路：最大前綴和，掃描一遍即可。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/K.cc
題意：求公式f(n) = f(n-1) + 2 *f(n-2)
思路：n 比較小，循環暴力求即可。
原始碼：
https://github.com/tiankonguse/ACM/blob/master/codeforces/gym/304511/M.cc
這次比賽大部分題其實都不難，但是作為個人賽，題目太多了，五個小時根本做不完。
平常團隊賽三個人也是做這麼多題，現在一個人，算是考察基本功的時候到了，全程敲代碼。
加油，算法人。
《完》
-EOF-
題圖：來自朋友圈。
上篇文章：leetcode 第 216 場算法比賽
推薦：初級樹狀數組 leetcode 練習題
長按二維碼，一起成長學習
▲ 長按關注，天天成長
覺得有幫助可以點擊好看與轉發，謝謝！