2025.11.18 ds专项……？

_zSqr_Mahiro_Oyama_ · 2025-11-18 09:14:41 · 个人记录

P5749

考虑一只鞋子肯定是找与它最近的另一侧鞋子匹配。然后可以固定鞋子的方向，比如从右往左，右边的鞋子找左边的鞋子。这样肯定是不劣的。

先按大小和左右记录鞋子的位置，然后从右往左扫，和最近的能匹配的鞋子匹配，此时需要去除这两个位置中间已经匹配过的鞋子，将未匹配设为 1，匹配设为 0，然后就可以用 BIT 快速计算了。时间复杂度 O(n \log n)。

P6619

首先注意到：温度升高时，冰系的能量总和会升高，火系的能量总和会降低，而温度确定时，总能量为冰系能量综合与火系能量总和的最小值的两倍。因此，温度升高时，总能量先升高再降低。

考虑离散化温度，分别开两个 BIT 维护冰系和火系的以温度为下标的前缀和，那么利用 BIT 找出冰系大于火系时的最大能量，与火系大于冰系的最大能量，就可以得到答案。

考虑二分，复杂度 O(n \log^2 n)，期望 60pts。使用 BIT 倍增的 trick，优化到 O(n \log n)，可以通过本题。

P4551

板板题。

注意到异或可差分，令 s_x 为 1 到 x 的边权异或和，则树上两个点 x,y 的异或路径为 s_x \oplus s_y。问题转化为求一个序列中取两个数的异或最大值。把每个 s_x 丢进 01trie 里维护，按位查询即可。时间复杂度 O(n \log V)。