先聲明一下，如果你是初學者，你可能會看不懂其中的一些東西，原因是你的知識點以及技巧沒有跟上，我會盡量寫得詳細一點，如果還有不懂，歡迎留言。

玩具謎題 toy

知識點

模擬

分析

可以發(fā)現(xiàn)，本題就是根據(jù)要求在環(huán)上順時針或者逆時針走動，那么假設(shè)當前的位置是 $p$p，那么逆時針走 $x$x 個到達的位置是 $(p - 1 x) \bmod n 1$(p?1 x)modn 1，順時針走 $x$x 個到達的位置是 $(p - 1 - x) \bmod n 1$(p?1?x)modn 1。模擬每一次的指令，判斷每次是走順時針還是逆時針即可。

實現(xiàn)上要注意，C 中對于模運算的定義與數(shù)學中的模運算是不同的，我們知道在數(shù)學上 $a \bmod b = a - b\cdot\lfloor \frac a b\rfloor$amodb=a?b???b??a???，問題就在于 $\lfloor\frac a b\rfloor$??b??a??? 的計算上。在大部分編譯器中，兩個 int 相除，是直接丟棄小數(shù)位得到答案的，這就導致了在 C 中兩個 int 相除并非總是得到 $\lfloor\frac a b\rfloor$??b??a???（例如 $\frac {-3} 2 = -1$?2???3??=?1），所以 $a$a 為負數(shù)的情況下，取模會存在問題，$a \bmod b$amodb 不一定能夠得到一個非負整數(shù)，但是我們可以保證這個數(shù)在 $(-\vert b\vert, \vert b\vert)$(?∣b∣,∣b∣) 內(nèi)，在所以實際需要取模的時候，采用 $((a \bmod b) b) \bmod b$((amodb) b)modb 來得到非負整數(shù)。

代碼

天天愛跑步 running

考點

DFS，LCA（最近公共祖先），差分標記，前綴和

分析

對于 NOIP 初學者來說，這個題在考場上是比較沒有辦法 A 掉的，但是這并不妨礙我們拿到暴力分。

25 分

對于前 5 個測試點，$n, m\le 1000$n,m≤1000。

可以考慮對于每一個人 $(u, v)$(u,v)，都使用 BFS 找出 $u \rightarrow v$u→v 的路徑，然后更新路徑上有滿足條件的點即可。至于找出路徑的方法，只需要從 $u$u 開始 BFS，并且在 BFS 中從 $a$a 擴展到 $b$b 時，記錄 $a$a 的前繼為 $b$b，最后我們從 $v$v 開始，不斷地找前繼，最終到 $u$u，這樣就還原出了路徑，你可能還需要記錄一個到點 $v$v 的距離來幫助判斷路徑上的點是否滿足條件。

復雜度：$O(n^2)$O(n?2??)。

40 分

接下來 3 個測試點，$n, m \le {10}^5$n,m≤10?5??，形成一條鏈。

本題有 2s 的時限，大概能夠承受 ${10}^8$10?8?? 的運算量，如果使用 25 分算法，運算量將達到 ${10}^{10}$10?10??，絕對無法承受。所以我們不能采用還原路徑的方法。

