做題筆記18

10.5

模擬賽

T1

。

T2

。

T3

。

T4

不會。

P5472 [NOI2019] 斗主地

考慮一下原來 $x$ 對現在 $i$ 的貢獻，我們先只考慮左邊的，有

\[g(i)=\sum_{x}\binom{i-1}{x-1}\binom{n-i}{l-x}x \]

這是一個范德蒙德卷積的形式，那可以考慮把前面的那個組合數拆了，有

\[\begin{aligned} g(i)&=\sum_{x}\left(\binom{i}{x}-\binom{i-1}{x}\right)\binom{n-i}{l-x}x\\ &=\sum_{x}\left(i\binom{i-1}{x-1}-(i-1)\binom{i-2}{x-1}\right)\binom{n-i}{l-x}\\ &=\left(\binom{n-1}{l-1}-\binom{n-2}{l-1}\right)i+\binom{n-2}{l-1} \end{aligned} \]

我們驚奇的發現這還是一個一次函數，而且系數變化只有常數，那么對于右邊的和 $f(i)=i^2$ 也類似，其變換一次之后仍然是一個二次函數，那么我們只需要維護這個二次函數就可以了，復雜度 $\mathcal{O}(n)$

10.6

中秋節快樂！中午吃了螃蟹，今天五點就潤了，爽，晚上吃了牛肉火鍋，吃了石榴

#833. Cells Blocking

首先處理出來 $(1,1)$ 和 $(n,m)$ 與每個點的可達性，找到兩條路，一條能往下走就往下走 $A$，另一條能往右走就往右走 $B$，如果 $A,B$ 有交，那所有封掉這個點的方案都是合法的，而且對于任意方案，其中肯定有一個點在 $A$ 上，我們枚舉這個點，這時候把這個點封掉再找一條新的 $A$，新的 $A$ 和 $B$ 的交點就對應了一個選點方案

怎么找這個新的 $A$？我們可以說明，如果我們去掉了 $(x,y)$，新的 $A$ 必然存在一個點在 $(x,y)$ 的正右上方，這個很顯然啊，你拉一條射線肯定能穿過新的 $A$，那找新的 $A$ 只需要從 $(x,y)$ 開始往左往下擴展

總復雜度 $\mathcal{O}(n+m)^2$

#837. Giant Penguin

拉一棵生成樹，然后點分樹，每個分治連通塊處最多多連了 $k$ 個非樹邊，找到這 $k$ 個非樹邊的 $2k$ 個端點和分治中心，以這些點為端點 bfs 一邊，詢問的時候以這些點為中點查一遍就行了，復雜度 $\mathcal{O}(nk\log n)$

#2554. AND PLUS OR

這么強？！

對于每一個 $i$，隨便找兩個位 $x,y$，把 $i$ 這兩位翻轉了 check 一下答案就做完了

道理呢？我們只需要證明若 $\forall i,j=i\oplus x\oplus y$，都有 $a_i+a_j\ge a_{i \cup j}+a_{i\cap j}$，則對于所有的 $i,j$，都滿足 $a_i+a_j\ge a_{i \cup j}+a_{i\cap j}$，這看著很像四邊形不等式，通過這個來證明結論也是簡單的

總復雜度 $\mathcal{O}(n^22^n)$

#4808. Great Party

一堆的時候，先手必勝

兩堆的時候，手玩一下可以發現失敗當且僅當 $a_1=a_2$

三堆的時候，先手必勝，因為先手可以把最大的那一堆去掉一些放到最小的那堆去

四堆的時候，失敗當且僅當 $\bigoplus_{i=1}^{4}(a_i-1)=0$，因為你先手如果取完了一堆或者把他挪到了另一堆，這時候就剩三堆了，所以可以把他變成 $a_i-1$ 的 nim 游戲

于是我們可以歸納得到，奇數堆的時候必勝，偶數堆的時候必勝當且僅當 $\bigoplus_{i=1}^{n}(a_i-1)\ne 0$

容易莫隊維護

#1876. MIPT: Connecting People

誒這不是我們聯考 T2 嗎

P5748 集合劃分計數

$n$ 個元素劃分到一個集合的 EGF 是 $e^x-1$，答案的生成函數就是 $e^{e^x-1}$

#4802. Ternary Search

我擦。

先考慮單谷，單峰的情況類似，逆序對這個東西并不好刻畫，如果我們能把單谷序列變成單調序列就好了，所以可以考慮，一個序列是單谷的，當且僅當存在一個前綴取相反數之后，這個序列是單增的，同時也可以推導出另一個充要條件，也就是存在一個子集取相反數之后，這個序列是單增的，那么我們只需要決策一些點變成相反數，計算逆序對的個數就行了

