8.19

AT_agc070_b [AGC070B] Odd Namori

對于任意圖，如何計數呢？考慮矩陣樹定理，這里我們把關聯矩陣的非 \(0\) 值全變成 \(1\)，考慮這個矩陣為 \(M\)，答案就是 \(det(MM^T)\)，證明可以類似的去搞，設 \(L=MM^T\)，那么有 \(L_{i,j}=e_{i,j}+[i=j]deg_i\)，直接解這個行列式是 \(\mathcal{O}(n^3)\) 的，而這張圖是一個完全圖去掉一棵樹，考慮如何快速解

考慮矩陣行列式引理：

構造 \(L=A+J\)，其中 \(J\) 是一個全 \(1\) 方陣，則 \(A\) 的值如下：

• \(A_{1,1}=n\)
• \(A_{i,i}=n-1(i>1)\)
• \(A_{i,p_i}=-1\)
• 其余位置為 \(0\)

那么 \(u,v\) 都是全 \(1\) 向量，\(\text{adj}(A)\) 的每一個位置的貢獻都是 \(1\)，其中第 \(i\) 行第 \(j\) 列的貢獻為其代數余子式乘上 \((-1)^{i+j}\)，\(A\) 是一個下三角矩陣，他的貢獻可以直接算出來，現在考慮 \(\text{adj}(A)\) 的貢獻是啥

• 若 \(i>j\)，剩余部分也為下三角矩陣，貢獻為 \(0\)
• 若 \(i=j\)，貢獻為對角線上其他元素的乘積
• 若 \(i<j\)，若 \(i\) 不是 \(j\) 的祖先則貢獻為 \(0\)，否則貢獻為 \(j\rightarrow i\) 之外的點的 \(A_{u,u}\) 的乘積

咋算的？

建一張圖，\(i,j\) 的邊權是 \(A_{i,j}\)，枚舉排列展開行列式，貢獻不是 \(0\) 即選中圖中的若干個環，再乘上一個逆序對的奇偶性，若刪去 \(i,j\)，則看作在圖上強制選了一條邊，并且最后依舊是若干個環，顯然當 \(i\) 不是 \(j\) 的祖先的時候貢獻是 \(0\)，而 \(A_{i,p_i}=-1\)，最后與逆序對的奇偶性抵消了

統計每種長度的鏈有幾個，特判鏈頂為 \(1\)，直接計算即可，復雜度 \(\mathcal{O}(n)\)

CF1603D Artistic Partition

顯然滿足四邊形不等式，而注意到當 \(r<2l\) 時，一段的答案是 \(1\)，所以只有 \(\mathcal{O}(\log n)\) 段有用，推一下式子：

預處理 \(\varphi\) 的前綴和，每次分治的時候先計算出來 \(w(tl,mid)\) 的貢獻，在掃 \(i=tl\rightarrow tr\) 的時候減去 \(i\) 的貢獻即可，可以分析出來復雜度是 \(\mathcal{O}(n^{1.5}\log^2 n)\)

CF868F Yet Another Minimization Problem

直接決策單調性優化，分治的時候莫隊，指針移動量是 \(\mathcal{O}(nk\log n)\) 的，總復雜度也是 \(\mathcal{O}(nk\log n)\) 的

P7364 有標號二分圖計數

記答案的生成函數為 \(G\)，考慮數有標號連通二分圖，記其生成函數為 \(F\)，則有 \(G=e^F\)，接著考慮數二分圖的染色方案，記其生成函數為 \(H\)，則每有一個連通塊，會在貢獻里乘上 \(2\)，那么有 \(H=e^{2F}\)，那么我們有 \(G=\sqrt H\)

考慮算 \(H\)，顯然可以枚舉兩邊有多少個點，則有

這里指數上是乘積不好處理，我們可以用 \(ab=\binom{a+b}{2}-\binom{a}{2}-\binom{b}{2}\) 將其化為 \(\binom{n}{2}-\binom{i}{2}-\binom{n-i}{2}\)，然后就可以直接卷了

