CF Global Round 29(#2147) 總結(jié)

?

A

void solve() {
	int x,y;
	cin>>x>>y;
	if(x<y) return cout<<"2\n",void();
	--x;
	if(y<x&&y>1) return cout<<"3\n",void();
	cout<<"-1\n";
}

B

可以考慮構(gòu)造 \(i\) 的距離為 \(2i\)，發(fā)現(xiàn)如下構(gòu)造是合法的：

C

考慮 DP。分為四種：

• 當(dāng)前位為兔子，且兔子往左看。
• 當(dāng)前位為兔子，且兔子往右看。
• 當(dāng)前位為空，且之前有兔子往這個(gè)空位看。
• 當(dāng)前位為空，且之前沒有兔子往這個(gè)空位看。

D

全是偶數(shù)的情況，先手選完，后手可以跟著選最優(yōu)。因此貢獻(xiàn)平分。

存在奇數(shù)的情況，一個(gè)奇數(shù)被選了就會(huì)轉(zhuǎn)化成偶數(shù)的情況，在被變成偶數(shù)后貢獻(xiàn)平分。

因此兩人的策略就是依次選當(dāng)前最優(yōu)的奇數(shù)。于是按奇數(shù)個(gè)數(shù)排序即可。

E

最優(yōu)答案一定是優(yōu)先把一個(gè)二進(jìn)制為前綴填滿。考慮計(jì)算 \(f_i\) 表示把前 \(i\) 位填滿的最小代價(jià)，查詢時(shí)二分即可。

考慮貪心。可以從高位往低位填，每次填 \(2^j-(a_i\bmod 2^{j+1})\) 最小的位置，如果已經(jīng)有 1 就可以不用填。

復(fù)雜度 \(O(n\log ^2V+q\log \log n)\)。

H

看起來(lái)很奇怪的題。可以猜奇怪的結(jié)論：顏色數(shù)最多為 \(2\)。

對(duì)顏色數(shù)為 \(1\) 的情況，可以建最小割樹。

剩下的情況，我們讓最小割為偶數(shù)。先把偶權(quán)邊去掉，然后黑白染色，總有一種方案使得每個(gè)點(diǎn)只有偶數(shù)個(gè)同色鄰點(diǎn)，此時(shí)有歐拉回路，則最小割為偶數(shù)。

可以高斯消元解異或方程組給每個(gè)點(diǎn)染色。

I1 & I2

考慮如果有一個(gè)等差數(shù)列（差為 \(1\)），那么可以從中間開始左右反復(fù)跳。

考慮拆成多個(gè)等差數(shù)列，我們需要一種方案使得任意一對(duì)等差數(shù)列都能來(lái)回跳。

考慮相鄰等差數(shù)列間的距離呈指數(shù)增長(zhǎng)，那么可以依次跳等差數(shù)列對(duì) \((2,1),(3,2),(3,1),(4,3),(4,2),(4,1),(5,4)\dots\)，即對(duì)于 \((a,b),(c,d)\) 先跳 \(a,c\) 為第一關(guān)鍵字、\(b,d\) 為第二關(guān)鍵字排序的對(duì)。

但還有一個(gè)問(wèn)題，就是跳完 \((i,j)\) 后怎么切換到跳 \((i,j-1)\)。因?yàn)橹苯犹鴷?huì)使得 \(r_i\to r_{j-1}\to l_i\) 不合法。可以考慮此時(shí)從 \(r_i\) 先往右跳、再往左跳到 \(l_i-1\)，這樣就合法了。