考慮最大值，如果不取相反數，其貢獻就是右邊的數的個數，如果取相反數，其貢獻就是左邊的數的個數，所以對于一個序列，我們可以依此找最大值并刪掉遞歸子問題，那么這個序列的最小逆序對數就是 $\sum_{i=1}^{n} \min(\sum_{j=1}^{i-1}[a_j<a_i],\sum_{j=i+1}^{n}[a_j<a_i])$，也就是左邊比他小的數的個數，右邊比他小的數的個數的 $\min$

考慮從左往右加數的過程，加入某個數之后，左邊比他小的數的個數不會再更改，而右邊比他小的個數是單調的，所以這個 $\min$ 在前一段時間內取得都是右邊，而后一段時間都是取的左邊，所以我們可以在加入這個數的時候維護出這個更改的時間，然后做一些簡單的區間操作，容易用線段樹維護，復雜度線性對數

#1166. Designing a PCB

很簡單的 2-sat！

首先考察一下連邊方式，不難發現對于 $l_i$ 和 $r_i$ 兩個位置，只有這幾種連邊方式：

._____.
.|...|.
.l...r.
.......

.......
.l...r.
.|...|.
._____.

________.
|......|.
|..l...r.
|__|.....

____.....
|..|.....
|..l...r.
|______|.

發現如果 $l_i$ 和 $r_i$ 向上或者向下申已經確定了，其連邊方案也是確定的，我們現在只需要知道是否存在矛盾，考慮任意一對 $(x,y)$，不妨設 $l_x<l_y$

若 $l_x<l_y<r_x<r_y$，$l_y$ 和 $r_x$ 方向必須相反
若 $l_x<l_y<r_y<r_x$，$l_y$ 和 $r_y$ 方向必須相同

直接建圖就行了，還是無向圖，直接并查集即可，構造的時候可以給令向上/向下的長度為 $r_i$，復雜度 $\mathcal{O}(n^2)$

#1173. Knowledge Is...

這種題我都做了五六百萬個了

按左端點排序，從小往大掃，維護一個 set $A$ 存未被匹配的區間，按右端點排序，再用一個 set $B$ 存被匹配了的區間，如果當前 $A$ 中存在 $r<l_i$，直接匹配，把當前區間加入 $B$，否則就是在 $B$ 中反悔掉一個已經匹配了的區間，顯然已經匹配了的區間中反悔 $r$ 最小的肯定最優，如果所有的 $r$ 都比當前的大，那不如把當前點加入 $A$

直接維護，復雜度線性對數

#2548. Juggler's Trick

記 $q=\frac{r}{r+b}$

考慮一下什么樣的能被消完，可以發現其充要條件是滿足 $r+b|N$ 且紅球數量 $R=qN$

顯然是充要的，還是提一嘴證明吧，只需要證明對于所有的這樣的序列，都能找到一個連續的長度為 $r+b$ 的子段，其中紅色的個數為 $r$，考慮一手鴿巢，每 $r+b$ 個分一段，如果其中某一段紅色的個數為 $r$，那直接刪掉這一段就行了，否則必定存在一段 $>r$ 和一段 $<r$ 的相鄰，當長為 $r+b$ 的區間 $[l,r]$ 變為 $[l+1,r+1]$ 時，紅色的最多變化 $1$，所以我們肯定能在相鄰處拿下

考慮 dp，記 $f_i$ 為到 $i$ 的答案，記 $sl_i$ 為 $[1,i]$ 至少會有幾個紅色，記 $sr_i$ 為 $[1,i]$ 至多能有幾個紅色，那么一段 $L,R$ 合法的充要條件就是 $r+b|R-L$ 且 $sl_{R}-sl_{L}\leq(R-L)\le sr_{R}-sr_{L}$，移項可得 $sl_{R}-qR\le sl_{L}-qL$ 和 $sr_R-qR\ge sr_{L}-qL$，這就是一個在線二位偏序，可以樹套樹或者 cdq 半在線轉移，復雜度 $\mathcal{O}(n\log^2n)$

10.7

模擬賽

T1

傻逼大模擬，不過沒想到可以建自動機

T2

傻逼

T3

何意味？

記 $f_{n,i}$ 為把 $n$ 劃分成 $i$ 個 $[l,r]$ 中的數的方案，有轉移

\[f_{n,i}=f_{n-i,i}+f_{n-l,i-1}-f_{n-(r+1)-(i-1),i-1} \]

