题解

1 条题解

  • 0
    @ 2024-09-13 11:58:43

    标记数组的运用:

    1、某个编号i,若它既不在a[1]..a[K]中,也不在b[1]..b[K]中,则为答案贡献1;

    2、对于a[1]..a[K]和b[1]..b[K]构成的两个环,分两种情况:

    1)直接统计既在a[1]..a[K]中,也在b[1]..b[K]的编号,算出他们的位置差,并用标记数组记录位置差的数量(delt[t]表示位置差为 t的编号数量),注意对于环的情况,若位置差小于0,则加K。

    2)因为是环,所以把a[1]..a[K]翻转一下,重新统计每个元素的位置,再算位置差。

    上面两种情况中delt[0]..delt[K-1]中最大的是对答案的贡献。

    本题用到了5个标记数组:
    cnta[i]和cntb[i] 都表示i分别在a[1]..a[K]和b[1]..b[K]中是否出现。
    da[i]和db[i]表示i分别在a[1]..a[K]和b[1]..b[K]中的位置。
    delt[i]表示i分别在a[1]..a[K]和b[1]..b[K]中的位置差。

  • 1

信息

ID
2936
难度
9
分类
(无)
标签
递交数
2
已通过
1
通过率
50%
上传者