5.27

P8392 [BalticOI 2022] Uplifting Excursion (Day1)

好題

考慮一個貪心，把所有的東西都選上，記當前的和為 \(s\)，若 \(s>l\)，則從 \(n\) 開始依次減，若 \(s<l\)，則從 \(-n\) 開始依次減，直到 \(s\in[l-m,l+m]\)，然后只需要再做一個背包就行了，此時我們最多只會加入 \(2n\) 個物品，因為 \(i\) 和 \(-i\) 同時加進去肯定不優，這樣背包的容量只需要開到 \([-n^2,n^2]\)，然后做部分背包轉移即可

P7606 [THUPC 2021] 混亂邪惡

啥必洛谷

直接做是 \(\mathcal{O}(\frac{n^3p^2}{w})\) 的

這里給出一個圖上隨機游走的結論，二維平面上每次等概率隨機選擇一個方向走，走 \(n\) 步最終的期望路徑長度為 \(\mathcal{O}(\sqrt n)\) 級別的，這里也是類似的，所以有兩維我們只需要開到 \(\sqrt n\) 大小，這樣復雜度就變成了 \(\mathcal{O}(\frac{n^2p^2}{w})\)

P6261 [ICPC 2019 WF] Traffic Blights

并不是背包，這個取大模數的方法還挺有啟發性的。

紅綠燈都是周期性變化的，記這個周期為 \(m_i=r_i+g_i\)，那他們整個的周期就是 \(M=\text{lcm}(m_1,m_2,...,m_n)\)，而一定有 \(M|2019!\)，所以只需要考慮隨機變量 \(X\in [0,M-1]\) 的情況就行了

如果只有兩個紅綠燈該怎么做？如果他們是互質的，即 \(\gcd(m_i,m_j)=1\)，發現其實對于任意 \(a<m_i,b<m_j\)，同余方程 \(X\equiv a\pmod m_i,X\equiv b\pmod m_j\)，在 \(X\in [0,M-1]\) 是有唯一的正整數解的，也就是說，\(i\) 和 \(j\) 的概率實際上是獨立的，這樣可以直接把這兩個的概率乘起來

那么如果所有的紅綠燈的周期都是互質的，我們只需要對于所有的 \(n\) 計算 \(\prod\limits_{i=1}^n \frac{r_i}{r_i+g_i}\)，于是我們可以考慮一個大的模數，記為 \(V\)，這時有 \(X=kV+l\)，我們去枚舉 \(l\)，把 \(k\) 當成那個隨機變量，那么這時候，每個紅綠燈的周期就變成了 \(\frac{\text{lcm}(V,m_i)}{m_i}=\frac{m_i}{\gcd(m_i,V)}\)，這時候我們想讓所有的周期能被劃分到若干個互質的等價類中，可以取 \(V=2^6\times 3^4\times 5^2\times 7^2=6350400\)，這樣去枚舉 \(l\)，再枚舉 \(k\)，復雜度是 \(6350400\times nm\)，其中 \(m\) 為最大的 \(r_i+g_i\)，無法通過

發現如果一個周期是另一個周期的倍數，我們可以把小的周期重復補齊到大的，這樣我們只需要找到一個 \(V\)，使得所有的周期都是一個質數的冪次，取 \(V=2^3\times 3^2\times 5\times 7=2520\) 就行了，復雜度是 \(2520\times nm\)

gym103428C

我***沙比提

找原根取對數變加法

做一個膜意義下的 01 背包，對于每一個物品 \(x\)，我們找出來他對應的轉移，發現會連成若干個環，我們每次的轉移都是若 \(u=1,v=0\) 且存在一條邊 \(u\rightarrow v\)，則 \(v\leftarrow 1\)

考慮如何優化，我們只需要找到所有 \(i\) 與 \(i+x \bmod (p-1)\) 不相同的對，更新那些 \(1\rightarrow 0\) 的邊即可，這樣 \(1\rightarrow 0\) 最多更新 \(p-1\) 次，而容易說明 \(0\rightarrow 1\) 也最多是那么多次，因為如果我們把環上的連續段都縮起來，這樣每個環都是 010101... 交替，此時顯然 \(0\rightarrow 1\) 和 \(1\rightarrow 0\) 數量相同，那我們每次找到不同的對更新即可，容易用二分+樹狀數組維護哈希值做到 \(\mathcal{O}(n\log^2 p)\)