復雜度 $\mathcal{O}(n\sqrt n)$

T4

重心的子樹和至少是總和的一半，要求深度最小的重心，所以答案的子樹和一定嚴格大于總和的一半

拍到 dfn 序上，序列帶權中點一定在答案的子樹內

倍增跳即可

#1351. Koosaga's Problem

原問題太難了，我們考慮一個更輕松的問題，即圖上所有邊權值為 $1$，可以把一些邊權更改成 $0$，至少需要更改幾條邊，才能使得所有環的權值和為偶數，那我們只需要考慮所有的簡單環，為什么呢，所有簡單環的權值都是偶數顯然是一個必要條件，而偶環和偶環拼一起只有偶環，所以這也是一個充分條件

既然我們已經開始考慮簡單環了，建出來dfs樹，我們考慮每一條非樹邊，我們稱一個非樹邊為奇邊，當且僅當這條非樹邊和他上下的樹邊構成一個奇環，否則我們稱為偶環，考慮把一個邊權為 $1$ 的變成 $0$ 有什么影響，如果我們改了一個樹邊，所有包含他的非樹邊的奇偶性都會改變，那我們最終的目的就是讓所有的非樹邊變成偶邊，如果直接做，給每條邊賦權值 $2^i$，同時把所有他包含的點的權值都加上這個 $2^i$，我們的目的就是選出一個樹邊的集合，使得這個集合的權值和等于所有奇邊的權值和，直接做太唐了，考慮隨機負權異或哈希，對完了

我們能說明這個問題和原問題完全等價！由于要考慮刪邊最少的方案，所以被刪的邊肯定在至少一個奇環中，也就是說如果我們刪了 $(u,v)$ 這條邊，他們仍然能通過另一條路徑連通，這條路徑的長度一定是偶數，而我們只關心奇偶性，所以這等價于這兩點之間存在一條長度為 $0$ 的邊，所以在我們想要的方案中，刪邊和改邊權完全等價，直接用這個方法做就行了

#2550. Lion and Zebra

如果是最優情況，答案一定是 $u$ 開始的最長鏈的長度加上 $d$，這時候 B 盡可能地往最長鏈走，然后在那兒等 $d$ 輪

所以我們的最優策略一定是先往最長鏈試探一步，這時候如果 A 和我們的距離減小了，那我們背后的都是安全的了，否則就是 A 在最長鏈上和我們相向而行，或者 A 在一條岔路上，那我們實際上可以遞歸子問題，因為背后的其實都已經可以更新答案了，所以我們可以都刪掉，這時候肯定還是會向最長鏈的方向走

所以，B 會一直往最長鏈走，直到下一步可能碰上 A，假如說下一步是 $x\rightarrow y$，那這個方向上的子樹都可以更新答案，直接求一個最長鏈即可，我會線段樹

還有一個細節，通過 $d$ 我們可以得出 A 一定不會在 $y$ 中 $dep$ 小于等于某個值的子樹內，這些點也可以更新答案，可以用 set 維護

最長鏈肯定在直徑端點上，這樣方便維護

復雜度線性對數

#2214. Link Cut Digraph

曾幾何時，我也認為我是分治大師

我們只需要考慮每一條邊 $(u,v)$ 兩個點在同一個 scc 的時刻，因為如果存在兩個點 $(u,v)$ 其中間沒有邊且在一個 scc 中，必存在一條連接他們的路徑，我們如果知道了每條邊的時刻，就能并查集了

考慮整體二分，對時間分治，假如當前正在處理答案在 $[l,r]$ 中的邊，我們需要知道哪些邊在 $[1,mid]$ 中是聯通的才能分治下去，考慮從出現時刻在 $[1,l-1]$ 的邊中加入 $[l,mid]$，我們會驚奇的發現，$[1,l-1]$ 中不在 scc 里也不在我們當前的邊的集合中的邊是毫無意義的，因為這些邊的答案肯定不在 $[l,r]$ 中！所以我們只需要保留編號 $[l,mid]$ 中的點跑一邊 scc

實現細節的話，前 $[1,l-1]$ 的邊的影響用并查集維護一下 scc，在分治的葉子處再把邊并起來，復雜度 $\mathcal{O}(m\log m)$

#10091. Fractal Maze

無敵了。

直接 $\mathcal{O}(ans)$ 爆搜加記憶化能過

