歷年題目-雅禮訓練11-2晚上

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

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