P1360 [USACO07MAR] Gold Balanced Lineup G

咋一看挺難轉(zhuǎn)化為一個(gè)有效狀態(tài)供后面查詢的。這里有兩種思路可以引導(dǎo)至正解。

1. 最樸素的列式子，\(sum_{i,k_{1}}-sum_{j,k1}=sum_{i,k2}-sum_{j,k2}=......\) 的時(shí)候方能滿足要求，顯然應(yīng)將同一天的放在一起變?yōu)橐粋€(gè)狀態(tài)，所以移項(xiàng) \(\to\) \(sum_{i,k_{1}}-sum_{i,k_{x}}=sum_{j,k_{1}}-sum_{1,k_{x}}\) 到這里就很顯然了我們要維護(hù) \(n-1\) 個(gè)差分。

2. 如果思路更順一點(diǎn)的話可以想到，均衡生長(zhǎng)的意思不就是相對(duì)能力值沒有變嘛，所以直接差分。

實(shí)現(xiàn)的話可以暴力維護(hù) std::map 里面的 \(\rm key\) 類型為 std::vector。

CF360E Levko and Game

既然是讓一個(gè)人優(yōu)于另一個(gè)人的，所以首先可以觀察到其實(shí)可變邊權(quán)只有選 \(l\) 或者 \(r\) 才更有意義。

其實(shí)可以動(dòng)態(tài)設(shè)置邊權(quán)，在 \(s_{1}\) 先到的時(shí)候設(shè)置為 \(l\)，在 \(s_{2}\) 先到的時(shí)候設(shè)置為 \(r\)。可以證明正確性，即這么根據(jù)一個(gè)人設(shè)置不會(huì)影響到另一個(gè)人，假設(shè) \(s_{1}\) 先到 \(u\) 后，將邊權(quán)設(shè)置為 \(l\)，如果 \(s_{2}\) 后續(xù)也到了這個(gè)點(diǎn)，那么二者后面的最短路徑應(yīng)該是重合的，\(s_{1}\) 先到這個(gè)點(diǎn)，故 \(s_{1}\) 先到終點(diǎn)。

這里要注意細(xì)節(jié)，這也關(guān)系到了本題的 hack，如果二者同時(shí)到達(dá)怎么辦？比如你優(yōu)先隊(duì)列先彈出 \(s_{2}\) 然后你將邊權(quán)設(shè)置為了 \(r\)，但是如果 \(s2\) 有另一條短路他可以走那一條，可是這個(gè) \(r\) 可能就影響到了同時(shí)到達(dá)的 \(s1\) 導(dǎo)致他后續(xù)最短路可能變長(zhǎng)。綜上，我們改變一下算法，進(jìn)行兩次 Dijkstra，其中第一次先爭(zhēng)取贏，如果不行再爭(zhēng)取平局。第一次策略如上，第二次在上一次基礎(chǔ)上稍微改變策略，如果二者同時(shí)到達(dá)，將邊權(quán)改為 \(l\)。

ARC066E Addition and Subtraction Hard

好題啊，單純?nèi)ハ肜ㄌ?hào)的幾層嵌套非常難搞，其實(shí)可以從最優(yōu)化角度去想。

考慮什么加括號(hào)目的，顯然是要最小化第一層括號(hào)內(nèi)的值，最大化第二層括號(hào)內(nèi)的值。

那就是讓第一層括號(hào)內(nèi)的減號(hào)盡可能多，第二層括號(hào)內(nèi)的加號(hào)盡可能多。此時(shí)再加第三層括號(hào)顯然是沒有意義的。這是一個(gè)貪心的思路，我們可以用 DP 來(lái)實(shí)現(xiàn)它。

P8445 射命丸文的取材之旅

注意觀察 \(a_{i}\) 和 \(b_{i}\) 范圍，所以選擇枚舉 \(\rm mex\) 的值。

考慮到一個(gè)值為 \(\rm mex\) 的必要條件，只有當(dāng)該區(qū)間沒有這個(gè)值的時(shí)候才行，同時(shí)注意到 \(\rm mex\) 特征以及題目要求，發(fā)現(xiàn)就算我們算大了 \(\rm mex\) 也不會(huì)使得答案不對(duì)。 所以在區(qū)間沒有該值的時(shí)候直接更新答案。\(a_{i}\) 與 \(b_{i}\) 只有相等才會(huì)產(chǎn)生限制。