如何分析？可以把原算法看成以下算法：設一個閾值 $K$，前 $K$ 層我們直接預處理出來所有關鍵點之間的距離，后面的 $n-K$ 層我們直接爆搜，爆搜的時候最多分成三段，中間的一段已經預處理出來了，所以復雜度是 $\mathcal{O}(q2^{n-K})$，預處理是 $\mathcal{O}(1)$ 的，復雜度是 $\mathcal{O}(4^K)$

總復雜度就是 $\mathcal{O}(q2^{n-K}+4^K)$，取 $K=\frac{\log q+n}{3}$ 可以得到 $\mathcal{O}(\sqrt[3]{q^24^n})$，大概是 $10^8$ 左右

#6284. Routes

嚯嚯嚯，嚯嚯嚯嚯

記 $f_{x,c}$ 為從 $u$ 開始，走到 $c$ 中任意一個點的距離，那么如果 $x$ 到 $y$ 至少用了一次飛機，就會有

\[\text{dist}(x,y)=\min_{c=1}^{k}f_{x,c}+f_{y,c}+1 \]

否則 $x,y$ 肯定是火車直達的，這樣的點對只有 $\mathcal{O}(nk)$ 個，我們光算上面那個權值就行了，記 $d_x$ 為 $x$ 所在的區域編號，$g_{i,j}$ 為從 $i$ 區域中任意城市到 $j$ 區域中任意城市的最短距離，肯定有 $g_{d_x,c}\le f_{x,c}\le g_{d_x,c}+1$，所以我們可以對于任意兩個區域 $(a,b)$，算這兩個區域間所有的貢獻

記 $v=\min_{c=1}^{k}g_{a,c}+f_{b,c}+1$，則對于任意的 $d_x=a,d_y=b$，都有 $\text{dis}(x,y)\in\left\{v,v+1,v+2\right\}$

考慮 $\text{dis}(x,y)=v$ 的充要條件，此時需要滿足存在一個區域 $c$，使得

\[f_{x,c}=g_{a,c},f_{y,c}=g_{b,c}$$$$v=g_{a,c}+g_{b,c}+1 \]

記滿足前兩個條件的集合分別是 $T_x,T_y$，滿足第三個的集合記作 $S$，那么條件可以轉化為

\[T_x\cap T_{y}\cap S\ne \emptyset \]

直接高維前綴和搞一搞就完了，復雜度 $\mathcal{O}(k^32^k+nk)$

10.9

已嚴肅掌握停時定理，一般的題目不太需要證明 $\varphi(A_T)=\varphi(A_i)$ 當且僅當 $T=i$，如果要證的話可以考慮一些單調性

CF1025G Company Acquisitions

構造勢能函數，我們只管活躍的節點，顯然不能簡單的記其為常數，那可以用一個函數 $f(n)$ 表示，其中 $n$ 是其下面掛了多少節點，則有

\[-1=f(n)+f(m)-\frac{1}{2}\left(f(n+1)+mf(0)+f(m+1)+nf(0)\right) \]

取 $n=m$，令 $f(0)=0$，則能得到

\[2f(n)+1=f(n+1) \]

則有 $f(n)=2^n-1$

直接算就完了，復雜度線性

AT_arc111_b [ARC111B] Reversible Cards

左部點卡右部點顏色跑 flow 即可，但是 TLE 了我其實沒懂，考慮顏色連顏色，容易發現對于一個點集，如果存在一個基環樹，肯定全都能取到，所以答案就是所有連通塊的 $\min$ 點數邊數之和

AT_arc068_c [ARC068E] Snuke Line

【模板】離線二維數點

CF850F Rainbow Balls

設 $\varphi(A_n)=\sum\limits_{i}f(a_i)$，令 $E(\varphi(A_{n+1})-\varphi(A_{n}))=-1$（這里是負一而不是一是因為我不想再推一遍式子了）

那么有

\[E\left(\varphi(A_{n+1})|A_n\right)=\sum_{i}\frac{a_i(a_i-1)+(m-a_i)(m-a_i-1)}{m(m-1)}f(a_i)+\frac{a_i(m-a_i)}{m(m-1)}\left(f(a_i-1)+f(a_i+1)\right) \]

把 $\varphi(A_n)$ 帶入則有

\[\sum_{i}\left(\frac{a_i(m-a_i)}{m(m-1)}\left(f(a_i+1)+f(a_i-1)-2f(a_i)\right)+\frac{a_i}{m}\right)=0 \]

那不妨取

\[\frac{x(m-x)}{m(m-1)}\left(f(x+1)+f(x-1)-2f(x)\right)+\frac{x}{m}=0 \]

寫好看一點

