2019.06.01 【NOIP提高組】模拟 A 組

T1：排序+線段樹維護。

首先按r從小到大排序。設f[i]表示從i開始最多往後跳多少步，那麼目前答案就是f[l~r]的最大值。

然後我們每次後移r時都要維護f。考慮在序列尾新加進來一個a[i]，那麼設j表示滿足a[j]>=a[i]的最大的j(j<=i)，則f[j+1~i]都會加1，其他不變。這個很好證。

用線段樹維護上述過程就好了。

總結：這題關鍵在于發現隻有j+1~i的f是變化的。

T2：費用流。

連邊方式如下：建立源點和彙點，源點向第一行的每一個點連流量為inf，費用為0的邊。（用(inf,0)表示，下同）。每一個(i,j)向自己連(1,a[i][j])，再向(i+1,j)和(i+1,j+1)連(1,0)。最後一行向彙點連(inf,0)。第一問做一遍費用流即可。

對于第二問，要把每個(i,j)連向自己的(1,a[i][j])改為(inf,a[i][j])。除此之外，還要建立一個超級源點連向源點，邊為(m,0)。這是為了保證路徑不超過m條。

總結：

費用流的做法：與最大流相似，不過每次增廣時要找費用和最小的增廣路徑(SPFA)，在增廣這條路上的最小流量。

T3：

這是一道偏數學的題。

因為關鍵的一個問題就是處理循環同構的情況，是以設f[d]表示最小循環節長度為d的串的個數。則ans=sum(f[d]/d)，因為每一個最小循環節為d的串都可以生成出d個循環同構的串。

接下來的任務就是求f了。設g[d]表示循環節長度為d的串的個數（注意不是“最小”循環節）。則f[d]=g[d]-sum(f[l])(l是d的因數且l<d)。這是因為如果一個串有l這個循環節，那麼它一定有d這個循環節，是以用g[d]減去所有f[l]求出的就是最小循環節為d的串的個數。

再加下來的任務就是求g了。設dp[i][j]表示長度為i，首位為1，後j位為0的串的個數。那麼轉移就是：

dp[i+1][0]+=dp[i][j](j<=k)    dp[i+1][j+1]+=dp[i][j] (j+1<=k)

原理就是讨論在目前長為i的串的最後加一個0還是1.

最後g[d]=sum(f[d][j]*(j+1))。因為每一個串後面都有j個0，每一個0有都可以轉到首位，是以總共有(j+1)種情況。

至此，這道就做完了。