P8817 [CSP-S 2022] 假期計(jì)劃

兩種做法。

• 隨機(jī)化

考慮為什么不能直接 DP ，因?yàn)榭赡軙?huì)重復(fù)旅游節(jié)點(diǎn)，發(fā)現(xiàn)如果給每個(gè)節(jié)點(diǎn)賦上一個(gè)階段就不會(huì)重復(fù)了。

于是建立滿足距離不超過(guò) \(k\) 的圖，然后在上面隨機(jī)染色，也就是說(shuō)每個(gè)點(diǎn)被賦予了一個(gè)第幾個(gè)到達(dá)的隨機(jī)階段，然后根據(jù)階段跑一遍 DP。正確性驗(yàn)證: 一次正確的可能性為 $ \frac{2}{4^4}$ ，即最后答案的四個(gè)點(diǎn)，每個(gè)點(diǎn)都有4種階段可能。跑個(gè) \(200\) 次就差不多了，可以用卡時(shí)函數(shù)。

• 枚舉 + 優(yōu)化

不會(huì)就暴力再優(yōu)化，最暴力的是枚舉四個(gè)點(diǎn)，考慮優(yōu)化這個(gè)過(guò)程。一般這種多個(gè)枚舉的優(yōu)化都是枚舉部分再拿數(shù)據(jù)結(jié)構(gòu)之類匹配剩余的。本題其實(shí)不太好匹配，為了更方便，觀察到第一個(gè)點(diǎn)和第四個(gè)點(diǎn)是對(duì)稱的，于是枚舉中間兩個(gè)點(diǎn)，用 std::set 匹配即可。

ABC128F Frog Jump

最暴力的思路就是枚舉 \(A\) 和 \(B\)，然后統(tǒng)計(jì)。

一般來(lái)說(shuō)為了簡(jiǎn)化計(jì)算可以只枚舉其中一個(gè)端點(diǎn)剩下一個(gè)端點(diǎn)可以放在一起計(jì)算減少重復(fù)計(jì)算。這題不太方便這么做，但是思路也是類似的。可以畫一下圖，模擬一下跳的過(guò)程。然后發(fā)現(xiàn) \(A-B\) 為一個(gè)周期。注意點(diǎn)的分類，奇數(shù)步為從終點(diǎn)開始的 \(A-B\) 往回眺，偶數(shù)步為從起點(diǎn)開始的 \(A-B\) 往前跳，于是就可以列出答案式子

發(fā)現(xiàn)這次枚舉的是 \(A-B\) 就可以了，而且這樣子每個(gè)答案計(jì)算式子中就有重合部分了可以前綴和減少重復(fù)計(jì)算，因?yàn)?\(A\) 的不同決定了第 \(k\) 個(gè)周期后跳到終點(diǎn)，于是 \(k\) 取任意一個(gè)合法的數(shù)都可以對(duì)答案產(chǎn)生貢獻(xiàn)。

本題的 Trick：周期的分類。

CF389A Fox and Number Game

雖然是紅題，但是挺巧妙的。

發(fā)現(xiàn)到題目的要求本質(zhì)是為錯(cuò)位相減，于是每個(gè)數(shù)最小變成整個(gè)數(shù)列的 \(\gcd\)。

P3129 [USACO15DEC] High Card Low Card P

顯然不能直接枚舉斷點(diǎn)計(jì)算，于是可以記錄前后綴然后拼接在一起。因?yàn)橐婚_始是數(shù)字大贏，后面是數(shù)字小贏，所以我們可以貪心地將大的卡牌在前面出，小的卡牌在后面出。當(dāng)規(guī)則為最大贏的時(shí)候，如果當(dāng)前最大數(shù)字也無(wú)法滿足，那么根據(jù)田忌賽馬我們應(yīng)該選擇最小的數(shù)字來(lái)匹配。

可是我們并沒有枚舉斷點(diǎn)，不知道當(dāng)前可用的最小的數(shù)字是哪個(gè)，比如如果當(dāng)前選擇了 \(1\) ，但是在后半段的拼接中又用到了 \(1\) 那就重復(fù)使用了。大膽猜測(cè)可以通過(guò)微調(diào)使得成立，如果假如重復(fù)使用了 \(x\) ，那么必定存在一個(gè)相異的 \(y\) 。根據(jù) \(y\) 與 \(x\) 的大小關(guān)系在前綴或者后綴中替換 \(y\) 就可以了。

