t1

題意

給定一個(gè)有向圖，含 \(n\) 個(gè)頂點(diǎn)、\(2n\) 條邊，且每個(gè)頂點(diǎn)恰有 \(2\) 條入邊和 \(2\) 條出邊。從中刪去 \(n\) 條邊，使每個(gè)頂點(diǎn)恰剩 \(1\) 條入邊和 \(1\) 條出邊。求滿(mǎn)足條件的刪邊方案數(shù)，對(duì) \(998244353\) 取模。

對(duì)于所有數(shù)據(jù)，滿(mǎn)足 \(1 \leq n \leq 10^5\)。

題解

假設(shè)一個(gè)點(diǎn)的兩條出邊為 $i , j $, 我們新建一個(gè)圖給 \(i , j\) 連邊。如果一個(gè)點(diǎn)的兩條入邊為 $i , j $, 我們也給 \(i , j\) 連邊。

不難發(fā)現(xiàn)新圖上每個(gè)點(diǎn)度數(shù)恰好為二，并且只有偶環(huán)。我們的要求事實(shí)上就是在新圖上選幾個(gè)不相鄰的點(diǎn)，所以一個(gè)環(huán)就只有兩種選法，于是答案顯然是 \(2^{\text{環(huán)數(shù)}}\) ，直接并查集即可。

t2

比賽過(guò)了但是原題沒(méi)過(guò)，數(shù)據(jù)有點(diǎn)水。

題面

拿到肯定想到倍增，考慮直接處理從下向上死 \(2^k\) 能到達(dá)的點(diǎn)。套一個(gè)倍增就能預(yù)處理了。

考慮把一條鏈從 \(lca\) 斷開(kāi)。先跳到 \(lca\) 下死的最上方，中間還會(huì)留一點(diǎn)。

這個(gè)部分如果長(zhǎng)度 \(<k\) 就不用死了，否則答案就會(huì) \(+1\)。

t3

板子題。

題意

給定無(wú)向圖 \(G = (V, E)\)，其中 \(V = \{1, 2, \ldots, n\}\)。對(duì)每個(gè)頂點(diǎn) \(v\) 給定權(quán)值 \(f_x(v)\) 和 \(f_y(v)\)。邊 \((i, j) \in E\) 當(dāng)且僅當(dāng) \(|f_x(i) - f_x(j)| + |f_y(i) - f_y(j)| \leq d\)。求 \(G\) 的最大團(tuán)的頂點(diǎn)數(shù)。最大團(tuán)：點(diǎn)數(shù)盡可能多的完全圖。

題解

先把 \(f_x(i)\) 和 \(f_y(i)\) 當(dāng)成坐標(biāo)，然后考慮曼哈頓距離轉(zhuǎn)切比雪夫距離。

那其實(shí)就是找出一個(gè) \(k\times k\) 的矩形能包含最多的點(diǎn)。

那其實(shí)就是這道題了，用掃描線(xiàn)直接寫(xiě)。

t4

題面

題意

一個(gè)合法的整數(shù)數(shù)列 \(\{a_n\}\) 需要滿(mǎn)足：

1. \(1\le a_i\le n\) 。
2. 令 \(p_i=\max\{a_k|1\le k\le i\}\) ，則 \(p_i\le p_{i-1}+1\)

對(duì)于所有 \(t\in[1,n]\) ，求 \(\sum_{a}cnt(a,t)^2\) ，其中 \(cnt(a,t)\) 表示 \(t\) 在一個(gè)合法數(shù)列 \(a\) 中的出現(xiàn)次數(shù)。

題解

首先有個(gè)套路，\(cnt(a,t)^2\) 可以理解為 \(t\) 在 \(a\) 中可重復(fù)的選擇兩次。

根據(jù)上面的要求，我們可以定義一個(gè) \(f_{i,j}\) 表示前 \(i\) 個(gè)中，\(p_i=j\) 的方案數(shù)。

類(lèi)似的定義一個(gè) \(g_{i,j}\) 表示倒著放 \(i+1\) 個(gè)，且倒數(shù)第 \(i+1\) 個(gè) \(p\) 為 \(j\) 的方案數(shù)。

不難得出轉(zhuǎn)移：

為了避免重復(fù)，我們枚舉 \(t\) 在 \(a\) 中的第一次出現(xiàn)的位置 \(i\) ，那么前 \(i-1\) 位的方案數(shù)就是 \(f_{i-1,t-1}\) 。

由于 \(i\) 位置已經(jīng)確定放了 \(t\) ，我們現(xiàn)在有 \(4\) 種情況：

