3 条题解
-
0
何老师 (root) LV 0 MOD @ 2023-03-02 09:35:08
很暴力的就做了这一题,当选择A进行旋转时,A序列翻倍,然后建一棵主席树,记录点Bi的度数,为了更新用(其实可以O(1)更新),然后长度为n的区间扫一遍。
-
02023-03-02 09:33:53@
数字大小没有影响,于是令第一个排列中第一个出现的编号为1,第二个出现的编号为2,于是变成最小化第二个排列的逆序对,一开始的逆序对可以O(nlogn)求出,然后考虑把当前第一个数移到最后,若这个数编号为x,明显多了n-x个逆序对,少了x-1个逆序对,就可以O(n)求出所有循环移动第二个排列的情况,然后我开心的交了,开心的WA了,后来才知道,自己忘记考虑移第一个的情况了(其实只要反过来再做一遍)。
得分:8/10(幸好数据大多是移第二个的?) -
02023-03-02 09:32:12@
先树状数组求出不移动的答案,然后一个一个枚举推一下就好。
- 1