1 条题解

  • 0
    @ 2026-11-15 19:02:07

    题目分析

    本题考察了图论的相关知识。

    30pts

    直接爆搜每次的情况并进行去重,时间复杂度为 O(n!)O(n!),后续会给出具体证明。

    +30pts

    令初始的异或和为 xx,拿在手中,相当于每次用手中的数把 aa 中的一个值顶掉,然后把原来的值拿在手里,这也间接说明了状态数是 n!n! 量级的。

    此档分会发现 aia_i 和所有 aia_i 异或后的权值两两不同,我们考虑一个过程,用 xx 替换了 apa_p,然后用 apa_p 替换了 aqa_q,循环下去。

    其实最终一定是要用 bib_i 替换 aia_i 的,而上面的过程又是从 xx 出发走了一条路,按如上方式建图找出环的个数即可统计答案。

    100pts

    我们从 bib_i 向 aia_i 连边(不同位置上相同的数值对应同一个点),然后尝试从 xx 出发遍历每条边。

    注意如果图是一个包含 xx 的连通块,则一定可以找到一条欧拉路径(不一定是回路)覆盖所有边。

    如果图不连通,或 xx 不在连通块内(xx 是孤立点),则答案就是边数再加上连通块数再减去 11(如果 xx 是孤立点就不用减 11)。

    时间复杂度为 O(n)O(n)。

    • 1

    信息

    ID
    164
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者