offer收割赛67 题目简析

1
0

题解

序列

相当于 a 不能有两个前缀的差是 P 的倍数,也就是前缀模 P 后两两不同,所以答案是 \prod_{i=1}^{n}P-I

时间复杂度:O(n)

彩球

显然答案是 k^n,我们可以用快速幂求 k^n mod P

问题在于如果是用c++写的话,两个 10^18 规模的数乘起来可能用 64 位整数存不下,所以需要写一个类似快速幂的快速乘

时间复杂度:O(\log^2{n})

最优子段

最优的子段显然要么是最大子段和,要么是最小子段和,所以都试一下就好了

时间复杂度:O(n)

公路收费

先枚举会议所在的城市,然后可以算出每条高速公路的收费,选最高的 k 条就好了

时间复杂度:O(n^2\log{n})

0 answer(s)

write answer 切换为英文 切换为中文


转发分享