2024.6.18
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变量枚举先后顺序
将相同的的值放在一起处理