怎么快速幂都能写挂啊我去。怎么数组都能开小啊我去。怎么求最大值写成求最小值啊我去。求不饭堂教程。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A
Difficulty:3- / Easy
Tag:-
没了。
时间复杂度:O(∣S∣)O(|S|)O(∣S∣)。
B
Difficulty:3- / Easy
Tag:-
有了。
时间复杂度:O(n∣S∣)O(n|S|)O(n∣S∣)。
C
Difficulty:3- / Easy
Tag:拓扑排序
注意到 Ai≥iA_i\ge iAi ≥i。题目让我们求的就是最终去哪个自环,而去掉自环后就变成 DAG 了,终点就是答案。所以拓扑排序即可。
不要傻傻写队列了,注意到从 n,n−1,n−2,...,1n,n-1,n-2,...,1n,n−1,n−2,...,1 是一个正确的拓扑序。
时间复杂度:O(n)O(n)O(n)。
E
Difficulty:3.9 / Easy+
Tag:分解质因子
首先分解质因子
然后 LCM 就是所有数每个质因子最多个数次幂的乘积
然后维护最多个数和次多个数就行了
次多维护来干什么()
去掉一个数可能删除了原来出现的最多次数,所以这时得用次多
时间复杂度 O(VloglogV+nlogVlogp)O(V\log\log V+n\log V\log p)O(VloglogV+nlogVlogp)。
F
Difficulty:3.9 / Easy
Tag:Floyd
Floyd 瞎搞即可。
由于 Floyd 实现与矩阵乘法很像,所以就封装到 matrix 类了。
时间复杂度:O(n3logm)O(n^3\log m)O(n3logm)。