這里是熱愛OI的予惜捏（冒頭）本次專欄打算講一講CSP-S復(fù)賽的真題。

首先來看T1：

可以發(fā)現(xiàn)這道題n ≤ 2500，我們可以枚舉起點使用廣搜求出任意兩個點之間的最短路，如果兩點之間最短路≤k+1，那么它們就可以連續(xù)出現(xiàn)在行程中。

40分做法：由于n≤20，直接使用4層循環(huán)枚舉A、B、C、D的下標(biāo)，再驗證是否滿足要求；

70分做法：考慮只枚舉A、B、C，其實D的值可以使用貪心法求解，D到C的距離≤k+1，并且D到1號點的距離≤k+1，那么D一定是滿足條件的點中權(quán)值最大的那個。

這里需要注意的是：權(quán)值最大的點也可能是A或B中的一個，由于景點不能重復(fù)，所以我們需要選權(quán)值第二大的點，但是權(quán)值第二大的點也有可能是A或B中的一個，這種情況我們需要選擇權(quán)值第三大的點。

因此我們需要預(yù)處理，對于每個點i，需要求出到i點和1號點的距離都≤k+1的點里面，權(quán)值的第一大、第二大、第三大，然后再三重循環(huán)枚舉A、B、C點，D點就是C點的前三大點中的一個；

100分做法：預(yù)處理的部分還是不變，我們可以發(fā)現(xiàn)A點的性質(zhì)和D點是非常類似的，A到B點和A到1號點的距離都≤k+1。我們可以只枚舉B點和C點，可以發(fā)現(xiàn)A點必須是B點前三大點中的一個，D點必須是C點前三大點中的一個（需要考慮到B點前三大點和C點前三大點之間考慮會重合）。

時間復(fù)雜度為O(n2)；

T2：

首先使用貪心法思考問題，如果第一個人選的數(shù)字已經(jīng)確定了，那么第二個人肯定會遍歷整個區(qū)間，選出其中乘積最小的對應(yīng)數(shù)字。對于第一個人來說，他選數(shù)的時候其實可以預(yù)見第二個人選的數(shù)字。

40分做法：直接枚舉第一個人選的數(shù)字，然后遍歷區(qū)間求出第二個人選的數(shù)字，實質(zhì)是選每行最小值中的最大值，時間復(fù)雜度為O(nmq)。當(dāng)數(shù)據(jù)滿足特殊性質(zhì)2時，時間復(fù)雜度為O(nq)；

65分做法：再考慮到特殊條件1：Ai,Bi>0，不管第一個人選的數(shù)字是什么，第二個人選的數(shù)字一定是區(qū)間中最小的數(shù)字。所以第一個人一定會選區(qū)間中最大的數(shù)字。我們可以使用ST表或者線段樹維護A數(shù)組的區(qū)間最大值和B數(shù)組的區(qū)間最小值，然后對于滿足特殊條件1的點，答案一定是A數(shù)組指定區(qū)間的最大值×B數(shù)組指定區(qū)間的最小值；

100分做法：按照上述討論，如果Ai和Bi都大于0，那么取的數(shù)字一定是區(qū)間最值。拓展上述結(jié)論會發(fā)現(xiàn)：如果第一個人取的是正數(shù)，第二個人一定會取區(qū)間的最小值；如果第一個人取的是負(fù)數(shù)，第二個人一定會取區(qū)間最大值。在此基礎(chǔ)上考慮第一個人的取值

1.如果他取正數(shù)：當(dāng)?shù)诙€人取的區(qū)間最小值是正數(shù)時，第一個人應(yīng)該取最大的正數(shù)；如果第二個人取的區(qū)間最小值是負(fù)數(shù)時，第一個人應(yīng)該取最小的正數(shù)（或者有0取0）;

2.如果他取負(fù)數(shù)：當(dāng)?shù)诙€人取的區(qū)間最大值是正數(shù)時，第一個人應(yīng)該取最小的負(fù)數(shù)；如果第二個人取的區(qū)間最小值是負(fù)數(shù)時，第一個人應(yīng)該取最小的負(fù)數(shù)。

綜上，第一個人只會取區(qū)間中四種數(shù)中的一個：最小的負(fù)數(shù)、最大的負(fù)數(shù)、最小的非負(fù)數(shù)、最大的非負(fù)數(shù)；而第二個人只會根據(jù)第一個數(shù)字的符號取區(qū)間的最大值或最小值。使用ST表，維護A數(shù)組的區(qū)間最大負(fù)數(shù)、區(qū)間最小負(fù)數(shù)、區(qū)間最大正數(shù)、區(qū)間最小非負(fù)數(shù)，再維護B數(shù)組的區(qū)間最大和區(qū)間最小，然后每輪游戲只有四種方案，求出其中最大值就能得出這一輪的答案了。

時間復(fù)雜度為O(nlogn)；

T3：

首先要把描寫得很復(fù)雜的反攻解釋出來：需要從每個點出發(fā)，都能進行無限次蟲洞穿梭，其實是要求從任意點出發(fā)能走到環(huán)上。每個點只能有一個從該點出發(fā)的蟲洞，其實是圖上每個點的出度為1。根據(jù)圖論知識，有向圖中每個點的出度為1，一定會形成環(huán)，并且所有點都能走到環(huán)上，因此反攻當(dāng)且僅當(dāng)所有點的出度為1。

40分做法：先存下每個點的初始鄰居，每次修改時直接修改鄰接矩陣，然后在修改過程中維護每個點的出度，如果n個點的出度都是1，輸出YES，否則輸出NO；時間復(fù)雜度O(nq)；

