歷年題目-雅禮訓(xùn)練11-2晚上

solution怎樣更有力氣討(che)論(dan)時(shí)間大家有沒有收到辣雞出題人送的溫暖??！你看出題人多有良心：部分分辣么多難度辣么小不卡常數(shù)據(jù)范圍提醒選手特判邊界Task1m=1由于此部分分低于普及組難度，不再講述Task2n,m≤104考慮第i天，先處理香港記者染白的區(qū)間。令dp[i]表示1~i全染白至少操作幾次。則dp[i]=dp[i-1]（i為白點(diǎn)）或dp[i-x]+1（i為黑點(diǎn)）時(shí)間復(fù)雜度O(nm)Task3x=0二分答案，那么只要看香港記者染白的區(qū)間是否將墻完全覆蓋即可。將區(qū)間按左端點(diǎn)排序，比較區(qū)間的左端點(diǎn)與前一個(gè)區(qū)間的右端點(diǎn)即可。正解其實(shí)已經(jīng)很明了了。在task3中，如果當(dāng)前區(qū)間的左端點(diǎn)小于上一個(gè)區(qū)間的右端點(diǎn)，就直接退出?，F(xiàn)在只要從上一個(gè)區(qū)間的右端點(diǎn)+1開始凃，一直涂到≥當(dāng)前區(qū)間左端點(diǎn)即可。注意到一次可能直接把整一段覆蓋了，那么下一次就要從當(dāng)前涂到的地方開始。怎樣學(xué)習(xí)哲♂學(xué)討(tu)論(cao)時(shí)間這題連出題人都感覺很爛。其實(shí)是一道多校的弱化版。此外OI大師抖兒提出這道題很像APIO2016賽艇。向大家致以深深的歉意……Task1n≤10直接暴力枚舉即可。時(shí)間復(fù)雜度O(m!)Task2n≤1000令dp[i][j]表示最后一個(gè)選擇為i,j的方案總數(shù)。轉(zhuǎn)移十分顯然。利用前綴和優(yōu)化之即可。Task3p=0顯然答案是C(n,m)由于模數(shù)是個(gè)較小的質(zhì)數(shù)，可以套用lucas定理。注意線性求逆元。正解令dp[i]表示僅經(jīng)過i這個(gè)空點(diǎn)的方案總數(shù)。那么dp[i]=起始點(diǎn)到i的方案數(shù)-dp[j]*j到i的方案數(shù)。其中j是所有在i左上方的空點(diǎn)。從一點(diǎn)到另一點(diǎn)的方案數(shù)，在task3中已經(jīng)計(jì)算過了，不再贅述。但是起始點(diǎn)和終止點(diǎn)都是不確定的，不難發(fā)現(xiàn)，其實(shí)相當(dāng)于強(qiáng)制起始點(diǎn)在(0,0)，終止點(diǎn)在(n+1,m+1)還有一種方法，即對(duì)所有空點(diǎn)離散化，然后用類似task2中的轉(zhuǎn)移也可以解決怎樣打好隔膜討(che)論(dan)時(shí)間

感覺是idea最好的一題了。但是很水啊有木有！部分分許許多多啊某木有！出題人很良心啊有木有！Task1m=1從1出發(fā)，路徑為1→i→j→n→j→i，耗時(shí)n-1+n-j從1出發(fā)，路徑為1→i→j→i→j→n，耗時(shí)n-1+j-i從n出發(fā)，路徑為n→j→i→1→i→j，耗時(shí)n-1+i-1三者取最小值即可Task2m=2從1出發(fā)，路徑為1→i→j→x→i→x→y→j→y→n，耗時(shí)n-1+x-i+y-j從1出發(fā)，路徑為1→i→j→x→i→x→y→n→y→j，耗時(shí)n-1+x-i+n-y從i出發(fā)，路徑為i→x→j→y→n→y→x→j→i→1，耗時(shí)n-1+j-x+n-y從y出發(fā)，路徑為y→x→j→x→i→1→i→j→y→n，耗時(shí)n-1+i-1+j-x從x出發(fā)，路徑為x→i→1→i→j→x→y→n→y→j，耗時(shí)n-1+i-1+n-y從x出發(fā)，路徑為x→i→1→i→j→x→y→j→y→n，耗時(shí)n-1+i-1+y-j取最小值即可p=1時(shí)，選擇i→x或j→y或x→j的傳送門，答案參見Task1不相交的情況同理討論即可Task3m≤8暴力枚舉進(jìn)入傳送門的順序以及進(jìn)入傳送門的端點(diǎn)，將走過的航線標(biāo)記，再看看有沒有沒走完的航線，走完即可。時(shí)間復(fù)雜度m!*2m*mTask4m≤2000發(fā)現(xiàn)問題和找歐拉路十分類似。一個(gè)圖存在歐拉路當(dāng)且僅當(dāng)存在兩個(gè)奇點(diǎn)（度數(shù)為奇數(shù)的點(diǎn)）或不存在奇點(diǎn)。問題等價(jià)于給定一個(gè)圖，刪除一對(duì)奇點(diǎn)的代價(jià)為它們的距離，求使圖存在歐拉路的最小代價(jià)。1和n原先是奇點(diǎn)，其余的點(diǎn)為偶點(diǎn)。一個(gè)傳送門會(huì)使連接的點(diǎn)性質(zhì)發(fā)生變化，即奇點(diǎn)變偶點(diǎn)，偶點(diǎn)變奇點(diǎn)。Task5m≤2000不難發(fā)現(xiàn)最終所有的奇點(diǎn)都排成了一行，消去i和j的代價(jià)為j-i。顯然消去相鄰的兩個(gè)奇點(diǎn)是最優(yōu)的。那么問題轉(zhuǎn)化為：給定n個(gè)a[i]，選出k個(gè)a[i]滿足兩兩不相鄰且和最小。令dp[i][j]表示前i個(gè)數(shù)選了j個(gè)的最小代價(jià)。dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+a[i])正解考慮一個(gè)錯(cuò)誤的貪心：每次選擇最小的a[i]，然后刪去a[i-1]和a[i+1]。但是如果要選擇兩個(gè)，可能選擇a[i-1]和a[i+1]是更優(yōu)的，因此每次貪心有可能會(huì)“反悔”，我們考慮維護(hù)這個(gè)“反悔”操作。每次選一個(gè)最小的a[i]，然后刪去a[i-1]和a[i+1]，a[i]的權(quán)值變成a[i-1]+a[i+1]-a