由于鏈上的點依次是 ，而題目中的路徑有從編號小的點走到編號大的點或者從編號大的點走到編號小的點。我們將這兩種路徑分開考慮，先考慮從編號小的點走到編號大的點 $(u, v)(u\le v)$(u,v)(u≤v)。
對于 $(u, v)$(u,v)，如果路徑上的點 $i(u\le i\le v)$i(u≤i≤v) 要滿足條件的話，必然是滿足 $w_i = i - u$w?i??=i?u，我們不妨設(shè) ${w'}_i = w_i - i$w?′???i??=w?i???i，那么現(xiàn)在的條件轉(zhuǎn)化為了 ${w'}_i = -u$w?′???i??=?u，也就是說，路徑上的點 $i$i 答案 1 的充分必要條件是滿足 ${w'}_i$w?′???i?? 等于一個定值。

現(xiàn)在問題轉(zhuǎn)化成了支持兩種操作：

1. 將一段鏈上的每個點插入一個數(shù)。
2. 查詢點 $i$i 上有多少個數(shù)是 ${w'}_i$w?′???i??。

我們考慮使用差分化標記實現(xiàn)，這個思想在 NOIP 2012 借教室 出現(xiàn)過。
對于將鏈上的 $[l, r)$[l,r) 同時插入一個數(shù) $v$v，差分后轉(zhuǎn)化為在 $l$l 位置插入一個 $(v, 1)$(v,1)（表示增加一個 $v$v），在 $r$r 位置插入一個 $(v, -1)$(v,?1)（表示刪除一個 $v$v）。由于差分的逆運算是前綴和，我們順序遍歷這條鏈，維護 $\mathrm{cnt}_v$cnt?v?? 為數(shù) $v$v 出現(xiàn)的次數(shù)（由于 $i$i 有負數(shù)，所以我們考慮將這個數(shù)組向右平移 $n$n 個單位來方便存儲），每遍歷到一個點 $i$i，我們就處理它上面所有的標記 $(v, t)$(v,t)，將 $\mathrm{cnt}_v$cnt?v?? 加上 $t$t。這樣遍歷到每個點的時候，$\mathrm{cnt}_v$cnt?v?? 就是在它上面數(shù) $v$v 的出現(xiàn)次數(shù)。

對于反過來的路徑 $(u, v)$(u,v)，同理可以發(fā)現(xiàn)點 $i(v\le i\le u)$i(v≤i≤u) 答案 1 的充分必要條件是 $w_i = u - i$w?i??=u?i，設(shè) ${w''}_i = w - (n - i)$w?′′???i??=w?(n?i)，那么條件轉(zhuǎn)化為 ${w''}_i = u - n$w?′′???i??=u?n，也是一個常數(shù)，可以用類似的方法處理。

復雜度：$O(n m)$O(n m)。這個做法比較重要，對于初學者建議實現(xiàn)這個程序。

樹鏈剖分

剛剛我們得出了鏈上的算法，樹鏈剖分可以讓我們將樹剖分成鏈，這樣樹上的問題就可以轉(zhuǎn)化為鏈上的問題，套用鏈上的算法即可。每條路徑產(chǎn)生 $O(\log n)$O(logn) 個標記，處理每條路徑的復雜度也是 $O(\log n)$O(logn)，最后結(jié)算標記的復雜度 $O(n\log n)$O(nlogn)，所以總復雜度 $O(n\log n)$O(nlogn)。依據(jù)實現(xiàn)的情況，得到 95 或 100 分。

100 分

NOIP 顯然不會考樹鏈剖分，這題有更優(yōu)美的解法。我們首先求出每條路徑的 LCA，使用 Tarjan 算法 在 $O(n m)$O(n m) 的時間內(nèi)預處理出 LCA。對于每一條路徑，我們拆成直上直下的兩條鏈（如果本身就是這種鏈就不拆），設(shè) $d_i$d?i?? 為 $i$i 點的深度。我們考慮鏈 $u \rightarrow v$u→v，對于向下的鏈，路徑上滿足條件的點 $i$i 必須滿足 $d_i - d_u = w_i$d?i???d?u??=w?i??，即 $w_i - d_i$w?i???d?i?? 是一個定值。對于向上的鏈，有 $d_u - d_i = w_i$d?u???d?i??=w?i??，即 $w_i d_i$w?i?? d?i?? 是一個定值，問題同樣轉(zhuǎn)化為了支持兩種操作（對于兩種鏈分別考慮，這里只說了第一種鏈）：

1. 將一段路徑（沒有彎折）上的每個點插入一個數(shù)。
2. 查詢點 $i$i 上有多少個數(shù)是 ${w'}_i$w?′???i??。

如果在路徑 $u\rightarrow v(d_u \le d_v)$u→v(d?u??≤d?v??) 上插入一個數(shù) $x$x，可以差分轉(zhuǎn)化為在 $v$v 這個地方插入一個 $x$x，在 $\mathrm{fa}_u$fa?u?? 這個地方刪除一個數(shù) $x$x，則點 $i$i 上的數(shù)就是其子樹的和（一個常用技巧，建議畫圖驗證）。

顯然對于每一個點都求一次子樹是 $O(n^2)$O(n?2??) 的，考慮如何快速計算。我們可以弄出樹的 DFS 序，對于一棵子樹，它在 DFS 序中必然是連續(xù)的一段。那么對于一個點 $i$i，我們只需要查詢它的子樹代表的一段連續(xù)的區(qū)間中有多少個數(shù) ${w'}_i$w?′???i??。假設(shè)其子樹的區(qū)間為 $[l, r]$[l,r]，$T_{j, v}$T?j,v?? 為 $[0, r]$[0,r] 中有多少個 $v$v，那么 $i$i 的答案等于 $T_{r, {w'}_i} - T_{l - 1, {w'}_i}$T?r,w?′???i?????T?l?1,w?′???i????。我們先算出所有點的 $l$l 和 $r$r，然后離線，順序遍歷 DFS 序列來結(jié)算每個前綴和。這一步比較抽象，大體的思想就是每遍歷到一個位置 $i$i，結(jié)算所有包含 $T_i$T?i?? 項的區(qū)間，由于只有 $2n$2n 個區(qū)間，所以結(jié)算的復雜度是 $O(n m)$O(n m) 的。

具體的實現(xiàn)見代碼，復雜度：$O(n m)$O(n m)。

代碼

樹鏈剖分

正解

吐槽

考試的時候?qū)懥藗€樹鏈剖分，考完以后寫了個線性做法，mdzz 跑的時間居然一樣。

換教室 classroom

知識點

數(shù)學期望，動態(tài)規(guī)劃，最短路

分析

首先有 $v\le 300$v≤300，使用 floyd 算法求出兩兩點對之間的最短路。接著可以發(fā)現(xiàn)，這是一個經(jīng)典的序列 DP 的模型，每個點有選或者不選兩種決策，那么根據(jù)期望的線性性，容易發(fā)現(xiàn)每次 DP 只與最后兩個選不選有關(guān)，考慮 $dp_{i, j, k}$dp?i,j,k?? 為到第 $i$i 個點，已經(jīng)選了 $j$j 個，$k$k 表示第 $i$i 個點是否選擇換教室，那么轉(zhuǎn)移就是根據(jù)后兩個是否選擇更換，來分情況討論（設(shè) $p_i$p?i?? 為更換成功的概率，$c_i$c?i?? 為不換的教室，$d_i$d?i?? 為換的教室，$G_{i, j}$G?i,j?? 為 $i$i 與 $j$j 之間的最短路）：

如果點 $i$i 不選，那么根據(jù)上一個選不選來計算期望（期望的線性告訴我們可以這樣做）。

如果點 $i$i 選，也是根據(jù)上一個選不選來計算期望，第二個式子會比較麻煩，有四種情況。

代碼