今天是我們第一次參加多校聯合集訓的比賽，比賽開始前，我們還是按照以前的慣例進行分題，我看后面，小波波看前面，阿登看中間，大概十分鐘以后，我們看了下board,發現1001和1008已經有人過了（快得令人汗顏啊…）,于是我們馬上開始看1008，題意大概是給你N個數，這N個數只能是0或者是1，題目讓你求出不包含101的數字串有多少個。起初我們想用數學方法去計算，但是發現去重很麻煩，一時卡住了，后來小波波突然想到一個dp的方法，AC了。然后大家開始看1001，小波波想到如果所有的結點被擴展的時候花費的步數是偶數，那么輸出YES,否則NO,但是用DFS窮搜所有路徑的想法復雜度太高被我否決掉了，既然DFS不行，BFS行不行呢，其實結點只需要最多擴展兩次就行了，如果對原圖進行一下BFS復雜度大概只需要O(n)，我和阿登合計了一下，覺得可行，然后阿登就開始敲了。我和小波波開始看其他題目，我看了1007，小波波看1005，1005要求good sequences,推公式，既然要都相同或者都不相同，那么對M做一個全排列是滿足要求的，還有就是所有數是一樣的也滿足要求，我想了一下，也沒發現什么反例，這個時候阿登的代碼敲好了，但是一開始wa,我們把代碼發到阿登機器上再檢查一下，小波波先寫代碼，提交，不過一開始wa了，是算法還是特殊數據的問題？這個時候阿登說他找到了源程序里面的Bug,提交，過了。對于1005，我們發現一組特例，就是當n等于1, 其實對它做全排列和所有數字都一樣其實是一種情況，另外還有一種M等于2的情況也是特例，改了一下，也過了。我一直在考慮1007其實就是一個比較典型的行列轉換的問題，我記得以前在FOJ上做過，劉汝佳的書上也有提到，當時是用雙向廣搜，但是n,m<10,而這道題n,m<=100，用搜索肯定不行，怎么辦呢，把原矩陣的第一列全部處理成0，然后用枚舉目標矩陣中的每一列，再列進行排序，如果排序后兩個矩陣完全相等，輸出YES.這題敲代碼也確實比較快，但是交上去卻wa了，于是我和小波波一起逐行檢查，終于發現原來是一個<=寫成<了，囧??！改了之后就過了。。。無語。我在查代碼的時候，阿登看了1009，說是線段樹，于是我把代碼發到自己機器上，阿登開始寫線段樹，剛開始過這道題的人很少，就寥寥幾個，但是阿登非常確定是線段樹，那就敲吧。在我過了1007之后沒多少時間，1009也過了。這時比賽還有大概一個小時吧，我們想再開一題，于是就各自看了幾道AC率比較低的題目，阿登看了下最后一題說最后一題可以做，就是用鏈表模擬一下，但是對于取反操作，如果用單鏈表的話，一次取反操作復雜度是N，操作次數一多肯定超時，這題有點遺憾，我當時再看1003，等我看完最后一題，我覺得其實可以用雙向鏈表的，后來大家也覺得雙向鏈應該是正解，但是卻沒有時間了，只能賽后再研究下了.