P9013 [USACO23JAN] Find and Replace S

看到這題的第一想法肯定是一堆字符串變來(lái)變?nèi)ィ浅?fù)雜。

此時(shí)不妨冷靜思考一下突破口：顯然對(duì)于一個(gè)字符 \(s\) 它只能變成除了 \(s\) 之外的。

約束關(guān)系考慮建圖。這個(gè)時(shí)候需要分類討論一下：鏈直接是邊數(shù)。環(huán)的話需要引入環(huán)外一點(diǎn)（如果不存在額外一點(diǎn)就無(wú)解），答案是邊數(shù)加一。基環(huán)樹答案也是邊數(shù)。

CF163D Large Refrigerator

搜索題。

先確定思路，應(yīng)該是逐一確定 \(abc\)。然后對(duì)于要搜的數(shù)考慮 \(V\) 的每一個(gè)質(zhì)因子應(yīng)該放幾次方進(jìn)去。

接下來(lái)就是剪枝

1. 可行性剪枝，不妨設(shè) \(a \le b \le c\)，那么 \(a\le\sqrt[3]{V}\) 且 \(b^2 \le \frac{V}{a}\)。

2. 優(yōu)化搜索順序，發(fā)現(xiàn) \(abc\) 三個(gè)數(shù)盡可能平均時(shí)答案應(yīng)該會(huì)更大。所以 \(a\) 作為最小的數(shù)應(yīng)該盡可能大一點(diǎn)才能保證平均，這樣才會(huì)先搜到更優(yōu)答案以方便后續(xù)更快排序不優(yōu)的答案。同理確定 \(a\) 后 \(b\) 也是如此，于是我們需要對(duì)于每一個(gè)質(zhì)因子從最大的指數(shù)開始枚舉。

3. 最優(yōu)性剪枝，

固定 \(a\)，

考慮面積表達(dá)式，

如果當(dāng)前搜到的 \(a\) 所得面積下限大于當(dāng)前最優(yōu)面積那么直接剪掉。

void dfs2(long long num1,long long num2,int tot){
	if((double)num2*num2>v/num1) return ;
	else if(tot>k){	
		long long num3=v/num1/num2;
		if(num1*num3+num1*num2+num2*num3<ans){
			ans=num1*num3+num1*num2+num2*num3;
			a=num1;
			b=num2;
			c=num3;
		}
	}else{
		for(register int i=cnt[tot];i>=0;i--){
			cnt[tot]-=i;
			dfs2(num1,num2*p[tot][i],tot+1);
			cnt[tot]+=i;
		}
	}
}
void dfs1(int tot,long long num){
	if((double)num*num>v/num) return ;
	else if(tot>k){
		long long x=v/num;
		if(ans<=2*num*sqrt(x)+x) return ;
		dfs2(num,1,1);
	}else{
		for(register  int i=cnt[tot];i>=0;i--){
			cnt[tot]-=i;
			dfs1(tot+1,num*p[tot][i]);
			cnt[tot]+=i;
		}
	}
}
void inp(){
	cin>>k; v=1;
	for(register int i=1;i<=k;i++){
		scanf("%lld%d",&p[i][1],&cnt[i]);
		p[i][0]=1;
		for(register int j=1;j<=cnt[i];j++) p[i][j]=p[i][j-1]*p[i][1];
		v*=p[i][cnt[i]];
	}
	ans=1e19;
}
dfs1(1,1);

CF1393D Rarity and New Dress

觀察到一個(gè) \(n\) 階菱形必然由以它中心相鄰的 \(4\) 個(gè)格子為中心的 \(4\) 個(gè) \(n-1\) 階菱形拼成，這啟發(fā)我們?cè)O(shè) \(dp_{i,j,k}\) 表示中心為 \((i,j)\) 的格子能否產(chǎn)生 \(k\) 階菱形，該狀態(tài)為 \(1\) 的條件是周圍四個(gè)格子與之同色，且周圍四個(gè)格子能產(chǎn)生 \(4\) 個(gè) \(k-1\) 階的菱形。這顯然會(huì)超時(shí)。解決方案：