P6295 有標號 DAG 計數

數不要求弱連通的有標號 DAG，最后求個 \(\ln\) 就完了，直接 DAG 容斥，則有

把 \(i(n-i)\) 拆了，可以直接多項式求逆

8.20~9.1

進行了文化課學習

9.1~9.9

在北京旅游

9.1

做高鐵到北京

9.2

去八達嶺

9.3

上午看了月餅，下午去了天壇公園

9.4

上午去了景山公園和北海公園，下午去了頤和園

9.5

上午去了填按們（幽默鑼鼓填暗們是違禁詞），下午去西單玩了玩

9.6

去了一個神秘山，感覺很幽默

9.7

感冒了很難受，上午去后綴自動機超市買東西，下午在睡覺，晚上吃了日本料理，很好吃

9.8

看了一天視頻，看完了兩季一拳超人

9.9

從大興機場去杭州

9.10

在教師節復活。

CF1637F Towers

只有葉子需要填數，不妨令 \(h\) 最大的為根，最后需要有兩個葉子的值為 \(h_{rt}\)，這時候只需要把樹分成若干個不交的到葉子鏈，每條鏈的權值是這條鏈上的最大值，記每個節點當前到葉子鏈的最大值為 \(f_u\)，對于每個非葉子節點，肯定是和 \(f_v\) 最大的合并，直接做就好了，復雜度線性

CF19E Fairy

先拉一個 dfs 樹，考慮每一個簡單環，我們發現一個奇環和一個偶環相交之后會形成一個新的奇環，而其他情況都會形成一個新的偶環，那做法就呼之欲出了，直接差分，維護一個數組 \(c\)，奇環直接把其包含的邊的 \(c\) 都加一，偶環則減一，最后 \(c\) 等于奇環數量的邊都是合法的，還要特判只有一個奇環的情況，復雜度線性

AT_arc199_a [ARC199A] Flip Row or Col 2

牛逼。

不妨強制讓第一行變成 \(0\)，這樣我們列上的操作最多只能進行 \(R_1\) 次，對于其他的行，我們發現如果其 \(1\) 的個數 \(>\left\lfloor\frac{n}{2}\right\rfloor\)，必須將其翻轉，如果是 \(<\left\lfloor\frac{n}{2}\right\rfloor\)，必須不翻轉，因為 \(R_1<\left\lfloor\frac{n}{4}\right\rfloor\)，這樣行的決策就確定了，列直接一個一個看翻轉之前/之后是否合法就行了

AT_agc023_f [AGC023F] 01 on Tree

把問題轉化為每次合并一條邊，使得合并成一個連通塊的代價最小，如果要合并的兩個連通塊的 \(01\) 個數分別是 \(A_0,A_1,B_0,B_1\)，那么先 \(A\) 后 \(B\) 的代價就是 \(A_1B_0\)，否則就是 \(A_0B_1\)，那先 \(A\) 更優則需要滿足 \(A_1B_0<A_0B_1\)，就是 \(\frac{A_1}{A_0}<\frac{B_1}{B_0}\)，用一個堆維護即可，復雜度線性對數

AT_arc120_f [ARC120F] Wine Thief

考慮貢獻，我們只需要對于每一項計算其方案即可，記 \(g_{n,k}\) 表示從 \(n\) 個數中選出一個大小為 \(k\) 的獨立集的方案數，可以插板出來 \(g_{n,k}=\binom{n-k+1}{k}\)，對于 \(i\)，如果我們直接算 \(g_{n-3,k-1}\) 的貢獻是不對的，因為這樣 \(i-2,i+2\) 就不能同時選，因此我們還要計算欽定選擇了 \(i-2,i+2\) 的貢獻，為 \(g_{n-7,k-3}\)，這樣一直算下去，直到碰到了邊界，前綴和與處理一下就行了，復雜度線性

CF798E Mike and code of a permutation

