题解

3 条题解

  • 0
    @ 2023-03-02 09:35:08

    很暴力的就做了这一题,当选择A进行旋转时,A序列翻倍,然后建一棵主席树,记录点Bi的度数,为了更新用(其实可以O(1)更新),然后长度为n的区间扫一遍。

  • 0
    @ 2023-03-02 09:33:53

    数字大小没有影响,于是令第一个排列中第一个出现的编号为1,第二个出现的编号为2,于是变成最小化第二个排列的逆序对,一开始的逆序对可以O(nlogn)求出,然后考虑把当前第一个数移到最后,若这个数编号为x,明显多了n-x个逆序对,少了x-1个逆序对,就可以O(n)求出所有循环移动第二个排列的情况,然后我开心的交了,开心的WA了,后来才知道,自己忘记考虑移第一个的情况了(其实只要反过来再做一遍)。
    得分:8/10(幸好数据大多是移第二个的?)

  • 0
    @ 2023-03-02 09:32:12

    先树状数组求出不移动的答案,然后一个一个枚举推一下就好。

  • 1

信息

ID
2590
难度
9
分类
数据结构 | 线段树 点击显示
标签
递交数
3
已通过
1
通过率
33%
上传者