\[f(x+1)-f(x)-\left(f(x)-f(x-1)\right)=-\frac{m-1}{m-x} \]

于是記 $g(x)=f(x)-f(x-1)$，則有

\[g(x+1)-g(x)=-\frac{m-1}{m-x} \]

所以有

\[g(x)=g(0)-\sum_{i=0}^{x-1}\frac{m-1}{m-x} \]

則有

\[\begin{aligned} f(x)=&f(0)+\sum_{i=1}^{x}\left(g(0)-\sum_{j=0}^{i-1}\frac{m-1}{m-j}\right)\\ =&f(0)+xg(0)-(m-1)x+(m-1)(m-x)\sum_{i=0}^{x-1}\frac{1}{m-i} \end{aligned} \]

不妨讓 $g(0)=m-1,f(0)=0$，則有

\[f(x)=(m-1)(m-x)\sum_{i=0}^{x-1}\frac{1}{m-i} \]

則有

\[E(T)=\varphi(A_0)-\varphi(A_T)=\sum_{i}f(a_i) \]

復雜度線性對數

CF1479E School Clubs

公式題，有

\[\begin{aligned} E\left(\varphi(A_{n+1})|A_n\right)-\varphi(A_n)&=\frac{1}{2}f(1)+\frac{1}{2}\sum_{i}\left(\frac{a_i^2}{n^2}+\frac{(n-a_i)^2}{n^2}+\frac{n-a_i}{n}\right)f(a_i)\\ &+\left(\frac{a_i}{n}+\frac{a_i(n-a_i)}{n^2}\right)f(a_i-1)+\left(\frac{a_i(n-a_i)}{n^2}\right)f(a_i+1)-\sum_{i}f(a_i)\\ &=\frac{1}{2}f(1)+\sum_{i}\frac{a_i(2a_i-3n)}{2n^2}f(a_i)\\&+\frac{a_i(n-a_i)}{2n^2}f(a_i+1)+\frac{a_i(2n-a_i)}{2n^2}f(a_i-1) \\&=1 \end{aligned} \]

不妨令 $\frac{1}{2}f(1)=1$，此時有 $f(0)=0$，取 $x=a_i$，則有

\[ (2x-3n)f(x)+(n-x)f(x+1)+(2n-x)f(x-1)=0 \]

即

\[f(x+1)=\frac{3n-2x}{n-x}f(x)+\frac{x-2n}{n-x}f(x-1) \]

線性能過，做到線性的話可以維護 $f(x)=\frac{p_x}{q_x}$，使用分數法！

#4881. Hard Problem

疑似假題。

#850. Edit Distance Yet Again

考慮一個最 bong 的 $\mathcal{O}(n^2)$，記 $f_{i,j}$ 為 $S$ 前 $i$ 位和 $T$ 前 $j$ 位全部相同，則有下面三種轉移：

$f_{i,j}+1\rightarrow f_{i+1,j}$
$f_{i,j}+1\rightarrow f_{i,j+1}$
$f_{i,j}+[S_{i+1}\ne T_{j+1}]\rightarrow f_{i+1,j+1}$

發現當 $i-j$ 變化時，$f_{i,j}$ 至少增加 $1$，所以當 $|i-j|>k$ 時，dp 值也 $>k$，所以可以把第二位縮小到 $k$ 的范圍，記作 $g_{i,d}$，其中 $|d|\le k$，我們又發現 dp 值也 $\le k$，所以考慮 dp 狀態中只記錄最大的 $i$，現在考慮說明這樣做一定是正確的

我們要說明的，就是如果存在 $g_{i_1,d}\ge g_{i_2,d}$，其中 $i_1<i_2$，那我們不需要進行 $i_1$ 的轉移，如果我們從 $(i_1,d)$ 轉移到了 $(i_2,d')$ 其中 $d'\ge d$，或者 $(i_1',i_2+d-i_1')$ 其中 $i_1'\ge i_2$，我們可以說明其一定不優，不妨只考慮 $(i_2,d')$，另一邊是對稱的，此時記操作次數為 $w$，則有 $w\ge g_{i_1,d}+(d'-d)\ge g_{i_2,d} +(d'-d)$，而如果直接從 $(i_2,d)$ 轉移到 $g_{i_2,d'}$，就能取到代價為 $g_{i_2,d}+(d'-d)\le w$，所以我們證明了 $g_{i_1,d}$ 完全沒用

于是記 $h_{w,d}$ 為 $g_{i,d}\le w$ 的最大的 $i$，轉移時除了刪除/插入/修改還要盡可能地匹配一段相同的子串，不過這個用二分加哈?？梢苑奖愕鼐S護