1. \(f_{i-1,t-1}\cdot g_{n-i,t}\) ：兩個(gè) \(t\) 都選 \(i\) 。
2. \(2(n-i)f_{i-1,t-1}\cdot g_{n-i-1,t}\) ：一個(gè) \(t\) 選 \(i\) ，另一個(gè) \(t\) 不選 \(i\) 。
3. \((n-i)f_{i-1,t-1}\cdot g_{n-i-1,t}\) ：兩個(gè) \(t\) 都不選 \(i\) ，且位置相同。
4. \(2{n-i\choose 2}f_{i-1,t-1}\cdot g_{n-i-2,t}\) ：兩個(gè) \(t\) 都不選 \(i\) ，且位置不同。

由于 \(i\) 位置開(kāi)始已經(jīng)有了 \(t\) ，所以后面放 \(t\) 是一定合法的，我們可以直接把后面放 \(t\) 的位置無(wú)視掉。

補(bǔ)一下上周六比賽

t1

題面

看數(shù)據(jù)范圍考慮區(qū)間 dp，發(fā)現(xiàn)不好合并，考慮枚舉最后一步。

首先將 \(a\) 和 \(b\) 離 散化，考慮區(qū)間 $\mathrm { d p } $, 設(shè) \(f _ { l , r }\) 表示修復(fù) \(\left[ a _ { i } , b _ { i } \right] \subseteq [ l , r ]\) 的所有故障所需的最少能量，由于必然有一次操作會(huì)涉及到距離最遠(yuǎn)的點(diǎn)，設(shè) \(D\) 表 示范圍內(nèi)的所有 \(i\) 的 \(d _ { i }\) 的最大值，枚舉在哪個(gè)時(shí)刻使用，設(shè)其為 $k $, 那么所有滿(mǎn)足 \(k \in \left[ a _ { i } , b _ { i } \right]\) 的故障都會(huì)被修復(fù)，只剩下沒(méi)有跨越 \(k\) 的故障，故有：

t2

原題

題意

給定一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的無(wú)向圖，現(xiàn)在每條邊可能是黑色或者白色，有 \(2^m\) 種可能。

只保留所有黑邊之后，如果整個(gè)圖每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)，那么這個(gè)圖米奇很喜歡！

現(xiàn)在米奇想知道，所有米奇喜歡的染色方案里黑邊數(shù)量的平方和。由于數(shù)字太大，只需要輸出對(duì) \(10^9+7\) 取模的結(jié)果。

題解

考慮把平方和套路性拆開(kāi)，拆成任選兩個(gè)邊都存在的方案數(shù)，那現(xiàn)在就要就出這個(gè)種類(lèi)數(shù)了。

考慮對(duì)于每個(gè)連通塊拎出來(lái)一個(gè) \(d f s\) 樹(shù)，任意的決定所有非樹(shù)邊是黑的還是白的，所有樹(shù)邊的狀態(tài)就可以唯一確定了。確定方式就是從下往上構(gòu)造，如果這個(gè)點(diǎn)度數(shù)是奇數(shù)，就把這個(gè)點(diǎn)和父親的邊的染黑，否則白。注意到根的度數(shù)一定是偶數(shù)。 因此方案數(shù)是 $2 ^ { m - n + c } $, 其中 \(c\) 是連通塊個(gè)數(shù)。

平方和可以枚舉兩個(gè)邊算一下貢獻(xiàn)。計(jì)算這兩個(gè)為黑色有多少個(gè)染色方案是好的。

cas1:這兩個(gè)邊存在一個(gè)割邊。假設(shè)第一個(gè)邊是割邊，圖分成了兩個(gè)連通塊，考慮沒(méi)有第二個(gè)邊的連通塊。這個(gè)連通塊恰有一個(gè)點(diǎn)度數(shù)增加了 \(1\)，因此整個(gè)連通塊的度數(shù)一定是奇數(shù)，所以一定無(wú)解。

case2:這兩個(gè)邊刪掉之后，整個(gè)圖的連通塊個(gè)數(shù)增加了1，此時(shí)方案數(shù)是 $2 ^ { m - n + c - 1 } $。

case3:這兩個(gè)邊刪掉之后，整個(gè)圖的連通塊個(gè)數(shù)不變，方案數(shù)是 $2 ^ { m - n + c - 2 } $。
因此我們只需要分別統(tǒng)計(jì)三類(lèi)點(diǎn)對(duì)的個(gè)數(shù)。其中一個(gè)方法是：考慮 \(d f s\) 樹(shù)的每個(gè)非樹(shù)邊，給這個(gè)非樹(shù)邊和對(duì)應(yīng)的樹(shù)鏈上的邊同時(shí)x0r一個(gè)隨機(jī)數(shù)。

