1 条题解
-
0
题目分析
本题考察了图论的相关知识。
30pts
直接爆搜每次的情况并进行去重,时间复杂度为 ,后续会给出具体证明。
+30pts
令初始的异或和为 ,拿在手中,相当于每次用手中的数把 中的一个值顶掉,然后把原来的值拿在手里,这也间接说明了状态数是 量级的。
此档分会发现 和所有 异或后的权值两两不同,我们考虑一个过程,用 替换了 ,然后用 替换了 ,循环下去。
其实最终一定是要用 替换 的,而上面的过程又是从 出发走了一条路,按如上方式建图找出环的个数即可统计答案。
100pts
我们从 向 连边(不同位置上相同的数值对应同一个点),然后尝试从 出发遍历每条边。
注意如果图是一个包含 的连通块,则一定可以找到一条欧拉路径(不一定是回路)覆盖所有边。
如果图不连通,或 不在连通块内( 是孤立点),则答案就是边数再加上连通块数再减去 (如果 是孤立点就不用减 )。
时间复杂度为 。
- 1
信息
- ID
- 164
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者