單組數據復雜度 $\mathcal{O}(n+k^2\log n)$

#856. Cactus

對于一棵樹，如果我們固定了根的顏色，其余點的顏色都有 $k-1$ 種選擇，其答案就是 $k(k-1)^{n-1}$，所以我們考慮把仙人掌變成樹，如果所有簡單環之間都沒有公共點，我們發現其和樹幾乎沒有區別，于是我們可以考慮連一些虛邊將其變成樹，并欽定這些虛邊所連接的點顏色必須相同，具體來說就是找到一些原點然后把他們拆開

這時候所有簡單環和外界都是獨立的了，最后只需要把他們的方案乘上 $\frac{1}{k}$ 或者 $\frac{k-1}{k}$

考慮如何計算一個環的方案，記 $f_{n}$ 為長度為 $n$ 的環的方案，考慮斷環成鏈，則能得到 $f_{n}=k(k-1)^{n-1}-f_{n-1}$，直接算就行了

復雜度線性

如何判斷 $A$ 能到達 $B$？我們不妨給獨立集劃分等價類，如果 $A$ 和 $B$ 在同一個等價類中，$A$ 就能到達 $B$，于是我們可以考慮給等價類欽定代表元，如果 $A$ 和 $B$ 所在等價類的代表元相同且能找到一個方案使得 $A$ 和 $B$ 都能到達其代表元，那么就可以構造一個 $A$ 到 $B$ 的方案

為了方便，我們給這棵樹按 bfs 逆序重標號，考慮取最大元，我們記一個狀態字符串 $S$，其中 $S_i=1$ 當且僅當 $i$ 在獨立集中，記一個等價類的最大元為字典序最大的 $S$，于是我們從 $i=1$ 往大考慮，判斷 $S_i$ 能否變成 $1$，bfs 序的優勢就體現在這兒了，也就是說如果我們已經考慮了前 $i-1$ 個點，他是不會影響后面的策略的，其實 dfs 也可以，不過沒那么好描述

所以現在考慮，找到某一個點 $u$ 拉到 $i$ 處，如果能拉過去，我們需要在拉過去之前清空 $u,i$ 之間所有的點以及其鄰域，就是一個毛毛蟲，我們以 $i$ 為根找到這個 $u$，也就是我們要讓 $i$ 往下走，如果想讓 $i$ 往下走，肯定得讓其二級鄰域盡量地往下走，所以我們可以先遞歸子樹往下挪棋子，再找到一個 $u$ 挪到 $i$

操作次數是多少？對于每個 $i$，每個棋子往下最多總共操作 $n$ 步，因為每個棋子操作一步就夠了，然后再把 $u$ 挪到 $i$，操作步數為 $n$，所以至多 $2n^2$ 步，而 $A$ 和 $B$ 加一起總共也就 $4n^2$ 步

復雜度 $\mathcal{O}(n^2)$

考慮先求出最長的好的子序列，我們先排個序，這樣最大值一定在子序列中下標最大的地方，觀察到對于最大值為 $a_i$ 的子序列，若存在一個長度為 $m$ 的好的子序列，則 $\left\{a_{i-m+1},a_{i-m+2},\cdots ,a_i\right\}$ 一定是好的，可以調整最小值得到，所以可以直接二分求出來這個長度，然后考慮對于每一個元素 $a_j$，是否存在一個好的子序列可以包含他，和上面的類似，如果存在子序列可以包含他，那么子序列 $\left\{a_{i-m+2},a_{i-m+3},\cdots,a_i\right\}\cup\left\{a_j\right\}$ 一定也包含他，所以我們可以對于每一個 $i$，二分找到合法的 $j$，然后前綴和一下就做完了

復雜度線性對數

#888. Travel around China

考慮 $(1,L)$ 到 $(3,R)$ 這個矩形，如果 $(i,L)$ 到 $(j,R)$ 的最短路超過了這個矩形的邊界，超過邊界的那一段肯定是形如 $(1,x)\rightarrow (1,y)\rightarrow (2,y)\rightarrow (3,y)\rightarrow (3,x)$，首先邊界上 $(1,x)$ 到 $(2,x)$ 或者 $(2,x)$ 到 $(3,x)$ 沒必要再繞路了，而且繞路肯定不會打很多彎，因為你還得回來，所以我們可以從左到右掃一遍遞推出來 $(1,x)\rightarrow (3,x)$ 的最短路，然后直接連邊