• 可以 bitset 亂搞。
• 一般遇到 bool 類型的 dp，如果某一維度具有單調(diào)性，也就是說(shuō)越大越好。這里顯然就是因?yàn)?\(k\) 大的時(shí)候滿足，那么小的時(shí)候必然也滿足。這個(gè)時(shí)候我們可以將狀態(tài)中的 \(k\) 提出來(lái)，放到 dp 值里面，這樣只需要最大化 \(dp_{i,j}\) 即可。兩種處理方式，第一種就是每個(gè)點(diǎn)能向 \(4\) 個(gè)方向擴(kuò)展的距離取 \(\min\)，這時(shí)也不需要 dp 了，循環(huán)判斷即可。第二種還是 dp，我們發(fā)現(xiàn)如果設(shè)置中心點(diǎn)的話會(huì)有后效性，因?yàn)?\((i,j)\) 依賴于 \((i-1,j)~(i,j-1)~(i+1,j)~(i,j+1)\)，剛剛因?yàn)橛?\(k\) 的階段所以無(wú)后效性，現(xiàn)在去掉 \(k\) 后就有了。于是我們直接選取菱形最右邊的點(diǎn)就行。

CF1348E Phoenix and Berries

最優(yōu)化問(wèn)題不會(huì)的話就嘗試找找上下界。

這題的突破口就是尋找上下界，可以發(fā)現(xiàn)答案上界為 \(\lfloor \frac{\sum a_i+\sum b_i}{k} \rfloor\)，下界為 \(\lfloor\frac{\sum a_i}{k}\rfloor+\lfloor\frac{\sum b_i}{k}\rfloor\)。不難發(fā)現(xiàn)二者最大差為 \(1\)，且取決于 \(ra=\sum a_i \bmod k\)，\(rb=\sum b_i \bmod k\)。

如果 \(ra+rb<k\)，那么上下界相等直接輸出即可。

如果 \(k \le ra+rb <2k\)，那么我們可以嘗試用同一顆樹上的果子來(lái)裝籃子，使得采用這個(gè)方法用掉的 \(a~b\) 滿足 \(ua' \bmod k \in (0,ra)\)，\(ub' \bmod k \in (0,rb)\)，且 $ ua'+ ub' \equiv 0 (\bmod k)$。

如果此時(shí)進(jìn)行 dp 的話狀態(tài)數(shù)太大，我們發(fā)現(xiàn) \(ua~ub\) 有約束關(guān)系，那么能否使用其中一個(gè)來(lái)表示另一個(gè)。 其實(shí)是可以的，只需滿足 \(ua' \bmod k \in (k-rb,ra)\) 即可。

CF1367F2 Flying Sort

先看簡(jiǎn)單版，其實(shí)我們發(fā)現(xiàn)答案下階是序列長(zhǎng)度減去最長(zhǎng)上升子序列長(zhǎng)度，能否達(dá)到呢，因?yàn)槲覀円苿?dòng)數(shù)字的順序是可以自己選擇的，所以我們必然可以滿足除了最長(zhǎng)上升子序列外剩下數(shù)字可以在下階操作次數(shù)下完成。然后是困難版，因?yàn)閿?shù)字可重復(fù)了這就麻煩了，如果形如 \(x-1~x~x+1~x\) 這樣的形式，雖然前三個(gè)可以構(gòu)成上升子序列，但是我們無(wú)法把最后一個(gè) \(x\) 插入進(jìn)去，因此簡(jiǎn)單版的做法在困難版不可取。可以發(fā)現(xiàn)這里要求的新最長(zhǎng)上升子序列中的每一項(xiàng)（除了第一和最后一項(xiàng)）必須保證所有與之相同的數(shù)字都在該序列里出現(xiàn)了。開頭和結(jié)尾的出現(xiàn)幾個(gè)無(wú)所謂。
于是我們?cè)O(shè)置出狀態(tài) \(dp(i,j)\)，其中 \(j\) 取 \(0/1/2\) 分別表示 \(a_i\) 作為序列的第一項(xiàng)，中間項(xiàng)和最后一項(xiàng)時(shí)序列的最長(zhǎng)長(zhǎng)度。其中中間項(xiàng)的要求必須是 \(i=end_{ai}\)。 然后記錄上次出現(xiàn)的位置轉(zhuǎn)移即可。

P3515 [POI2011] Lightning Conductor

此處主要記錄不用決策單調(diào)性的做法。