CF1758F Decent Division

怎么想的啊

一個經典的思路是，把 \(0\) 看成 \(-1\)，把 \(1\) 看成 \(+1\)，記 \(f(i)\) 為 \(\min\limits_{j>i,sum_j=sum_{i-1}}j\)，也就是 \(i\) 對應的最左邊的合法的右端點

操作 \(0\rightarrow 1\) 時，我們會刪去一些區間并讓他們合并，若當前點 \(i\) 已經在一個區間 \([l,r]\) 內，那么令 \(p\leftarrow l\)，否則令 \(p\leftarrow i\)，然后添加 \([p,f(p)]\)，并刪除與 \([p,f(p)]\) 有交的所有其他區間，這樣為什么合法呢？證明并不難，考慮每一對 \(i<j\)，肯定 \(i<j<f(j)<i\)，因為 \(sum_i\) 每次只會變化 \(1\)，可以認為其是連續的，這時候考慮中值定理狀物并分討就行

而操作 \(1\rightarrow 0\) 時，我們會新增一些區間，有一個顯然的做法是，找到當前 \(1\) 所屬于的那個區間，從左往右掃一遍，每次找到最左邊的那個 \(1\)，并添加 \([i,f(i)]\)，但是這樣可以被卡到 \(\mathcal{O}(n)\) 級別

我們發現出現這種情況是因為我們的區間在擴張時并沒有緩沖的余地，事實上，把 \(f(i)\) 的定義改成 \(\max\limits_{j>i,sum_j=sum_{i-1},\forall k\in [i,j],sum_k\ge sum_j}j\) 就行了，這樣我們每個區間右邊還會有一個 \(0\) 作為緩沖，而且我們可以說明這樣在 \(1\rightarrow 0\) 操作時，最多只會新增 \(2\) 個，因為我們每選出來一個 \([i,f(i)]\) 都會使得當前區間 \([l,r]\) 的總和減一，這樣每個只會最多操作 \(4\) 次，最終操作次數為 \(4n\)，時間復雜度容易直接線段樹上二分做到 \(n\log n\)

5.28

模擬賽

讀錯題了。

T1

如果括號序列已經確定，記 \(sum_i\) 為 \(1\sim i\) 的前綴和，那答案一定是 \(\sum\limits_{s_i=)}sum_i-\sum\limits_{s_i=(}sum_i\)，這時候我們的策略一定是右邊的 ? 盡量放 (，左邊的 ? 盡量放 )，那每一個區間可以從用往左掃一遍做，全局答案直接枚舉右端點即可

T2

首先發現如果一個長度 \(>3\) 的區間如果沒有絕對眾數，那么一定是可以消成 \(1,1,...,1,1\) 之后再減一，如果有區間眾數為 \(x\)，那么最后的形式為 \(1,1,...,x,1\) 之后再減一

于是可以掃左端點，二分出每個前綴 \([l,i]\) 對應的區間中的絕對眾數，這個東西的數量只有 \(\log V\)，順便二分出來這個眾數可以影響到的區間，我們的貢獻形式是 \(\log V\) 個 \((i,l,r,k)\)，表示左端點在 \(i\)，右端點在 \([l,r]\) 中的值加上 \(k\)，這樣的貢獻區間有 \(\mathcal{O}(n\log V)\) 個，找到之后做二維數點就好了，復雜度是 \(\mathcal{O}(n\log n\log V)\)

T3

考慮樹的部分分，經典的，我們可以長剖出來所有的長鏈，然后枚舉每一個起點，每次肯定是取出來這個起點子樹中前幾大的長鏈，這樣可以做到 \(\mathcal{O}(n^2)\)，但是其實沒必要把一個子樹中所有的長鏈都取出來，發現這個節點長兒子對應的鏈之外的長鏈，會重復計算多次，那么我們可以把這些次數記下來，然后把所有的長鏈排序，這樣只有 \(\mathcal{O}(n)\) 個了

