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