所有權(quán)值為 \(0\) 的邊是割邊，權(quán)值相同的邊屬于 $c a s e 2 $, 剩余的屬于 $c a s e 3 $。 正確性證明可以百度 DZY loves Chinese II 用哈希表做到時(shí)間復(fù)雜度 $O ( n ) $。

t3

題面

考慮第一問(wèn)，其實(shí)就是最短路。考慮第二問(wèn)，對(duì)于每個(gè)點(diǎn)，其實(shí)有貢獻(xiàn)的點(diǎn)就是在最短路 DAG 上的點(diǎn)。也就是滿(mǎn)足 \(dis_u+w=dis_v\) 的這些 \(E=u\to v\)。建了圖之后我們發(fā)現(xiàn)一個(gè)方程 \(dp_u=dp_v+(dis_u-dis_v)^2\)。其中 \(v\) 是 \(u\) 的一級(jí)祖先的道路上 \(dis\) 比 \(u\) 小的節(jié)點(diǎn)。考慮拓?fù)涮幚恚乾F(xiàn)在就只需要維護(hù)出每個(gè)可達(dá)鐵路的 \(\max(dp_v+(dis_u-dis_v)^2)\) 了。這是一個(gè)經(jīng)典的可以用斜率優(yōu)化的式子，拆開(kāi)用李超樹(shù)維護(hù)即可。

t4

題面

這篇講的挺好的：link

P8170

題面

考慮二分答案，然后性質(zhì)就是貪心選擇能操作的直接操作。考慮怎么快速找到能操作的，就是直接剪掉了把下一次操作的時(shí)間算出來(lái)放在對(duì)應(yīng)時(shí)間的 vector 里面，時(shí)間復(fù)雜度 \(O((n+m+k)\log V)\to O(mk\log v)\)。

你也可以直接放堆里維護(hù) \(O(n\log V+k\log n\log V)\)。

P3660

題面

\(a\) 為左端點(diǎn)，\(b\) 為右端點(diǎn)。

為了滿(mǎn)足 \(a_i\le a_j\le b_i\le b_j\) 容易發(fā)現(xiàn)是三維偏序，但是可以直接用樹(shù)狀數(shù)組。

先左端點(diǎn)從小到大排序 \(a_j\le b_i\le b_j\)，然后就是一個(gè)區(qū)間求和，單點(diǎn)修改把右端點(diǎn)放進(jìn)去。

P1064

題面

我最開(kāi)始以為依賴(lài)性背包還比較難，沒(méi)想到就是分組背包，考慮這一組內(nèi)只有 \(4\) 種情況，直接背包做完了。

p3961

題面

還是依賴(lài)性背包，考慮按照斜率分組，然后這個(gè)依賴(lài)性的處理就是每個(gè)點(diǎn)的斜率前綴和算一個(gè)值，然后同一個(gè)斜率算一個(gè)組，然后直接背包就好了。

P3512

題面

做點(diǎn)水題，考慮雙指針，做完了。

AT_abc150_d

題面

考慮拆貢獻(xiàn)。拆成 \((1+2p)\times \frac{a_k}{2}\)。然后就是關(guān)于 \(\frac{a_k}{2}\) 的 \(lcm\) 的倍數(shù)為奇數(shù)的個(gè)數(shù)，特判一下初始就是自己偶數(shù)倍的情況 \(=0\) 就好了。

P5597

題面

考慮一個(gè)循環(huán)內(nèi)機(jī)器要怎么動(dòng)。他應(yīng)該吧除終點(diǎn)子樹(shù)的東西吃了吧，然后遞歸完成相同情況，那么完成的就是所有情況的樹(shù)的并。然后來(lái)看怎么計(jì)算這棵樹(shù)的答案，就是 \(2(n-1)+d\) 其中 \(d\) 為終點(diǎn)深度，\(n\) 為節(jié)點(diǎn)個(gè)數(shù)，枚舉每種終點(diǎn)，每次遍歷這棵樹(shù)。

P3006

題面

同類(lèi)型題

我喜歡管這種東西叫做樹(shù)上掃描線(xiàn)。看看這種東西的特點(diǎn)，就是：

• 可以分階段處理
• 貢獻(xiàn)可以合并到父親/到根的鏈上

對(duì)于這道題，對(duì)于時(shí)間分階段，有一個(gè)顯然的貪心，就是如果這個(gè)點(diǎn)能運(yùn)多少運(yùn)多少。所以會(huì)有兩個(gè)階段：