1. 我們發(fā)現(xiàn)根號(hào)的取值是 \(O(\sqrt{n})\) 級(jí)別的。于是在每一個(gè)位置枚舉根號(hào)取值然后在對(duì)應(yīng)前后綴中查詢 \(a_j\) 最值，這樣算法是 \(O(n\sqrt{n})\) 的。
2. 使用貢獻(xiàn)法，對(duì)于每一個(gè)位置 \(i\) 考慮對(duì)別的位置的貢獻(xiàn)，只需要在每一個(gè)根號(hào)值發(fā)生變化的地方打上標(biāo)記即可。
3. 優(yōu)化:我們發(fā)現(xiàn)一個(gè)位置能對(duì)之后產(chǎn)生貢獻(xiàn)的必要條件為這個(gè)位置的值大于之前的所有位置。這么一來(lái)在隨機(jī)數(shù)據(jù)的情況下復(fù)雜度又下降為 \(O(n+\sqrt{n}\log{n})\)。
4. 其實(shí)能產(chǎn)生貢獻(xiàn)的位置更少，設(shè)序列最大值為 \(max\)，那么只有值域落在 \([max-\sqrt{n},max]\) 之間的數(shù)才能產(chǎn)生貢獻(xiàn)。而且該數(shù)必須是第一次出現(xiàn)。這就把能產(chǎn)生貢獻(xiàn)的規(guī)模降到了 \(O(\sqrt{n})\)，總復(fù)雜度為 \(O(n+\sqrt{n})\)。

PR #1 刪數(shù)

其實(shí)數(shù)列是可以從左往右按順序刪除的，我們發(fā)現(xiàn)每次刪除保留的是兩邊的數(shù)，也就是一個(gè)區(qū)間刪完之后剩下的是左右端點(diǎn)，所以并不能通過(guò)左右各刪一部分，使得左右邊的某個(gè)數(shù)跨過(guò)了屏障相遇。這題還有區(qū)間平均數(shù)的不變性，所有剩下兩個(gè)端點(diǎn)平均數(shù)為區(qū)間平均數(shù)不過(guò)好像沒用。

部分分 \(a_i=i\)，直接奇偶刪即可。部分分，\(a_i \le 3\) 挺有意思的，其實(shí)我們發(fā)現(xiàn)本來(lái)是不能遇到能刪就刪，但是這個(gè)部分分策略就是能刪就刪，因?yàn)槿绻羞B續(xù)的三個(gè)不同的數(shù)可以被操作，也就是 \(1~2~3\)，我們發(fā)現(xiàn)左或右邊的數(shù)無(wú)法被更左或更右的數(shù)刪，因?yàn)樗鼈円呀?jīng)是極值了。

部分分 \(n \le3000\)，其實(shí)雖然 \(\sum n \le 10000\)，但是單組數(shù)據(jù) \(n\) 并不大，所有可以 \(O(n^2\log n)\)。易知區(qū)間刪到最后就是兩個(gè)端點(diǎn)，所以區(qū)間結(jié)果具有唯一性。于是設(shè) \(dp_{l,r}\) 表示區(qū)間 \([l,r]\) 能否被操作，中間的分治點(diǎn)需要滿足 \(a_{m}=\frac{a_l+a_r}{2}\)。觀察性質(zhì)，發(fā)現(xiàn)區(qū)間 \([l,r]\) 是單調(diào)的，二分尋找即可。

可以聯(lián)想 NOIP2022 T3，正解是考慮差分，這樣就是合并相同差分并乘以 \(2\)。固定右端點(diǎn)，發(fā)現(xiàn)可以滿足條件的左端點(diǎn)級(jí)別在 \(O(\log n)\)。這里有一個(gè)小技巧，我們發(fā)現(xiàn)呈 \(2\) 倍關(guān)系的值 \(\frac{x}{lowbit(x)}\) 相同。

ARC067F Yakiniku Restaurants

法一：設(shè) \(f_i\) 表示 \(i\) 的轉(zhuǎn)移點(diǎn)，我們發(fā)現(xiàn) \(f_i\) 具有單調(diào)性，分治即可。
法二：差分其實(shí)還有標(biāo)記功能，對(duì)于我們用 \(s_{l,r}\) 表示 \([l,r]\) 的貢獻(xiàn)，對(duì)于每一種燒烤券，每家燒烤店都有一個(gè)左右的控制范圍，在那個(gè)范圍內(nèi)對(duì)于該燒烤券必然選擇該店，假設(shè)為 \([l,r]\) 于是對(duì)于左端點(diǎn)位于 \([l,i]\) 且右端點(diǎn)位于 \([i,r]\) 的決策必然選擇該店。于是二維差分標(biāo)記一下即可。