考慮一個暴力，如果已經知道了每對 \(p_i<p_j\)，直接建圖跑一個拓撲排序就行了，現在直接跑拓撲排序比較困難，考慮另一種拓撲排序的方法，建出來反圖，從每個點開始，如果其沒被遍歷過，就跑一邊 dfs，每次把逆 dfs 序存下來，這樣得到的就是拓撲序！而這個求拓撲序的算法只需要對于每個點求其入邊

怎么判定一個點是不是另一個點的入點？我們令 \(b_{a_i}=i\)，最后為 \(0\) 的 \(a_i\) 和 \(b_i\) 我們把他賦值為 \(n+1\)，那么 \(u\rightarrow v\) 要么滿足 \(b_v=u\)，要么滿足 \(v\in[1,a_u)\) 且 \(b_v>u\)，用一顆線段樹維護刪點求區間最大值即可，復雜度線性對數

CF1152F2 Neko Rules the Catniverse (Large Version)

666。

考慮從 \(1\) 到 \(n\) 給每個數選擇一個在最終序列里的位置，發現每個數 \(i\) 可以放在序列開頭或者 \(i-1,i-2,\cdots,i-m\) 那些數的后面，直接記一個狀態 \(f_{i,j,S}\) 表示考慮了前 \(i\) 個數，當前序列的長度為 \(j\)，\(i-1\) 到 \(i-m\) 里誰被放了，則有轉移

• \(f_{i+1,j+1,(S\times2 +1)\cap(2^m-1)}\leftarrow f_{i,j,k}\times (|S|+1)\)
• \(f_{i+1,j,(S\times 2)\cap (2^m-1)}\leftarrow f_{i,j,k}\)

顯然可以矩陣優化，復雜度 \(\mathcal{O}(8^mk^3\log n)\)

CF1163F Indecisive Taxi Fee

刪邊最短路。

經過一些平凡的分討之后可以轉化成刪邊最短路

考慮隨便取一條 \(1\) 到 \(n\) 的最短路 \(P\)，有結論，對于任意的 \(u\)，從 \(1\) 到 \(u\) 的最短路，都和 \(P\) 有一個公共的前綴，記為 \(L\)，反過來從 \(u\) 到 \(n\) 的最短路，都和 \(P\) 有一個公共的后綴，記為 \(R\)，證明以后再補，枚舉每條邊 \((u,v)\)，令區間 \([L_u+1,R_v]\) 和 \([L_v+1,R_u]\) 對 \(1\rightarrow u\rightarrow v\rightarrow n\) 和 \(1\rightarrow v\rightarrow u\rightarrow n\) 取 \(\min\)，復雜度線性對數

9.11

911。

昨晚睡了四個小時，我要爆了。

學習了變分，學習特征多項式失敗，學習停時定理失敗。

模擬賽

T1

幽默。

T2

臨項交換。

T3

容斥。

T4

\(k>1\) 咋比 \(k=1\) 還幽默。

\(k=1\) 是一個調和級數求和，分段打表。

\(k>1\)，考慮把分母變成 \(\prod\limits_{i=1}^{k} (x+i)\) 的形式，因為這樣的話可以直接裂項，也就是 \(\frac{1}{\prod\limits_{i=1}^k(x+i)}-\frac{1}{\prod\limits_{i=2}^{k+1}(x+i)}=\frac{k}{\prod\limits_{i=1}^{k+1}(x+i)}\)，那給分子分母同時乘上一個多項式把他補齊就行了，然后就做完了

CF1372E Omkar and Last Floor

首先發現當 \(\sum q_i\) 一定的時候，肯定會想去最大化單個的 \(q_i\)，又發現如果最大的 \(q_i\) 已經確定了，其對其他的決策是沒有影響的，于是可以考慮一個區間 dp，記 \(f_{l,r}\) 為考慮區間 \([l,r]\) 中的數，答案是多少，直接枚舉最大的那個位置 \(k\)，記 \(c_{l,r,k}\) 表示滿足 \(l\le l'\le k\le r'\le r\) 的 \((l',r')\) 的個數，那么有轉移

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

