本题解将会在本人写出其他题后持续更新
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1
题目大意:
你可以将一个数组最左边的数移到末尾,问你移多少次可以使得这个数组非降序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
?我的解法好神秘
起因是一直过不了样例和自己的hack数据,于是便误以为这是一道黄题。
首先我的想法是如果逆序对的个数 >1>1>1 那肯定不行,因为不管怎么换位都有一个逆序对。
然后写完了代码发现过不了样例 222 里面的这组数据
实际应该是-1,但我输出的2。
然后就发现了这个本质上应该是一个环形的数组,所以 a(1)<a(n)a(1)<a(n)a(1)<a(n) 也是一个逆序对。
我还发现了这题数据有着两个很大的问题
* 我的过不了样例2的代码90分(多加点 a(1)<a(n)a(1)<a(n)a(1)<a(n) 的数据)
* ∑n≤2×106,\sum n\le 2\times 10^6,∑n≤2×106, 我数组开的 10510^5105 过了。
时间复杂度:O(n)O(n)O(n)
T2
赛时思路:打表小数据,发现输入的 nnn 是 1,4 或者质数的时候是 YES,否则是NO。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
赛后:
被出题人题解吓哭了,看不懂出题人的思路
时间复杂度:O(T+nloglogn)O(T+n log log n)O(T+nloglogn)
T5
题目大意:
一个长度为 nnn 的数组 aaa,你可以将 aaa 中一个长度不超过 LLL 的连续子数组取相反数(最多这样干一次,可以不干),最后截取 aaa 中一段连续子数组的和作为答案,要求子数组的和尽可能大。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一张图片就概括了我写这道题目的精神状态。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
先把 L=0L=0L=0 判了。
暴力太劣了,好像至少是 O(n2L)O(n^2L)O(n2L) 的,那我们直接正解。
注意到答案可以分成三段,翻转段前,翻转段,翻转段后。
定义 le(i),ri(i)le(i),ri(i)le(i),ri(i) 分别表示从左到右和从右到左长度为 iii 的最大子段和,d(i)d(i)d(i) 前缀和,随后我们枚举翻转段的右端点,拿一个单调队列来维护区间最大值,用区间最大值来更新答案,类似于一个单调队列板题:区间滑动窗口最值问题。
答案对上述以及不翻转的情况求最大值即可
大坑:MEMSET开0X3F3F3F3F也是不够的,直接手动赋值-1E18
时间复杂度:O(n)O(n)O(n)