CF1943E2 MEX Game 2

像這種關(guān)于 \(\rm mex\) 的題目經(jīng)常都是是枚舉 \(\rm mex\) 判斷是否可行。本題可以將枚舉改為二分，然后就是需要判斷能否 Alice 無(wú)法取到 \([1,x]\) 內(nèi)的所有數(shù)。

明確一下雙方的策略， Alice 肯定是先取小的。考慮這么一種情形，就是 Bob 將全部 \(k\) 次花在了第 \(i\) 堆上但是沒拿完，那么 Alice 一下將第 \(i\) 堆刪掉，以此類推，這種顯然 Bob 的努力也就白費(fèi)了，所有正確的策略應(yīng)該是均勻地取 \([suf_x,x]\) 之內(nèi)的數(shù)。于是需要保證當(dāng) Alice 取到 \(suf_x\) 的時(shí)候，\([suf_x,x]\) 之間的極差小于等于 \(1\)。這個(gè)位置顯然是可以二分的。

找到這個(gè)位置之后如何操作呢，我們發(fā)現(xiàn)此后的每個(gè)位置基本上是等價(jià)的，于是只需要求出總和 \(sum\) 和剩余個(gè)數(shù) \(res\) 就行了，然后根據(jù) \(Alice\) 策略每次 \(sum \to sum-\lfloor\frac{sum}{res}\rfloor\)，然后 \(res \to res-1\)，同時(shí) \(sum \to sum-k\)。

如何快速判斷 \((sum,res)\) 是否符合要求呢，有個(gè)小技巧可以預(yù)處理遞推數(shù)組 \(dp_i\) 表示剩余 \(i\) 個(gè)的時(shí)候能滿足的最大 \(sum\)。

CF201E Thoroughly Bureaucratic Organization

第一反應(yīng)是是對(duì)于構(gòu)造若干個(gè)集合，使得每一個(gè)元素都是某些集合的唯一交集，這是錯(cuò)誤的，比如詢問(wèn) \(\{1,2\}\) 和 \(\{1\}\) 的時(shí)候就是一個(gè)反例。從元素角度考慮就是考慮包含他的詢問(wèn)集合，使得任意兩個(gè)元素的集合不完全相同。

考慮二分答案次數(shù) \(k\) 轉(zhuǎn)化為判定，于是我們就需要找到 \(n\) 個(gè) \(k\) 位的互不相同的二進(jìn)制串，使得任意一位的 \(1\) 總數(shù)不超過(guò) \(m\)。這里需要大膽猜想一下，只需要所需 \(1\) 的總數(shù)不超過(guò) \(mk\) 就行了，至于證明就是考慮某一位 \(i\) 個(gè)數(shù)大于 \(m\) 個(gè)，那么不斷移動(dòng)到小于 \(m\) 的位置 \(j\) 上，那么會(huì)不會(huì)有沖突呢，也就是移過(guò)去之后發(fā)現(xiàn)有一個(gè)數(shù)其他位相同且正好也是 \(i\) 無(wú)，\(j\) 有。可是因?yàn)?\(i\) 的數(shù)比 \(j\) 多，所以總能找到一種搭配使得與 \(j\) 不沖突。然后只需要貪心地從 \(1\) 個(gè) \(1\) ，\(2\) 個(gè) \(1\)，\(3\) 個(gè) \(1\dots\) 開始放就行了。

CF333E Summer Earnings

轉(zhuǎn)化一下題意就是選擇三個(gè)點(diǎn)，使得它們構(gòu)成三邊的最小值最大。

直接枚舉三邊是 \(O(n^3)\) 的，于是我們可以先將邊降序排序，發(fā)現(xiàn)一條邊可以產(chǎn)生貢獻(xiàn)，當(dāng)且僅當(dāng)它所連兩點(diǎn)在此前都和另一個(gè)點(diǎn)連通過(guò)了（這說(shuō)明這兩條邊比這條邊大）。這可以用 std::bitset 判斷。時(shí)間復(fù)雜度 \(O(\dfrac{n^3}{\omega})\)。