CF1481F AB Tree

最優的情況下一定是每一層的節點顏色相同，此時答案為最大深度，記為 \(D\)，我們可以說明，如果不存在一種使得所有深度相同的點都顏色相同的方案，其答案一定是 \(D+1\)

我們考慮從上往下填，記當前層的非葉子節點個數為 \(l\)，填完了這 \(l\) 個之前還剩下 \(m\) 個位置需要填，顯然有 \(l\le \frac{m}{2}\)，因為非葉子節點至少有一個葉子，如果還能填的紅色的個數為 \(x\)，那么肯定有 \(\max(m-x,x)\ge l\)，也就是說必定存在一種方案將一層中的非葉子節都填了，接下來考慮葉子，如果說填非葉子用的顏色被用完了，那么剩下的所有點肯定可以全都填成一個顏色，否則直接令這些葉子和非葉子的顏色相同就行了，那我們就說明了答案的上界為 \(D+1\)

只需要判斷答案是否可以為 \(D\)，用經典的多重背包可以做到 \(\mathcal{O}(\frac{n\sqrt n}{w})\)

AT_arc132_e [ARC132E] Paw

牛的。

發現最終的狀態一定是形如 <<<..<<<---...--->>>...>>>，- 表示狀態不變，<> 則分別表示變成了相應的方向，那最終的狀態就是一段向左、兩個相鄰的 . 中間是一段 -、還有一段向右，那我們可以枚舉那相鄰的兩個 . 的位置，這時候我們需要計算一個 \(f_n\)，表示有 \(n\) 個 .，全都向左的概率，發現只有第一部填了最右邊的且填了 > 的時候會寄，于是有遞推式 \(f_n=f_{n-1}\times(1-\frac{1}{2n})\)，算出來 \(f\) 就能直接算答案了，復雜度線性

AT_arc132_f [ARC132F] Takahashi The Strongest

不難發現高橋能贏，必須滿足青木和 すめけ 出的一樣，而且高橋比他們的都大，考慮一個四元冪級數，把三種決策用 \(1,2,3\) 表示，接著定義運算 \(x\circ y=\begin{cases}x &x=y \\0&x\ne y \end{cases}\)，我們希望求出來 \(c_i=\sum_{j\circ k=i}a_j b_k\)，可以直接 FWT。

算出來 \(c\) 之后，我們希望求出 \(d_i=\sum_{i\circ j\ne 0}c_j\)，不妨計算 \(d_i=\sum_{i\circ j=0}c_j\)，考慮 dp，記 \(f_{i,j}\) 表示考慮了前 \(i\) 位，\(j\) 表示為前 \(i\) 位是已經的策略，后面的位和 \(d_i=\sum_{i\circ j=0}c_j\) 中的 \(j\) 后面的位相同，這樣的方案，枚舉當前位填什么即可

復雜度 \(\mathcal{O}(k4^k)\)

P4548 [CTSC2006] 歌唱王國

這一類題都是解生成函數的方程。

設 \(f_i\) 表示到第 \(i\) 輪停下的概率，\(g_i\) 表示到第 \(i\) 輪還沒停下的概率，記他們的生成函數分別是 \(F,G\)，則有

這是第一個方程，接著考慮 \(f,g\) 之間的轉化，我們直接在 \(g\) 后面加上一個串，但是可能會存在還沒加完就停了，如果我們加的長度為 \(i\)，那么 \(m-i\) 是原串的一個 border，枚舉這個 border 的長度為 \(i\)，于是又有一個方程

其中 \(a_i\) 表示 \([1,i]\) 是原串的一個 border，化簡上式可以得到

因為我們要求期望，對于第一個方程，我們可以等式兩邊同時求導，得到

則有

代入 \(x=1\) 就有

那 \(G(1)\) 就是我們需要的期望

對于第二個式子，我們同樣代入 \(x=1\)，得到

