云落碎碎念

1. 題面翻譯取自 luogu，本蒟蒻也會安置原題鏈接
2. 不保證文章中不出現(xiàn)“顯然”或者“注意到”，可能會出現(xiàn)“易證”
3. 有寫錯的地方歡迎各位神犇指正

前言

半路上的我，穿上回憶和風(fēng)沙

CF888A

直接模擬

CF888B

橫縱坐標(biāo)獨(dú)立，挑一個最小值貢獻(xiàn)答案，over

CF888C

對于每種顏色統(tǒng)計答案，取 \(\min\) 即可

CF888D

簡單組合數(shù)與錯排問題

CF888E

觀測數(shù)據(jù)范圍，直接折半搜索

CF888F

區(qū)間 DP 好題

首先數(shù)據(jù)范圍提示了 DP，并且根據(jù)這個連通性的神奇結(jié)構(gòu)，想一想也可以想到區(qū)間 DP

記 \(f_{l,r}\) 表示使 \([l,l+1,...,r]\) 連通的方案數(shù)，轉(zhuǎn)移分討 \(l,r\) 是否連邊，枚舉斷點(diǎn)……嗯，不對？

你發(fā)現(xiàn)當(dāng) \(l,r\) 不連邊的時候，對于連接形式為一條鏈的結(jié)構(gòu)，會在斷點(diǎn)枚舉的時候被統(tǒng)計多次

所以我們直接加一維狀態(tài)，記 \(f_{l,r,0/1}\) 表示 \([l,r]\) 是否強(qiáng)制連邊的方案數(shù)

如此隨便轉(zhuǎn)移即可

CF888G

考慮 kruskal 的合并過程與異或的關(guān)系，不難想到把 \(a_i\) 丟到 01Trie 上，而對于 \(a_i \oplus a_j\) 較小的顯然是 01Trie 上 LCA 深度較深的

直接 DFS 按位貪心就好了嘛

后記

雙手握緊，頂在鏡子上，像是和過去的自己，碰了碰拳

完結(jié)撒花！