CF878D Magic Breeding

神仙題。可以發(fā)現(xiàn)每次需要維護(hù)處理的信息量是 \(O(n)\) 的，難以通過(guò)數(shù)據(jù)結(jié)構(gòu)之類的操作。

同時(shí)注意到每一種特征是獨(dú)立的，而該特征的取值只有不超過(guò) \(12\) 種，這啟發(fā)我們對(duì)于取值進(jìn)行操作。

首先對(duì)于每種特征的取值離散化，排名為 \(k\) 的取值的 \(1-k\) 位為 \(0\)，\(k+1-12\) 位為 \(0\)，于是取 \(\min\) 就變成了按位與，取 \(\max\) 變成了按位或。

此時(shí)還是有點(diǎn)難以維護(hù) \(n \times k\) 列的 std::bitset，我們發(fā)現(xiàn)由于是 \(0/1\) 串，于是最多存在 \(2^k\) 種本質(zhì)不同的列。

對(duì)于每個(gè)物品，我們只需要維護(hù)其 \(2^k\) 種列的變化（無(wú)論他有沒有這種列）即可。

P10308 「Cfz Round 2」Osmanthus

如果打表需要打不同類型的表找規(guī)律，而不是對(duì)著某一個(gè)地方死打。

這題的思路也是的，兩種思路，拆位走不通就走 \(x\oplus x=0\)。后者是可以的，我們回歸需要異或上同一個(gè)數(shù)抵消了，于是類似線段樹結(jié)構(gòu)分組，第一組搞完了，異或一遍才能消掉第二組的數(shù)，然后一二合并才能消掉后面的數(shù)。

于是答案就是 \(2^{\lceil logn \rceil}\) ，注意這里的 \(n\) 是去除前導(dǎo) \(0\) 后的序列長(zhǎng)度。

「NOIP 多校聯(lián)考」修改權(quán)值

給定一顆帶權(quán)樹，求修改至少多少個(gè)點(diǎn)的權(quán)值，才能滿足對(duì)于祖先關(guān)系的點(diǎn)，祖先小于等于孫子。

如果往樹上某點(diǎn)的值往什么地方修改那么想法就偏了，因?yàn)闀?huì)上下影響，這種題目要有一個(gè)意識(shí)就是調(diào)整是很自由的，因?yàn)榭梢匀〉龋砸坏┠承〇|西確定了，其他地方必然有一種方式滿足。

我們轉(zhuǎn)化一下問(wèn)題，就是求最多有多少節(jié)點(diǎn)不需要被修改。這個(gè)問(wèn)題就是樹上 LIS，經(jīng)典 P4577 [FJOI2018] 領(lǐng)導(dǎo)集團(tuán)問(wèn)題，參照序列 LIS 求法，我們用 set 啟發(fā)式合并，每次二分更新即可。

CF1503D Flip the Cards

可以發(fā)現(xiàn) \(\forall i,j\)，在兩個(gè)序列中其大小關(guān)系是相反的，所以都有 \(\max(a_i,b_i)>\min(a_j,b_j)\)。故一張卡片同時(shí)包含 \(\le n\) 或者 \(>n\) 是肯定不行的。

所以每張卡牌必定是一面 \(\le n\)，另一面 \(>n\)。按照 \(\le n\) 的一面來(lái)考慮。我們先不管操作次數(shù)只去滿足可行性。假設(shè)現(xiàn)在正面朝上的都是 $ \le n$，設(shè) \(i\) 的反面是 \(f(i)\)。于是最后正面肯定是前面一些 \(i\)，后面一些 \(f(i)\)，反面是前面一些 \(f(i)\) 后面一些 \(i\)。

對(duì)于前面的部分，\(i\) 遞增 \(f(i)\) 遞減，對(duì)于后面的部分 \(i\) 遞減，\(f(i)\) 遞增。于是就等價(jià)于按 \(i\) 排序后的序列劃分成兩個(gè) \(f(i)\) 單調(diào)遞減的序列。這可以通過(guò)開兩個(gè)棧，每次貪心地放入棧頂較小地棧來(lái)完成。

如果要統(tǒng)計(jì)該劃分方案下的代價(jià)最小值，就是看兩個(gè)棧中翻轉(zhuǎn)誰(shuí)需要的代價(jià)小，就選誰(shuí)。