因為 \(F(1)=1\)，所以可以得到

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

9.12

P10779 BZOJ4316 小 C 的獨立集

記 \(e_{u,v,0/1,0/1}\) 表示一個簇不包含界點貢獻的答案，光這樣的話縮一度點就廢了，\(f_{u,0/1}\) 表示一個點簇包含界點的答案，直接轉移就完了

復雜度線性對數。

P4426 [HNOI/AHOI2018] 毒瘤

幽默完了

跟上面那個一樣，縮完了之后變成 \(n\le 20,m\le 30\)，直接搜。

P10044 [CCPC 2023 北京市賽] 最小環

有一點腦子。

• 先縮掉所有只有入度和只有出度的點，這樣的點肯定不會出現在環里
• 原來的縮二度點，這里變成縮入度和出度都是 \(1\) 的點
• 疊合重邊

這時候每個點度數至少為 \(3\)，則有 \(2m\ge 3n\)，又有 \(m-n\le 1500\)，聯立可得 \(m\le 4500,n\le 3000\)，然后每個點跑一邊最短路就行了

P12461 [Ynoi Easy Round 2018] 星野愛

嘗試做 rmpq 和 zhk 的互測，都沒做動，題解也看不下去，來道簡單的數據結構。

感覺有點像閾值分治，但是想了想發現沒有必要，所以就可以把 \(\sum deg \le \sqrt n\) 的分成一塊，如果 \(deg>\sqrt n\) 就單獨一塊，這樣最多只有 \(\mathcal{O}(\sqrt n)\) 塊

然后考慮修改對詢問的貢獻：

• 修改散塊，詢問散塊，可以直接暴力做
• 修改散塊，詢問整塊，可以對每一塊預處理出來一個系數數組 \(f_i\)，表示這個塊內有多少點的編號 \(\le i\)，這樣直接打標記就可以了
• 修改整塊，詢問散塊，接著用 \(f\) 數組就行了
• 修改整塊，詢問整塊，只需求出 \(f\) 的前綴和

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

P11622 [Ynoi Easy Round 2025] TEST_176

平衡樹有交并。

\(x=\max(x,a_i-x)\) 的操作，就是對于 \(\le \frac{a_i}{2}\) 的 \(x\)，令其乘上 \(-1\) 再加 \(a_i\)，于是可以掃描線，對于每一個詢問，在 \(l\) 時刻插入值為 \(x\) 的數，在 \(r+1\) 時刻詢問值，而每次修改就是先把平衡樹分成兩部分，對左半邊執行操作再和右半邊合并，而這個合并的過程值域有交，需要用到平衡樹的帶交合并，給出代碼：

void split(int t,int val,int &x,int &y){...}
int merge(int x,int y){...}
int qm(int t){
	while(ls[t])siftdown(t),t=ls[t];
	return val[t];
}
int mermer(int x,int y){
	int z=0;
	while(x&&y){
		int vx=qm(x),vy=qm(y);
		if(vx>vy)swap(x,y),swap(vx,vy);
		int w;
		split(x,vy,w,x),z=merge(z,w)
	}
	return merge(merge(z,x),y);
}

復雜度證明：

我們定義一個有序序列 \(A\) 的勢能函數 \(\pi(A)=\sum \log(a_{i+1}-a_i)\)，當我們合并兩個序列 \(A,B\) 的時候，有

這時候我們把 \(A,B\) 排在數軸上，會形成若干個 \(A,B\) 的連續段，每個連續段之間會有一個間隔，不妨假設此時 \(A\) 變成了 \(A'_1,A'_2,\cdots,A'_\frac{k}{2}\)，\(B\) 變成了 \(B'_1,B'_2,\cdots,B'_\frac{k}{2}\)，他們中間的間隔長度為 \(d_1,d_2,\cdots ,d_k\)，這時候計算 \(\Delta \pi\)，有

放縮一下可以得到

對數函數是個下凸函數，所以有

帶回原式就能得到

