2024.6.18

T1

题面

给定若干个自然数 \(a_{1\sim n}\) 。
你需要选出其中一些数，然后将你选出的数划分为若干个集合。
你需要最大化每个集合 mex 的异或和，输出这个值。

\(1\le a_i\le n\le 10^6\)

解法

找出所有的 \(0\to1\to2\to\cdots\to x\) 链，每一个链对应集合 \(\{0,1,\cdots,x+1\}\)，考虑构造答案，对所有链按照 \(x\) 从大到小排列，每次枚举每一位，若这一位是 \(0\) ，尝试使这一位为\(1\)，如果为一后当前的数大于 \(x\) 则构造失败，这一位为 \(0\) ，否则为 \(1\)。

方法

• 贪心

T2

题面

给定一棵有根树，树上的每个节点是黑色或白色的。\(1\) 号点是根。
请对于每个白色的点，在子树中找一个黑色的点与其匹配，其中每个黑点只能和一个白点匹配。你需要求出所有白点与其配对的黑点的距离之和最小是多少。
树上两点的距离定义为他们之间简单路径上的边数。
数据保证有解。

\(1\le n\le 10^6\)

解法

从下往上考虑，遇到黑点放入堆，遇到白点取出深度最小的匹配，用可并对实现

方法

• 可并堆

T3

题面

有一张 \(n\) 个点的无向图，每个点有一个点权 。
与 之间有边当且仅当 $a_i&a_j\not=0 $ ，其边权为 \(a_i+a_j\)。 其中 \(\&\) 是按位与。
\(q\) 次询问两个点之间的最短路，若这两点不能互相到达，则输出 \(-1\) 。
注意：若 \(s=t\)，请大家输出 \(s\) 点权的二倍作为答案。

\(1\le n,a_i,q\le 10^6\)

解法

直接建图复杂度太高，考虑优化建图。
对于 \(i\) ，若 \(a_i\) 二进制第 \(j\) 位为 \(1\) ，就连边 \(a_i\to j'\)，边权为 \(a_i\)。易验证等价于原图的建边方法。
考虑 \(s\) 到 \(t\) 的路径的最短路过程：

• \(s\) 到某个虚点 \(x\) ；

• \(x\) 到某个虚点 \(y\)；

• \(y\) 到 \(t\)

这样我们就只需要求出关键点之间的最短路，就可以快速回答询问了。

对于虚点 \(x\) 与 \(y\) 之间的边 \(g[x][y]\) 应为\(2\min\limits_{2^x|a[i]\land2^y|a[i]}a[i]\)，我们可以用后缀和进行处理。
由三段过程中一头一尾的答案是固定的，我们只需要考虑虚点到虚点的过程，预处理出\(res[i][S]=\min_{2^y|S}g[x][y]\)，最后询问时枚举虚点 \(x\) 即可

最后复杂度 \(\mathcal O(m\log m)\)

方法

• 优化建图

• 超集——高维后缀和

• DP预处理

T4

题面

\(1\le n\le 500,1\le x,y\le 2000\)

解法

方法

• 更换DP变量枚举先后顺序

  将相同的的值放在一起处理