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