60分做法：如果沒有4號操作，那么我們可以使用set對每個點維護兩個集合，分別存儲完好的入邊的起點和被摧毀的入邊的起點。每次1、2號操作時，可以在v對應(yīng)集合中刪除u，并且把u加入另一個集合，同時修改u的出度。在3號操作中，直接枚舉u點的所有完好的入邊，執(zhí)行摧毀操作，并維護對應(yīng)起點的出度。如果一條邊被摧毀兩次，說明它至少被修復(fù)了一次，由于最多能修復(fù)不超過q條邊，所以整個程序最多摧毀m+q條邊，再加上set的復(fù)雜度，時間復(fù)雜度為O((m+q)logn)；

100分做法：既然考慮使用set對每個點i分別維護好的蟲洞的起點集合S[i]和壞的蟲洞的起點集合T[i]，但是在4號操作時，需要枚舉set中的所有點，把它們從壞集合移動到好集合，因此超時（雖然set合并可以做到O(logn)，但是修改起點的入度必須枚舉）。

可以考慮使用Hash法存儲集合，合并和修改時時候都是O(1)的。

設(shè)定一個足夠大的質(zhì)數(shù)P，令pi = p的i次方，假設(shè)有一個集合為{1,3,4,5}，那么可以對應(yīng)Hash值為p1+p3+p4+p5（還需要按照指定模數(shù)進行模運算，為了便于描述以下均省略），這個值是唯一對應(yīng)的。如果我們刪除3到i的邊，只需要讓Hash值減去p3；如果我們修復(fù)7到i的邊，只需要讓Hash值加上p7，非常方便。

對于3、4號操作，如果點i的好的蟲洞的起點集合對應(yīng)Hash值為s[i]，壞的蟲洞的起點集合對應(yīng)Hash值為t[i]。3號操作執(zhí)行后，好集合的所有邊都要移入壞集合，此時點i的新的Hash值s'[i]=0,t'[i]=s[i]+t[i]；4號操作執(zhí)行后，壞集合的所有邊都要移入好集合，此時點i的新的Hash值s'[i]=s[i]+t[i],t'[i]=0。引入Hash值的最終目的其實是避免記錄出度的工作，我們可以存儲所有蟲洞的起點集合（可重復(fù)集合），這個集合是一個大小為n的不重復(fù)集合，此時答案就是YES。求出初始狀態(tài)下，所有蟲洞的起點集合對應(yīng)的Hash值Q，比如如果初始集合{1,1,2,3,5,5,5}，那么Q= 2p1+p2+p3+3p5。如果Q=p1+p2+?+pn，此時答案就是YES，否則答案是NO。

對于1號操作，Q-=pu；對于2號操作，Q-=s[u]；對于3號操作，Q+=pu；對于4號操作，Q+=t[u]。每次操作對Q的維護都是O(1)的。

時間復(fù)雜度為O(n+m+q)；

最后來看T4：

觀察數(shù)據(jù)可以發(fā)現(xiàn)1≤k≤3，由于k的值很少，肯定對做法有影響，可以分別考慮不同的情況。當(dāng)k=1時，路徑中不能跳過任何一個點，所有只能直接從起點走到終點。當(dāng)k=2時，不難想到我們停留過的點都是在起點到終點的簡單路徑上的。因為如果想規(guī)避掉路徑上下一個點u時，我拐到這個點的某個兒子v上，繼續(xù)走還是只能走到u的下一個點w，而從當(dāng)前點可以直接走到w，不需要走到v。當(dāng)k=3時，類似于上述情況，走到下一個點的兒子或者孫子都是沒有意義的，我們停留過的點只能是起點到終點的簡單路徑中的點或者這些點的鄰接點。

8分做法：使用深搜，每次直接枚舉下一個點，最好先預(yù)處理存儲距離小于等于k的點；

24分做法：當(dāng)k=1時，從起點到終點的所有點都要停留，所以答案就是樹上路徑權(quán)值和，直接求出lca，然后使用差分法求出路徑權(quán)值和即可；

44分做法：當(dāng)k=2，并且n比較小的時候，我們可以把樹上路徑取出來，然后對取出來的路徑使用線性DP。設(shè)f[i]為從起點出發(fā)停留在路徑第i個點的最小時間，那么f[i] = min(f[i-1],f[i-1])+t[i]，其中t[i]等于第i個點的點權(quán)。最終答案為最后一個點的f值；

76分做法：當(dāng)n比較小的時候并且k=3的時候，對于路徑上的點的所有鄰接點i，我們令g[i]為從起點出發(fā)停留在路徑第i個點的鄰接點的最小時間，如下圖所示；

我們設(shè)c[i]表示i點鄰居的最小處理時間。對于路徑上第i個點x_i ，如果它是路徑上的點，有

這種方法每次詢問需要訪問路徑的所有點及其鄰接點，時間復(fù)雜度為O(nq)；

100分做法：上述方法需要遍歷路徑上的所有點，我們可以嘗試使用倍增法把DP的一些轉(zhuǎn)移提前處理。這樣子合并DP轉(zhuǎn)移的時間復(fù)雜度可以變成O(logn)。重定義矩陣乘法A=B·C為

很明顯這樣也符合結(jié)合律；

當(dāng)k=2時，DP轉(zhuǎn)移可以表示成：

當(dāng)k=3時，可以把之前的DP表示成一個5×5的轉(zhuǎn)移矩陣，但是這樣子每次矩陣乘法需要5的3次方個操作，時間上無法接受，需要簡化一下DP方程。

簡化完畢后，該題即可滿分。