1 条题解

  • 0
    @ 2026-11-15 20:48:24

    题目分析

    n≤5n \leq 5 时按样例的方式构造,否则答案一定不小于 44,其实按 44 构造即可,具体方法为 ai=i mod 4+1a_i = i \bmod 4+1。

    因为考虑质数要么为 22 要么为奇数。

    如果两个数异或起来为 22,考虑 x⊕y=2x \oplus y=2,那么一定有 ∣x−y∣=2|x-y|=2,因此两个数模 44 的值不同。

    如果两个数异或起来为奇数,那么两个数奇偶性不同,因此两个数模 44 的值不同。

    所以两个数异或起来为质数,那么模 44 的权值一定不同。

    有些选手利用如下方式构造,给第 ii 个数染色时搜索前 i−1i-1 个数 j∈[1,i−1]j \in [1,i-1],如果 j⊕ij \oplus i 为质数,那么把所有jj 中的颜色提出来,染成第一个没有出现过的颜色,如果所有颜色均出现,那么 k+1k+1,以下是一组反例:

    n=18,k=5:n=18,k=5: 1 2 2 3 1 4 4 3 1 2 2 3 1 4 4 3 1 5

    • 1

    信息

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