打破纪录!37min 切 ABCD!
4 题用时:2min, 2min, 18min, 15min
A
Difficulty:3- / Easy
Tag:-
显然,交换 A1A_1A1 与值为 nnn 的即可。
时间复杂度:O(tn)O(tn)O(tn)。
B
Difficulty:3- / Easy
考虑分解质因子。注意到 n∣knn|k^nn∣kn,则 nnn 的质因子得包含在 knk^nkn 的质因子内。
由于 nnn 的每个质因子指数一定不超过 nnn,所以 kkk 的指数取 111 即可。
时间复杂度:O(tn)O(t\sqrt n)O(tn )。
C
Difficulty:3.4 / Easy
Tag:-
首先它是往开头加的,太难受了,反转一下当成加在末尾。
由于字典序,前面的数享有最高权力,可以随便诬蔑后面的数,所以直接每次选字典序最小的即可。
选完以后记得删除后面重复的数。
时间复杂度:O(V+∑2Li)O(V+\sum^2 L_i)O(V+∑2Li )。
D
Difficulty:3.6 / Easy
Tag:单调栈
首先想怎么删。
显然每次操作都要把中间最大值尽量往两边移动,最终把整个搞成一个谷状。
我们可以单调栈求出每个点最左边和最右边能搞成谷的最长的长度,求最大值即可。
时间复杂度:O(∑n)O(\sum n)O(∑n)。