那么如果最優(yōu)化呢，如果要最優(yōu)化不一定是放棧頂較小的，可能使得可行性劣一點(diǎn)能使答案更優(yōu)。

序列貪心問(wèn)題有一種很典型的劃分方式，就是根據(jù)最大最小值來(lái)劃分。

找到所有的位置 \(i\) 滿足 \(\min\limits_{1 \le j \le i} f(j)>\max\limits_{i<j \le n}f(i)\) 來(lái)將序列劃分成若干個(gè)部分，這樣多段的答案顯然是可以拼接的，因?yàn)椴还?\(i\) 的前綴棧是怎么樣的，對(duì)于 \(i\) 后面的部分都不影響。

注意到棧頂?shù)膬蓚€(gè)元素 \(s_1\) 和 \(s_2\) 滿足 \(\min(s1,s2)\) 為序列前綴最小值。當(dāng)我們放入 \(f(i)\) 的時(shí)候，如果有\(s_1>f(i)\) 且 \(s_2>f(i)\)，根據(jù)劃分方式同一段內(nèi)后面必然存在 \(f(j)>\min(s1,s2)\)，如果用 \(f(i)\) 替換 \(\max(s1,s2)\) 必然會(huì)使得后面的 \(f_j\) 不滿足要求，所以我們只能被強(qiáng)制要求放到較小棧了，這就唯一確定了放置方式了。可以直接模擬這個(gè)過(guò)程計(jì)算代價(jià)。

CF1805F Survival of the Weakest

先是 easy 版本，隊(duì)列求前 \(k\) 大是很簡(jiǎn)單的，暴力合并 \(F\) 即可。這里需要注意我們不能在中途取模，這樣會(huì)改變相對(duì)大小關(guān)系，但是為了保持相對(duì)大小我們可以給序列同時(shí)減去 \(a_1\)，在第 \(i\) 步我們減去的 \(a_1\)，后面因?yàn)楹喜?huì)被加上 \(a_1 \times 2^{n-1-i}\)。

然后是 hard 版本，打個(gè)表或者猜測(cè)一下，發(fā)現(xiàn)越到后面編號(hào)越大的位置能被用到的可能性越小。每次只保留前面一部分即可。

CF407D Largest Submatrix 3

很顯然的暴力枚舉左右邊界，對(duì)于上下進(jìn)行雙指針，時(shí)間復(fù)雜度 \(O(n^4)\)。

思考一下復(fù)雜度花在哪里了，主要是掃描線每次推進(jìn)的代價(jià) \(O(n)\) 太大了，由于左右列間距很大，每次推動(dòng)指針向下暴力掃描那一行的信息很浪費(fèi)時(shí)間。考慮移動(dòng)枚舉左右邊界的時(shí)候一點(diǎn)點(diǎn)移動(dòng)繼承上一次的一點(diǎn)信息。

仔細(xì)想想好像有點(diǎn)困難，雖然單純繼承前幾列的信息很容易，但是加入新的一列面臨的是很長(zhǎng)一段新的信息如何整合？我們可以同時(shí)在每次下移下邊界的時(shí)候，只計(jì)算新移動(dòng)出來(lái)的這一行，然后對(duì)于上一行算出來(lái)的上邊界結(jié)果取一下交即可。

總結(jié)一下就是我們維護(hù) \(f_{h,l,r}\) 表示只考慮第 \(h\) 行，列區(qū)間在 \([l,r]\) 之內(nèi)的最多能延生的上邊界（上為開區(qū)間），行內(nèi)更新 \(\max(f_{h,l+1,r},f_{h,l,r-1}) \to f_{h,l,r}\)，同時(shí)我們可以發(fā)現(xiàn)對(duì)于 \(a_{h,l}\) 沒有統(tǒng)計(jì)其在 \(r\) 列的情況（\(a_{h,r}\) 同理），于是我們維護(hù)列的信息 \(lst_{t,j}\) 表示對(duì)于數(shù)字 \(t\) 在第 \(j\) 列上一次出現(xiàn)的位置，然后 \(\max(lst_{a(h,l),r},lst_{a(h,r),l}) \to f_{h,l,r}\)。最后第 \(h\) 行作為下邊界能取到最遠(yuǎn)上邊界就是 \(\max(f_{h,l,r},\max\limits_{c=1}^{h-1}(f_{c,l,r}))\)。