現在就沒有邊界的限制了，考慮分治，找中間的三個點，跑一遍最短路，把這三個點到每個點的距離分別記作 $a_i,b_i,c_i$，我們要數的就是形如 $a_i+a_j<b_i+b_j$ 且 $a_i+a_j<c_i+c_j$ 的點對，可以直接 $a_{i}-b_{i}<b_{j}-a_j$ 和 $a_{i}-c_{i}<c_j-a_j$，直接二位數點即可

復雜度 $\mathcal{O}(n\log^2n)$

#964. Excluded Min

記 $f(S,x)=|\left\{z\in S\wedge z<x\right\}|-x$，則 $F(S)$ 為 $\max_{f(S,x)\ge 0}x$，從大往小掃描 $x$，考慮維護所有的詢問區間，注意到若 $S\subseteq T$，有 $f(S,x)\le f(T,x)$，于是我們只需要維護一些不交的區間，這樣就有單調性了

~~至此，一切都豁然開朗。~~

每次加入一個數，用線段樹維護有用的區間的 $f$ 值，直接區間修改，區間查詢最大值，另外用一個樹狀數組做數點，用來查詢新加的有用的區間的 $f$ 值，我們還需要維護一個數據結構以找到新的有用的段，這個可以線段樹上二分，當然也可以直接用一個 set 維護

10.10

雙十節。

模擬賽

奇異搞笑，掛分掛沒了

T1

喜歡我們 $\max a_i\times \log \max a_i$ 嗎

T2

傻逼提了哇

T3

斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了斜杠糗大了

T4

wqs 二分，內層反悔貪心，掃券，前面有代價 $\le 0$ 的就匹配，反悔的話扔一個 $w_i$ 進去，這樣就是 $a_i-w_x+w_x-w_y$，復雜度線性對數

#970. Best Subsequence

考慮二分 $W$，如果所有的數都 $\le \frac{W}{2}$，那么這個序列一定是合法的，所以這啟發我們按是否 $>W$ 分類，對于 $\le \frac{W}{2}$ 的，我們稱之為一類點，對于 $>W$ 的，我們稱之為二類點，發現最終的序列中肯定包含所有的一類點，并且二類點不能相鄰，也就是說它只能插在一類點之間

所以如果我們確定了一類點，只需要考慮相鄰兩個一類點之間二類點的貢獻（先不管頭尾了，忙這個無關緊要），假如我們正在加入 $x$，其與另一個點 $y$ 成為相鄰的一類點，一定有 $\max(a_x,a_y)<\min_{x<i<y}a_i$，或者 $x=y-1$，那我們可以通過單調棧求出合法的 $(x,y)$ 的對

現在掃 $W$ 預處理出來一類點之間二類點的貢獻，記 $\Delta_x$ 為 $x$ 能作為一類點，則是否能在和 $y$ 中間放一個二類點，如果能是 $2$，不能是 $1$，如果不是一類點則為 $0$，那這樣 $\Delta_x$ 的變化一共就 $\mathcal{O}(n)$，可以用主席樹把 $\Delta_x$ 維護出來，最后二分的時候再線段樹上二分

復雜度 $\mathcal{O}(n\log^2n)$

#975. Game

！？強強？！

如果到了某些位置我們肯定不會再動了，加入這些位置是

\[1=x_1<x_2<\cdots<x_k=n \]

那么會動的位置會一直左右橫跳直到到了不會動的位置，那么答案就是

\[\frac{1}{2n}\left((a_1+a_n)+\sum_{i=2}^{k}(a_{x_{i-1}}+a_{x_{i}})\times (x_{i}-x_{i-1})\right) \]

里面的 $\sum$ 正好就是 $(x_1,0),(x_1,a_{x_1}),(x_2,a_{x_2}),\cdots,(x_k,a_{x_k}),(x_k,0)$ 圍成的多邊形的面積乘二，于是求出 $x_i,a_{x_i}$ 的凸包即可

復雜度線性

#977. Local Maxima

二項式反演，枚舉欽定 $i$ 個位置滿足限制，如果把這 $i$ 個位置從小到大排序，相當于要有 $n+m-2i$ 個數 $<$ 第 $i$ 個數，方案就是

\[f_k=\left(\prod_{i=1}^{k}A(s_{i-1}+t_i,t_i)\right)\times A(m,k)\times A(n,k)\times A(nm,s_k) \]

其中 $t_i=n+m-2i,s_i=\sum_{j=1}^{i}t_j+1$

答案就是

\[Ans=\sum_{i=1}^{\min(n,m)}(-1)^{i-1}\binom{i}{1}f_i \]