所以，每次合并兩個顏色段為 \(k\) 的序列，總勢能至少減少 \(k-\log(V)\)，而序列合并之后再拆開會減小勢能，初始勢能最多 \(\mathcal{O}(n\log V)\)，所以總勢能最多 \(\mathcal{O}((n+q)\log V)\)，總復雜度 \(\mathcal{O}((n+q)\log V\log n\)

P8293 [省選聯考 2022] 序列變換

T2 笑傳之重出變。

觀察一下題面，手玩一下發現最終肯定是變成 ((...()...))，而且他的操作中有一個交換相鄰的兩個合法括號串，權值不跟隨括號的移動而改變，如果直接考慮括號序列顯然寄了，所以可以考慮建樹，這樣目標就變成了最后變成一條鏈，而兩種操作分別是交換一對兄弟/把一個節點和其子節點全都掛到他左邊的兄弟上

考慮貪心，肯定是深度從上往下操作，因為下面的節點不可能跑到上面去，那每一層最后只會剩下一個點，同時一層中的節點都是只有權值是不同，下面依此分討四種情況：

• \(x=y=0\)，輸出 \(0\)
• \(x=0,y=1\)，此時當前層中所有跑到了下面的點都有貢獻，因此保留權值最大的即可
• \(x=y=1\)，最優的操作一定是選擇留下一個點 \(u\)，先讓其他的所有點跑到當前層最小的點的下面，再把這個最小的掛到 \(u\) 下面，可以得到貢獻是 \(val_{mn}\times (cnt-2)+sum_{dep}-val_u\)，這里的 \(cnt\) 表示當前層在貪心的時候有幾個點，下文中同理，那直接保留權值最大的就行了
• \(x=1,y=0\)，最優操作和上面的相同，貢獻為 \(val_u+val_{mn}\times (cnt-2)\)，同時我們知道，最終狀態下在最深處的節點是沒貢獻的，那總的貢獻就是每一層的 \(val_{mn}\times (cnt-2)\) 加上總的和減去最后留下的點的權值，這意味著我們在每一層貪心的時候，既希望把最大的丟下去，又希望把最小的丟下去
  當 \(cnt=1\)，這一層沒有貢獻，所以我們把開頭的一段 \(1\) 都刪掉
  當 \(cnt>2\)，只需要保留次大值
  當 \(cnt=2\)，這時候的情況較為復雜，對于一段連續的 \(2\)，其貢獻一定是所有數的和減去下放的那個數的權值，因為我們希望把最小值或者最大值下放，所以對于一段連續的 \(2\)，他也只會下放最大值或者最小值，直接分討下放最小值或者最大值即可

這樣就完了，復雜度線性對數

P11536 [NOISG 2023 Finals] Curtains

掃描線，從左到右掃 \(r\)，定義 \(f_{l}\) 為使用 \([l,r]\) 內的區間最右能覆蓋到哪兒，不難發現 \(f\) 具有單調性，加入一個區間 \([l',r]\) 的時候，使所有滿足 \(f_l\ge l'\) 且 \(l\le l'\) 的 \(f_l\) 都對 \(r\) 取 \(\max\) 即可，使用線段樹維護容易做到線性對數

CF1838F Stuck Conveyor

普通交互題。

有一個直覺是構造一條長蛇，能從 \((1,1)\) 開始走一直走出去，具體來說，就是先從 \((1,1)\) 開始向右走，如果向右走到頭了就向下走一格，再向左走......這樣一直構造下去就行了，然后開始詢問 \((1,1)\)

如果死循環了，我們發現這個蛇上的點天然有序，于是可以二分

如果從不該出去的地方出去了，只可能是某個拐角寄了，可以直接得到答案

如果直接出去了，要么他的方向和我們構造的這張圖的方向是一樣，要么是從上到下，容易想到構造一張反圖，根據這張反圖回答就行了

CF1646F Playing Around the Table

牛逼

嘗試構造出來一個方案使得所有人手中的牌不重復，即都是 \(\left\{1,2,\cdots,n\right\}\)，方案如下：

• 如果一個人手中有重復的，就把重復的那個傳給下一個人
• 否則，此時手牌肯定是 \(\left\{1,2,\cdots,n\right\}\)，把上一個人傳過來的傳給下一個人即可

容易說明這樣是 \(\le \frac{n(n-1)}{2}\) 的，考慮每一種牌 \(i\)，他最重復的情況肯定是有某一個人是 \(\left\{i,i,\cdots,i\right\}\)，讓這些牌都歸位，需要 \(\le \frac{n(n-1)}{2}\) 次操作

然后構造方案把第 \(i\) 個人的手牌變成 \(n\) 個 \(i\)，只需要把第 \(i\) 個人的手牌看作 \(\left\{i,i+1,\cdots,n,1,2,\cdots,i\right\}\)，把所有人的牌放到一起，就變成了一個每行每列都不相同的方陣，每次轉其中一列到正確位置就行了，也只需要 \(\frac{n(n-1)}{2}\) 次操作

這樣總操作數就是 \(n^2-n\) 的

CF1806F2 GCD Master (hard version)

不妨先假定所有數互不相同

可以把題目看成將所有的數分成 \(n-k\) 個集合，定義每個集合的權值是其所有元素的 \(\gcd\)，接下來可以說明，有且僅有一個集合的元素個數 \(>1\)

假如當前有兩個集合 \(S_1,S_2\)，\(u\) 為 \(S_1\) 中最大值，\(v\) 為 \(S_2\) 中最大值，不妨設 \(u\le v\)，且 \(|S_1|,|S_2|>1\)，將其調整為：\(S_1'=(S_2/\left\{v\right\})\cup S_1,S_2'=\left\{v\right\}\)，此時有

結論得證，這樣我們可以設最終那個 \(>1\) 個元素的集合為 \(|T|\)，有一個直覺是選擇那些比較小的數，因為 \(\gcd\) 的擾動比較小，接下來我們可以說明，把 \(T\) 從小到大排序后前 \(|T|-1\) 個數一定是前 \(|T|-1\) 小的

我們要最大化 \(T\) 的貢獻，即 \(\gcd(T)-\sum_{x\in T}x\)，考慮三個數 \(u<v<w\)，其中 \(v,w\in T,u\not\in T\)，令 \(T'=(T/\left\{w\right\})\cup\left\{v\right\}\)，有

結論得證，所以 \(T\) 一定是形如一段連續的前綴加上一個孤立點，不妨設排序后這些元素是 \(a_1<a_2<\cdots<a_k\)，定義 \(c_k=\gcd_{1\le i\le k}a_i\)，假設選了長度為 \(t\) 的前綴，如果當前 \(c_t=c_{t+1}\)，那么那個孤立點一定選 \(t+1\)，否則可以直接暴力枚舉孤立點，因為 \(t\) 是 \(\mathcal{O}(\log V)\) 級別的

對于重復的點，我們只需要選所有重復出現的數中較小的幾個即可

注意一些實現細節可以做到 \(\mathcal{O}(n\log V)\)

9.13

模擬賽

沒打。

T1

好像是幽默分層圖最短路

T2

這不是我們 UNR D幾T幾 嗎

T3

好像是幽默二分

T4

好像是困難的題

CF1153F Serval and Bonus Problem

不妨令 \(l=1\)

定義 \(f(x)\) 為 \(x\) 這個點被覆蓋的概率，我們最后只需要求一個 \(f\) 在 \(0\) 到 \(1\) 上的定積分就行了，算 \(f\)，我們去枚舉他被覆蓋了幾次，而每一條線覆蓋 \(x\) 的概率顯然是 \(2x(1-x)\)，則有

等式兩邊同時積分，得到

中間有 \(\binom{n}{i}\binom{n-i}{j}=\binom{n}{i+j}\binom{i+j}{j}\)

怎么算形如 \(\sum_{i=0}^{n-k}(-1)^i\binom{n}{i}\)？施展一些奇技淫巧：

然后就做完了

AT_agc045_b [AGC045B] 01 Unbalanced

考慮 \(0\rightarrow -1\)，先把所有的 \(?\) 都變成 \(-1\)， 然后考慮調整，每次我們固定最高點 \(x\) 去計算最低點的最大值 \(f(x)\)，顯然如果當前能把一個 \(?\) 所在的位置的 \(-1\) 變成 \(1\)，一定是不劣的，記錄一個后綴和即可判斷，這樣就能 \(\mathcal{O}(n^2)\) 了

我們又注意到 \(f(x+2)\le f_x+2\)，因為當 \(x\) 變成 \(x+2\) 時，最多只有一個 \(?\) 發生改變，因此我們只需要計算兩次 \(f\)，復雜度線性

AT_arc193_d [ARC193D] Magnets

并不困難。

發現對于我們操作的位置左邊的 \(1\) 之間的距離不會改變，右邊的 \(1\) 同理，而改變的只有可能是讓相鄰兩個 \(1\) 之間的距離減二，或者讓相鄰三個 \(1\) 中相鄰的兩對的距離減一，或者是讓最左、最右的兩個 \(1\) 之間的距離減一，最后把距離為 \(0\) 都刪了，那我們不妨記這些距離為 \(d_i\)，\(B\) 中 \(1\) 的距離為 \(d_i'\)，最后使得 \(d_i=d_i'\)

我們可以把 \(d'\) 中間加若干個 \(0\)，讓 \(d\) 與其對位匹配，對于 \(d_i'=d_i\) 的地方，我們把他定住，這樣可以把他分成若干個段，每個段只要滿足奇偶性相同且 \(d_i'<d_i\) 就是合法的，那這一段的貢獻就是 \(\frac{\sum d_i-d_i'}{2}\)，而只有開頭結尾的段貢獻不同，那只需要枚舉開頭結尾的狀態，答案就是確定的了

怎么判斷是否存在一種方案？從左往右掃 \(a\)，拿 \(b\) 去消 \(a\) 即可，復雜度線性

CF1979F Kostyanych's Theorem

牛啊。。。

初始狀態下，有

所以至少存在一個度數 \(>n-3\) 的點，我們需要根據這個條件構造

詢問 \(n-2\)，我們可以輕松判斷出是否存在度數為 \(n-2\) 的點

如果存在有度數為 \(n-2\) 的點，此時有 \(n'=n-1,m'=\frac{n(n-1)}{2}-(n-2)=\frac{(n-1)(n-2)}{2}-(n-3)\)，我們可以直接遞歸子問題；否則，此時肯定有一個度數 \(\le (n-3)\) 和一個度數為 \(n-1\) 的點，可以遞歸到一個 \(n'=n-2,m'\ge\frac{(n-2)(n-3)}{2}-(n-4)\) 的子問題

這樣就做完了。

AT_arc172_d [ARC172D] Distance Ranking

我操。。。

如果讓所有點的距離都相同，我們顯然可以構造 \(p_{i,j}=[i=j]\)

不妨讓 \(p_{i,j}=K[i,j],K=10^8\)，這個 \(K\) 很大，然后進行一些微調即可

對于 \((p_i,p_j)\)，如果我們令 \(p_{i,j}\) 加一，那原來 \(\text{dis}(p_i,p_j)=2K^2\)，那調整之后就變成了 \(2K^2-2K+\mathcal{O}(1)\)，而其他的 \(k\ne i,k\ne j\)，其和 \(p_i\) 的的距離變化都是 \(\mathcal{O}(1)\)！！！

所以我們給每一個 \(\text{dis}(p_i,p_j)\) 減去一個 \(c_{i,j}\times K\)，其他的 \(\text{dis}\) 的變化都是 \(\mathcal{O}(1)\)，所以我們只需要讓 \(c_{i,j}\) 互不相同就完成了構造！！！