考慮 DAG，類似于樹的情況，我們依舊可以做一個長剖狀物，計算次數的時候，對于長兒子分討一下就行，這樣復雜度是 \(\mathcal{O}(n\log n)\) 的

CF1340F Nastya and CBS

不難啊

類似 () 時，我們只需要用線段樹維護出每個節點上形如 )))((( 的失配的 ( 和 ) 的數量，然后直接區間合并即可

這里其實也類似，我們可以考慮維護形如 }]){[( 的左右哈希值以及長度，這樣我們做區間合并的時候，為什么只維護這樣是對的？因為如果我們中間出現 ([)] 的情況，在這樣的括號序列左右加括號不可能合法，于是只需要維護前后綴即可

合并的時候，先比較長短，然后需要查詢一個區間中的前綴/后綴哈希值，寫單側遞歸線段樹就行了，可以做到 \(\mathcal{O}(n\log^2n)\)

5.29

講了很多圖圖題

CF475E Strongly Connected City 2

好玩

首先縮點，每個邊雙肯定可以構造出來一個強連通分量，考慮構造方案的話，只需要讓這個邊雙跑出來一顆 dfs 樹，讓所有樹邊往下連，非樹邊往上連就行了。又發現答案一定是以某一個點為轉折點，他的一些兒子的子樹全都是外向樹，另一些全都是內向樹（現在還沒有想到嚴謹的證明），那么我們只需要找到一個節點，把他的兒子劃分到兩個集合 \(S\)、\(T\) 中，求 \(\max (\sum\limits_{i\in S}siz_i)(\sum\limits_{i\in T}siz_i)\)，這樣可以直接背包，然后觀察到我們要求的式子滿足均值不等式，那如果有任意一個兒子的 \(siz\) 不小于其他兒子的 \(siz\) 和，肯定就是這個兒子單獨劃分，其他兒子放在一起，這樣只有重心需要做背包，可以自然根號優化以下再寫個部分背包，可以做到 \(\mathcal{O}(\frac{n\sqrt n}{w})\)

P9829 [ICPC 2020 Shanghai R] Traveling Merchant

好玩

首先手玩一下可以發現，我們走出來的路徑肯定是一個 "6"，即一段 \(1\) 開頭的路徑和一個環，而且環與那條路徑的連接處有一條同色邊，其他的都是異色邊，我們只需要判斷是否存在這樣的邊就行了

考慮直接枚舉那條同色邊，那我們的問題實際上就是要每次判斷是否存在一條 \(1\rightarrow u\rightarrow v\) 的只經過異色邊的簡單路徑

首先考慮縮點雙（顯然是點雙），把圓方樹建出來，以下進行一些分類討論：

• 如果 \(u,v\) 在同一個點雙內，那么必然有解，因為對于一個點雙中的兩個不同點，必然存在兩條無交點的路徑（點雙的定義），因為如果必然存在交點，那所有的這兩個點之間的路徑肯定是有交集的，我們任意選取交集中的一個點，那這個交點其實是一個割點，那這個點雙就不合法。記 \(1\) 到這個點雙的割點為 \(x\)，考慮直接取出來 \(u,v\) 之間的那兩個路徑，隨便找一條簡單路徑能讓割點到達這兩條路徑上的任意一個點就行了

• 如果 \(u,v\) 所在的點雙在圓方樹上存在祖孫關系，那么必然有解，這個并不難構造

• 如果 \(u,v\) 所在點雙在圓方樹上沒有祖孫關系，那么必然不合法，因為這時候，這兩個點雙的割點肯定會被經過兩個，而在一個循環中，別的點只會經過一次，這樣就破壞了這個循環

那我們的算法流程就是，每次找出同色邊 \((u,v)\)，若存在某對 \(u,v\) 滿足 \(fa_u,fa_v\)（\(1\) 的 \(fa\) 還是 \(1\)）有祖孫關系，那么有解，否則無解，容易做到線性

CF1062F Upgrading Cities

好玩

考慮記 \(f_u\) 為 \(u\) 能到達的所有點和能到達 \(u\) 的所有點之和，考慮如何求 \(f_u\)。\(u\) 能到達的和能到達 \(u\) 的實際上是對稱的，我們只需要考慮 \(u\) 能到達的然后再反圖做一遍就行了。如果一個點能到達另一個點，那么他們的拓撲序肯定是遞增的，這啟發我們在拓撲排序的過程中進行算 \(f\)

考慮 \(u\) 出隊的時候，若當前隊列中的點數為 \(0\)，說明 \(u\) 能到達所有的沒入隊過的點，給 \(f_u\) 加上這個數量就行了，若當前隊列中的點數大于 \(1\)，那 \(u\) 不可能是我們要求的點，接下來只需要考慮隊列中的點數等于 \(1\) 的情況就行了

記隊列中的那個點為 \(v\)，此時肯定 \(u\) 到達不了 \(v\)，如果還有一個點是 \(u\) 無法到達的但是 \(v\) 能到達的，那么 \(u\) 這個點就是無用點了，發現如果有這樣的點，那么肯定存在一個這樣的點滿足入度為 \(1\)，而且這個點是 \(v\) 能一步到達的點，那我們只需要知道 \(v\) 的出點中是否有點的度數為 \(1\) 就行了，實現的時候傻逼了帶了 \(\log\)，但是每個點入讀變成 \(1\) 的時候直接一遍入邊就能做到線性了

CF1338E JYPnation

好玩好玩好玩

首先有 \(dis(i,j)<4\)，直接考慮一條最短路徑 \(a\rightarrow b\rightarrow c\rightarrow d\rightarrow e\)，此時這條鏈肯定不能存在 \(x\rightarrow y,y\rightarrow z,x\rightarrow z\)，因為這樣可以直接通過 \(x\rightarrow z\) 這條邊來松弛，那么其他邊一定是大的連小的，這時候就會出現題目限制不能出現的那個形狀，所以得證

還有一個經典但是我忘了的結論，競賽圖強連通分量中一定存在三元環，證明的話直接考慮增量就行了，如果現在有一張 DAG，向其中加入一個點，那要么是這個點連所有其他的點，要么是其他的全都連這個點，否則一定會形成一個三元環，得證

接著考慮題目限制的那個結構，我們可以把競賽圖縮點后得到一條鏈，如果一個強連通分量不是拓撲序最大的那個，說明這個強連通分量中的所有點都向別的強連通分量有連邊，那么就會不合法，因為我們剛剛證明了，一個強連通分量中一定有一個三元環

那我們縮點之后肯定是形如一堆孤立點在前面，鏈尾有一個非孤立的強連通分量，這時候考慮分別數 \(\text{dis}={0,1,2,3}\) 的數量，發現 \(0,1\) 是好數的，只要你不是啥子，這時候肯定選擇數 \(2\)

我們要數的，就是有多少個 \((u,v)\)，滿足 \(v\) 到 \(u\) 有連邊，\(u\) 到 \(a\) 有連邊，\(a\) 到 \(v\) 有連邊，我們再考慮去枚舉 \(u\) 的出點，這時候有一個重要性質，考慮 \(u\) 出點中的兩點 \(a,b\)，若 \(u\) 到 \(a\) 有連邊，\(a\) 到 \(v\) 有連邊，而且 \(a\) 到 \(b\) 有連邊，則 \(b\) 肯定也滿足 \(u\) 到 \(b\) 有連邊，\(b\) 到 \(v\) 有連邊，證明并不難，只需要考慮他限制的結構就行了

上面的那個結論說明了什么呢？說明合法的可用于判定的點是有傳遞性的，也就是說，對于一個 \(u\)，取他出點集合中拓撲序最大的點，肯定是最優的，這樣我們只需要對于每個 \(u\) 找出拓撲序最大的點就行了

實現的話，縮點不需要跑 tarjan，可以按出度排序，遇到第一個 \(\text{deg}\ne n-i\) 的點，則其及以后的點肯定都在那個強連通分量中，之前的肯定都是孤立點，要找拓撲序最大點，把 \(u\rightarrow v\) 的這條邊看成一個偏序關系 \(u\preceq v\)，像在集合中找最大值的時候要做的一樣，遍歷出點集合，每次與現在確定的最大點做比較就好了，這樣總復雜度是 \(\mathcal{O}(n^2)\) 的

qoj10272

不好玩

設一個區間 \([l,r]\) 的眾數為 \(x\)，對于一個合法的區間，如果其滿足 \(a_l\ne x\) 且 \(a_r\ne x\)，那肯定有 \([l,r-1]\)、\([l+1,r]\) 和 \([l+1,r-1]\) 同樣合法，那么這三個區間就包含了 \([l,r]\) 的邊，所以我們不需要考慮 \(a_l\ne x\) 且 \(a_r\ne x\) 的情況，下面分 \(a_l=a_r=x\) 和 \(a_l=x\ne a_r\) 來討論

對于 \(a_l=a_r=x\)，我們找到每一個 \(x\)，把 \(=x\) 的位置看作 \(1\)，\(\ne x\) 的位置看作 \(-1\)，考慮每個位置的前綴和，我們連邊合法就是要滿足 \(s_r-s_{l-1}>0\)，我們只需要找到每個 \(l\) 最左邊的滿足 \(s_r=s_l\) 或者 \(s_r=s_l+1\) 的 \(r\)，將其連邊，不難發現這樣可以覆蓋所有情況

對于 \(a_l=x\ne a_r\)，我們對于每一個 \(i\)，找到最大的 \(j\)，滿足存在一個位置 \(p\)，\(\forall k\in[i,j],[p,k]\) 是合法的，發現這個 \(i,j\) 肯定是形如 xx..xx??i??j??xx..xx，即前面有一個極長的 \(x\) 連續段，而且 \([i,j]\) 是一個無 \(x\) 段的子段，那么我們只需要把所有 \(a_{l-1}=x\) 的情況都處理了就行，這時候會連邊 \((p,i)\) 以及 \((i,i+1),(i+1,i+2),...,(j-1,j)\)，可以維護一個差分數組

這樣就沒了，隨便做到線性

5.30

P12445 [COTS 2025] 數好圖 / Promet

拼好飯

如果 \(k=n\) 該怎么做？這時候就是讓所有的點都能被 \(1\) 到達且都能到達 \(n\)，如果所有的點都滿足入度為 \(0\) 且有至少一條出邊，那么這張圖肯定所有點都滿足限制，那可以直接考慮容斥去欽定某些點的入度為 \(0\)，這樣可以 \(\mathcal{O}(n^2)\) 的時間復雜度算出來只考慮 \(i\) 個點，欽定了 \(j\) 個入度是 \(1\) 的方案數，記為 \(f_{i,j}\)，那么只考慮 \(i\) 個點，所有的點都滿足存在 \(1\rightarrow u\) 且 \(u\rightarrow n\) 的路徑的方案數 \(g_i\) 就等于 \(\sum\limits_{j=0}^i (-1)^j\times f_{i,j}\)

接著考慮其他的點和 \(g_i\) 的合并，圖上有這么幾種點

• 一類點，就是 \(g_i\) 中的點
• 二類點，有 \(1\rightarrow u\) 但是沒有 \(u\rightarrow n\) 的點
• 三類點，其余點

考慮從前往后連邊（不考慮 \(g_i\) 已經存在的邊），一類點可以從他前面的三類點連過來，二類點可以從他前面的一二三類點連過來，而且必須存在一條一類或二類點連向他的邊，三類點可以從他之前的三類點連過來

發現三類點與一二類都無關，也就是說每個三類點都可以向他后面的所有點連邊，可以直接 dp 出來三類點的貢獻，復雜度為 \(\mathcal{O}(n^2)\)

一二類點之間的貢獻，也容易做到 \(\mathcal{O}(n^2)\)，最后我們卷積一下就行了，總復雜度為 \(\mathcal{O}(n^2)\)

AT_agc071_c [AGC071C] Orientable as Desired

孬玩！

首先發現非二分圖直接合法

考慮調整法，我們把某一個割點的 \(x_u\) 變成 \(k\)，考慮被割開的那些連通塊，發現每一個連通塊內的連邊都是確定的，而且與 \(u\) 的連邊的方向都相同，把這些連通塊與 \(x\) 的連邊拉出來，記作 \(a_i\)，于是就變成了，是否對于所有的 \(k\)，都存在一種選 \(a_i\) 的方案，滿足 \(\sum\limits_{i\in S}a_i=k\)，這是個經典問題，直接把 \(a_i\) 從小到大排序，如果出現 \(\sum\limits_{j=1}^{i-1}a_j<a_i-1\)，那么就有一個數不能被填出來

對于每個點都做一遍，通過調整法可以證明這是充要的（？？？？？

復雜度 \(\mathcal{n\log n}\)

P6177 Count on a tree II/【模板】樹分塊

說實話有點想寫

隨機撒點，如果我們撒了 \(B\) 個關鍵點，那每個點到最近祖先關鍵點的期望距離為 \(\frac{n}{B}\)

預處理出來所有關鍵點之間的顏色數，以及每種顏色在每個關鍵點到根的路徑上的出現次數，這樣每次詢問 \(u,v\) 時，先找出 \(u,v\) 所在的簇的最近的關鍵點 \(u',v'\)，然后對于散塊，我們要求得就是每個點是否在 \((u',v')\) 這條路徑上出現過，找到 \(u',v'\) 的 lca，記作 \(w\)，其簇上的最淺關鍵點為 \(w'\)，再開一個桶，把 \(w\rightarrow w'\) 上的顏色記下來，這樣詢問散塊中的點的出現次數就能 \(\mathcal{O}(1)\) 了

其實也可以把虛樹建出來，這樣就不用考慮 \(w\rightarrow w'\) 了

視 \(n,q\) 同階，復雜度是 \(\mathcal{O}(nB+n\frac{n}{B})\) 取 \(B=n^{0.5}\)，復雜度為 \(\mathcal{O}(n^{1.5})\)

CF232E Quick Tortoise

竟然沒想到

首先有一個 bongbong 的 \(\mathcal{O}(\frac{n^4}{w}+q)\) 的做法，預處理和詢問的復雜度極不平衡

查詢時，我們并不支持太多的信息合并，但是只合并兩個區間是簡單的，可以考慮貓樹分治，具體實現的時候，我們可以按行分治，再預處理出來 \(f_{i,j,k,l}\) 表示在 \((i,j)\)，能不能走到第 \(k\) 個分治中心的第 \(l\) 個點，用 bitset 稍微存一下，這樣我們查詢的時候只需要進行一個按位或，這樣總復雜度是 \(\mathcal{O}(\frac{n^3\log n}{w}+q(\log n+\frac{n}{w}))\)，直接堆式建樹應該可以把那個 \(q\log n\) 去掉

P5313 [Ynoi2011] WBLT

幽默感這一塊

閾值分治。

若 \(b\ge w\)，則莫隊出來 \([l,r]\) 中所有數的 bitset，然后把 bitset 每 \(b\) 個分一塊，最后從前往后按位與起來就完了，這一部分的復雜度是 \(\mathcal{O}(n\sqrt q+q\frac{n}{w})\)

若 \(b<w\)，這時候復雜度直接報了，那直接對每一個 \(b\) 跑一下莫隊維護出來每個剩余系的 \(\text{mex}\)，直接維護連續段就行，這一部分的復雜度是 \(\mathcal{O}(wn\sqrt q)\)

哈哈，喜歡出 bitset

CF1239E Turtle

好像之前 lcd 講過這個王八題，感覺還是有點實力的

首先如果烏龜不是傻逼，他肯定會走 \((1,1)\rightarrow (1,x)\rightarrow (2,x)\rightarrow (2,n)\)

結論：第一行的數單調不降、第二行的數單調不升

若存在 \(i<j\) 且 \(a_{1,i}>a_{1,j}\)，直接交換一定不劣

結論：最小值和次小值分別在 \((1,1)\) 和 \((2,n)\)

根據第一個結論，次小值只能在 \((2,n)\) 或 \((1,2)\)，而在 \((2,n)\) 肯定不劣

結論 \(x\in\left\{1,n\right\}\)

由于結論一的單調性，\(pre_{1,i}\) 和 \(suf_{2,i}\) 都是下凸的，那最大值肯定在 \(1\) 或者 \(n\) 取到

要最大值最小，也就是兩邊的上下的差值最小，可以直接背包做到 \(\mathcal{O}(\frac{n^2\sum a_i}{w})\)

CF914F Substrings in a String

嗯

有一個叫 “shift-and” 的字符串匹配方法，具體來說就是搞出來字符集大小個 bitset，字符 \(c\) 對應的 bitset 叫 \(f_c\) 好了，那 \(f_{c,i}=[a_i=c]\)

這樣我們做匹配的時候，把所有的 bitset 右移后與起來就行了，最后 \(1\) 的個數就是答案，具體來說，就是

ans.reset();
for(int i = 0; i < b.size(); ++ i)
	ans &= f[ b[ i ] - 'a' ] >> i;
return ans.count();

做這題直接用這個 shift-and 就行了，復雜度是 \(\mathcal{O}(\frac{|S|m}{w})\)，\(m=\sum |y|\)

6.1

怎么已經六月了

模擬賽

T1

幽默

手玩一下發現，答案肯定在 \([-2,2]\) 之間，因為兩個人總有一種方法把答案控制在這個區間內，那就是一直往對方的方向走，如果兩人相遇，那一個人走一步后另一個人緊跟著走，這樣差值的絕對值最多是 \(2\)，這個答案可以按 \(\text{dist}(x,y)\) 的奇偶性以及 \(k\) 的奇偶性分討得到，還有一種情況，如果當前答案對某個人來說是最劣的，那他可以選擇不往另一個人的方向走，又顯然重復走的路徑是肯定不優的，那這個人肯定會走一條最長鏈，且這條鏈不能與另一個人的路徑相遇，就相當于算一個點不經過另一個點的到其他點的最大距離，容易用線段樹維護出來，題解直接維護的是直徑，這樣復雜度最后是 \(\mathcal{O}(n\log n)\)，不卡常

T2

場上在干嘛？

首先發現 \(w_i\le 50\)，那我們可以掃描值域轉成 \(01\) 問題，這里有一個經典技巧，我們從小往大加邊，假如加入 \(< x\) 的所有邊后有 \(c_1\) 個連通塊，加入 \(\le x\) 的所有邊后有 \(c_2\) 個連通塊，那么就會造成 \((c_2-c_1)\) 的貢獻，這樣就能直接做了，復雜度是 \(\mathcal{O}(Vme)\)，考慮進一步優化

對于 \(m=2\) 時，此時的連通塊個數是好求的，我們只需要把所有 \(e\) 條邊加進去就行了，我們可以從右往左加邊，我們把左部點看作 \(u\)，右部點看作 \(v+n\)，考慮當前連邊 \(u\rightarrow v+n\)，找到 \(u\) 和 \(v\) 所在的集合，如果此時 \(u\) 所在集合中有右部點，記這個點為 \(l\)，那么其實相當于在下一次合并的時候添加 \(l\leftrightarrow v\) 這條邊，把 \((l-n,v-n)\) 這條邊加到下一個加邊集合中就行了，如果我們遇到加邊的端點在同一個集合中，那說明這條邊在以后都不能使得連通塊的數量減少了，維護一個 \(s\) 數組，表示 \(m\) 增加時，有用邊個數的增量，我們最后做一個前綴和算答案就行了，這樣我們并查集的大小始終是 \(2n\)，那最多就會加入 \(2n-1\) 條邊，沒用的邊不會有貢獻，那這部分我們就進行 \(\mathcal{O}(n)\) 次變化，這樣復雜度就做到了 \(\mathcal{O}(V(n+m+e)\alpha(n))\)

不知道為啥題解一直在說 \(\Delta=c_2-c_1\)，感覺沒啥用啊

T3

很無聊

首先令 \(a_{i,j}=-w_{j,i}\)，接著把問題轉化為，有 \(n\) 個人，第 \(i\) 個人的手上有編號為 \(i\) 的牌，第 \(j\) 張牌在第 \(i\) 個人手中的權值為 \(a_{i,j}\)，兩個相鄰的人可以交換手中的牌，而且交換之后需要滿足兩個人手中牌的權值都更大，問你能否每次交換相鄰兩張牌，使得第 \(x\) 個人手中拿的牌是 \(y\)，并且最大化手中的牌和初始的牌相同的人數

不妨令 \(y<x\)，可以發現 \(y\) 之前的牌一定不會被交換

一張牌一旦被交換了，不可能再向相反方向交換，也就是要么一直向左交換到達某個位置，要么向右交換到達某個位置

若 \(i\) 手中的牌被交換到了 \(i+1\)，那他不可能再被交換回去，所以只能一直朝著一個方向交換

兩張交換方向相同的牌，相對順序不變

考慮 \(i,j\)，假設 \(i<j\) 且 \(i,j\) 都向右交換，若 \(i\) 被交換到了 \(>j\) 的位置，肯定在某個位置做了 \(i\) 與 \(j\) 的交換，這時候其中必有一張牌是向左交換，與假設矛盾

于是可以考慮最后一次交換肯定是 \(x\) 和 \(x-1\) 兩個人發生了交換，我們去枚舉最后 \(x-1\) 手中的牌為 \(k\)，顯然 \(k\in[x,n]\)，而我們也肯定只需要考慮 \([y,k]\) 中的牌，而交換過的牌不能被交換回去，那么 \(k\) 合法的貢獻就是 \(n-(k-y+1)\)

如果我們確定了 \(y<i<k\) 的牌的交換方向，其最終的位置是唯一確定的

如果 \(i\) 向左交換，找到 \(\le \min(x-1,i-1)\) 的最靠右的位置 \(p\) 滿足 \(p\) 手中 \(i\) 比 \(y\) 權值大，\(p+1\) 手中 \(y\) 比 \(i\) 權值大，那么 \(i\) 一定會被交換到 \(p\)。因為其向左交換一定會和 \(y\) 換，此時 \(y\) 在 \(p\)，\(i\) 在 \(p+1\)，如果在 \(>p\) 的位置發生交換，則 \(p\) 這個位置就不是最靠右的了，在 \(<p\) 的位置交換會先使得 \(p\) 這個位置上的牌比 \(i\) 還大，這樣 \(y\) 就不能再交換到右邊了，對于向右交換也同理

注意到每張牌只能向左或向右，記 \(i\) 向左被交換到 \(l_i\)，向右會到 \(r_i\)，考慮 2-SAT 建模

我們去枚舉每對 \(i<j\)，考察他們向左向右的限制，記 \(LL\) 為他倆都能向左，類似的再記錄 \(LR,RL,RR\)

對于 \(LL\)，若滿足 \(i<l_j\)，肯定是合法的，若 \(l_i\ge l_j\)，那 \(i\) 和 \(j\) 的相對順序會改變，對于 \(l_i<l_j\le i<j\)，有必要條件 \(\forall x\in [l_j,i],a_{x,j}>a_{x,i}\)，直接這樣建可能會存在一些需要交換的限制沒被考慮到，但是我們對于所有的 \(i,j\) 都進行了討論，那就可以覆蓋到所有的情況

\(RR\) 的情況是類似的，\(LR\) 一定構不成限制，接下來只需要考慮 \(RL\) 的情況了

這時候，我們希望能夠找到一個位置 \(p\)，使得 \(i\) 在 \(p\)，\(j\) 在 \(p+1\) 時發生了交換，這時候需要滿足 \(p\) 左半需要滿足 \(j\) 比 \(i\) 權值更大，\(p+1\) 右半滿足 \(i\) 比 \(j\) 權值更大。這里有結論，\(p\) 的位置是唯一確定的，且 \(p=r_i+l_j-x\)

若 \(i\) 被放到了 \(r_i\)，則 \([y,i-1]\) 中還會有 \(r_i-x\) 個牌被向右交換了，\([j+1,k]\) 中則有 \(x-l_j-1\) 個位置被向左交換了，若 \(p<r_i-l_j-x\)，那 \(j\) 被交換到 \(l_j\) 的時候， 仍然有被需要交換到右邊的牌在 \(l_j\) 左邊，那就不對了，如果 \(p+1>r_i-(x-l_i-1)\)，那 \(i\) 被交換到 \(r_i\) 的時候，仍然有需要被交換到左側的牌在 \(r_i\) 右側，也不對了

把 \(LL,LR,RL,RR\) 的限制都加上去直接跑 2-SAT 就能知道當前 \(k\) 是否有解，寫一些前綴和啥的可以做到 \(\mathcal{O}(Tn^3)\)