思维训练汇总

· · 个人记录

思维训练汇总

2025.11.18

A

题意简述

每次交换两个鞋，求相邻两个配对且左鞋子在左边的最小操作次数。

解题思路

贪心。

每只和最前面的配对，求个逆序对就可以了。

C

题意简述

给定一棵有边权的树，求 \max\limits_{1\le i<j\le n}\operatorname{dis}(i,j)，其中，\operatorname{dis}(i,j) 指树上 i 到 j 的路径上边权异或和。

解题思路

发现 \operatorname{dis} 与根无关，所以指定 1 为根。

令 a_i 为 \operatorname{dis}(1,i)，显然，用一遍 DFS 可以处理出。

我们发现：

\operatorname{dis}(i,j)\\ =\operatorname{dis}(i,\operatorname{lca}(i,j))\oplus\operatorname{dis}(\operatorname{lca}(i,j),j)\\ =\operatorname{dis}(1,i)\oplus\operatorname{dis}(1,\operatorname{lca}(i,j))\oplus\operatorname{dis}(1,j)\oplus\operatorname{dis}(1,\operatorname{lca}(i,j))\\ =\operatorname{dis}(1,i)\oplus\operatorname{dis}(1,j)\\ =a_i\oplus a_j

于是，把 a_i 丢到 01Trie 上去求最大异或对即可。