CSPS模拟 44

2024-10-06 13:27:59

　　状态不是很好吧

　　这套和前边是一套的，

　　skyh在我旁边AK，好像开了三个对拍又在拼小人

　　

　　T3 正解没调出来，暴力又忘交了qwq

　　当时心情都要爆炸了

　　T1 区间$gcd$乘区间长度的最大值

　　　　暴力是$n^3logn$的，考虑怎么替代$n^2$的无用计算量

　　　　考虑了很久数据结构最后爆闭了

　　　　最后祭出yzh讲的，无脑分治算法

　　　　$gcd$的$log$省不下来，已经$log^2$了

　　　　答案的计算必须$O(1)$，也就是分治区间必须扫一扫就出答案

　　　　能用单调性么？

　　　　从中点出发的区间$gcd$的确是单调的

　　　　所以就是从中间向两边求区间$gcd$，然后两个单调指针

　　　　扫哪边都行，每移动一格就移动另一边的指针到本点$gcd$能整除另一边$gcd$的最远位置

　　　　

　　　　正解利用了从一个点向两边的$gcd$不超过$logn$种来保证复杂度。

　　T2 两种贪心

　　　　一种是两种颜色分别选两端的极值

　　　　另一种是一种颜色把极值选满，让另一种颜色的值域尽量狭窄

　　T3 线段树优化$dp$

　　　　状态定义还挺显然的，没调出来，两行泪

　　　　感觉谁都容易想到，只要能调出来了就是$nb$

最新文章

热门文章