A
读入的时候遍历检查一遍,看有多少个字符 s.
B
暴力模拟即可。即 i 从第 n 项到第 0 项,每次
。就可求出 f(x)。复杂度 O(nm)。
C
考虑倒推。如果当前最后一步向右走那么就相当于把这个字符插入到最前面,如果是向左走就相当于插入到最后面。直接用一个 deque 维护一下即可。
D
考虑按照
从小往大排序,考虑
表示前 i 个数,第 i 个数必须选最多能选多少个。转移为:
![](https://www.nowcoder.com/equation?tex=dp%5Bi%5D%20%3D%20%5Cmax%20%5Climits_%7Bj%20%3C%20i%2C%20gcd(b%5Bi%5D%2C%20b%5Bj%5D)%20%3E%201%7D%20dp%5Bj%5D%20%2B%201)
考虑如何优化转移,我们维护mx[z]表示:
![](https://www.nowcoder.com/equation?tex=mx%5Bz%5D%20%3D%20%5Cmax%20%5Climits_%7Bz%20%7C%20b%5Bj%5D%2C%20j%20%3C%20i%7D%20dp%5Bj%5D%20%2B%201)
那么,
![](https://www.nowcoder.com/equation?tex=dp%5Bi%5D%20%3D%20%5Cmax%20%5Climits_%7Bd%20%7C%20b%5Bi%5D%2C%20d%20%3E%201%7D%20mx%5Bd%5D)
考虑 mx 和 dp 都可以在
的时间内求得。
考虑
。
所以时间复杂度是 O(nlogn) 的。
读入的时候遍历检查一遍,看有多少个字符 s.
B
暴力模拟即可。即 i 从第 n 项到第 0 项,每次
C
考虑倒推。如果当前最后一步向右走那么就相当于把这个字符插入到最前面,如果是向左走就相当于插入到最后面。直接用一个 deque 维护一下即可。
D
考虑按照
考虑如何优化转移,我们维护mx[z]表示:
那么,
考虑 mx 和 dp 都可以在
考虑
所以时间复杂度是 O(nlogn) 的。
全部评论
(0) 回帖