1. 滿(mǎn)了
2. 沒(méi)滿(mǎn)

考慮掃描這個(gè)東西，我們先假設(shè)所有邊都是滿(mǎn)的，然后用堆找到第一個(gè)不滿(mǎn)的節(jié)點(diǎn)，然后就可以吧自己的信息合并到父親的聯(lián)通塊上了。這個(gè)堆還不用可刪，因?yàn)橐欢ㄔ酵笙У募s快，因?yàn)橐恍﹥鹤舆\(yùn)完了。

具體來(lái)說(shuō)，維護(hù)一個(gè)時(shí)間叫做 要花多少時(shí)間能才能把自己走完。定義這個(gè)值為 \(Time_i=\lfloor\dfrac{C_i}{S_i}\rfloor\)，可見(jiàn) \(Time\) 值最小的點(diǎn)一定先送完人。設(shè)此點(diǎn)為 \(u\)，容易發(fā)現(xiàn)此點(diǎn)之后只是一個(gè)中轉(zhuǎn)站，送來(lái)的人直接往上送，于是我們可以把 \(u\) 和它的父親 \(F_u\) 合并為一個(gè)點(diǎn)。

所以我們每次取出 \(Time\) 最小的點(diǎn)，通過(guò)并查集維護(hù)聯(lián)通關(guān)系和 \(C\) 與 \(S\) 的轉(zhuǎn)移即可。

對(duì)于詢(xún)問(wèn) \(t\)，我們只要 \(t\) 時(shí)處于哪一階段，答案顯然是當(dāng)時(shí)的 \(C_1-S_1*t\)。

P8122

題面

復(fù)習(xí)一下函數(shù)交互。先看數(shù)據(jù)范圍，估計(jì)是 \(\log n +???\) 考慮分類(lèi)討論。接下來(lái)auther

分類(lèi)討論有沒(méi)有選擇 \(\geq A\) 的數(shù)。如果選擇了，一定是僅選擇一個(gè) \(\geq A\) 中最小的數(shù)，這時(shí)已經(jīng)滿(mǎn)足 \(\geq A\) 了，剩下的肯定是要取前 \(k-1\) 小。

如果沒(méi)有選擇，那么先默認(rèn)選擇最小的 \(k\) 個(gè)數(shù)，如果和 \(<A\)，就不斷把最小的數(shù)換成 \(<A\) 的數(shù)中最大的數(shù)，這樣每次的變化量都小于 \(A\)，不會(huì)突然超過(guò) \(2A\) 的上界限制。

先找到第一個(gè) \(\geq A\) 的數(shù)的下標(biāo) \(i\)，還要知道下標(biāo)在 \([1,k]\) 和 \([i-k,i-1]\) 中的數(shù)的值，總詢(xún)問(wèn)次數(shù) \(\log n+2k\)。

P14234

題意

考慮只關(guān)注逆過(guò)來(lái)的邊，就像這樣。

發(fā)現(xiàn)要最小化遍歷所有邊的長(zhǎng)度，其實(shí)就是要求這些邊的長(zhǎng)度并，我們有個(gè)結(jié)論：

• 求若干條線(xiàn)段的交的長(zhǎng)度，按照左端點(diǎn)排序一下貪心右端點(diǎn)即可。

證明用手模即可。

還有一種做法：我們考慮對(duì)左右端點(diǎn)都分別排序，然后排序后的 \(x_i,y_i\) 代表的區(qū)間并也是原來(lái)的區(qū)間并。

但是現(xiàn)在保證了左右端點(diǎn)遞增，所以總長(zhǎng)度就是：

for(int i=1;i<=cnt;i++){
	ans+=2*(x[i]-max(x[i-1],y[i]));
}

P3076

順便回憶一下一道類(lèi)似的題

題面

和剛才不一樣的就是這一次每趟只能帶一個(gè)人。考慮設(shè)起始點(diǎn)，終點(diǎn)分別為 \(st_i,ed_i\).

那答案就是排序找到一種序列最小化 \(\sum_{i=1}^{n}|st_i-ed_i|+|ed_i-st_j|\)。

第一段是定值，考慮最小化第二段。對(duì)于第二段，我們有經(jīng)典結(jié)論，就是：

• 把 \(ed\) 和 \(st\) 數(shù)組從小到大排序 \(ans=\sum_{i=1}^{n}|st_i-ed_i|\)。

證明就是任意交換一定不優(yōu)，交叉部分一定不減。