#1174. Lights On The Road

這么弱，，，

如果要求算合法的 $S$ 的 $g(S)=\prod_{i\in S}a_i$ 的和，我們可以直接跑一個 dp，而跑這個 dp 會建出來一張 DAG，那一個合法的 $f(S)$ 實際上就對應了一條 $s$ 到 $t$ 的最短路徑，我們只需要求 K 短路

求 K 短路，拉出一個最短路樹，可以發現一條非最短路的路徑，其形態肯定形如一段樹邊、一條非樹邊、一段樹邊......我們把非樹邊寫下來就是 $(u_1,v_1,w_1),(u_2,v_2,w_2),\cdots,(u_k,v_k,w_k)$，其中 $u_{i+1}$ 是 $v_i$ 的祖先，那么這一條路徑的權值就是 $d_s+\sum_{i=1}^{k}(d_{v_i}-d_{u_i}+w_i)$，其中 $d_i=\text{dis}(t,i)$

于是我們可以建一張新圖，點集不變，邊集為對于每個點 $u$，其祖先中的非樹邊 $(u',v,w)$，連邊 $(u,v,d_v-d_u+w)$，那么從 $s$ 到 $t$ 的 K 短路就是 $s$ 開始的 K 短路，做一個超級鋼琴就可以了

如果直接這樣搞邊數就爆了，但是一個點的出邊一定是從小到大求，可以考慮用堆維護，我們可以先用可持久化可并堆維護出所有點的出邊，然后把狀態 $(dis,heap)$ 塞進優先隊列，其中 $dis$ 為當前的長度，$heap$ 為當前點對應的堆，每次取出 $new\_dis=dis+heap.top$ 最小的，得到一條那么長的路徑，把 $heap$ 的堆頂彈出得到 $new\_heap$，然后把 $(dis,new\_heap)$ 和 $(new\_dis,out\_edge_{to(heap.top)})$ 塞進去，這樣前 K 個彈出的狀態就對應了 K 短路

復雜度線性對數

#1355. Rhythm Game

記 $f_{i,j}$ 為考慮了前 $i$ 個，miss 了 $j$ 個的得分，有轉移

\[f_{i,j}=\max_{k<i}\left\{f_{k,j-1}+w_{k+1,i-1}\right\} \]

其中 $w_{l,r}$ 是恰好從 $l$ 開始連擊到 $r$ 結束的得分，考慮有沒有決策單調性

\[\begin{aligned} (w_{l-1,r}+w_{l,r+1})-(w_{l-1,r+1}+w_{l,r})=(w_{l-1,r}-w_{l-1,r+1})+(w_{l,r+1}-w_{l,r})\\ =-C_{r-l+3}A_{r+1}+C_{r-l+2}A_{r+1}\\ =A_{r+1}\times (C_{r-l+2}-C_{r-l+3}) \end{aligned} \]

由于 $C_j\ge C_{j+1},A_i\ge 0$，所以有決策單調性，直接做就是 $\mathcal{O}(n^2\log n)$

#1812. Interesting Coloring

把問題強化為對于每一個簡單環，其顏色數 $\le 8$，非樹邊我們可以瞎幾把填，問題就變成了對于任意的 $1$ 到 $i$，其顏色數量 $\le 7$

給出構造：將所有點的兒子按子樹大小排序，假如現在 $u$ 到 $1$ 上有 $c$ 種不同的顏色，則兒子先填另外這 $c-1$ 種顏色，其余的點填新顏色

那么如果存在一條 $1$ 到 $u$ 且顏色 $=8$ 的路徑，其沿著 $1/2$ 走到兒子 $v$，則有 $s_v+1\le s_u$，若沿著 $3$ 走，則有 $2s_v+1\le s_u$，以此類推，這樣就能得到 $\sum_{i=1}^{7}i!=5913>5555$，所以寄了

直接構造就行了，復雜度線性

#7510. Independent Set

變色龍。

先問出來一些獨立集，個數大概是 $\min(n,\frac{m}{n})$，然后二分，對于第 $i$ 個獨立集，把前 $i-1$ 個獨立集放在一起二分即可

posted @ 2025-10-05 16:07 fqmzwmhx 閱讀(38) 評論(0) 收藏舉報

刷新頁面返回頂部

oaigoaigilowoaigiy

10.5

模擬賽

T1

T2

T3

T4

10.6

10.7

模擬賽

T1

T2

T3

T4

10.9

10.10

模擬賽

T1

T2

T3

T4

公告