cqwyj @ 2018-11-01 20:53:53
光是目前的数据,vector下标查找的方法不加任何优化(包括输入输出)会疯狂TLE,(我写出来只有25分全是T);开O(N*T)数组部分一加一减暴力统计可以过。我看大家的数组都开得比较大,似乎此题正解是后者了?
如题,若数据加强怎么做,数组O(N*T)就开不下了。虽然vector空间O(N),但时间怕是更惨。
有大神了解吗
by Voldermod @ 2018-11-01 21:04:42
@cqwyj 用分块,可以实现时间复杂度和空间复杂度都为
by cqwyj @ 2018-11-01 21:08:04
@Voldermod 我的意思是分块之后,左右的零头可以暴力统计也可以vector.... 目前不开O2可过方法的空间是:N*根号N,加了一两个0恐怕空间不行....
by Voldermod @ 2018-11-01 21:17:01
@cqwyj 加两个0算了吧,就算加一个0都可能超时,
我们还是NOIP之后再考虑是否应对这些毒瘤情况吧
by degage @ 2018-11-01 21:17:12
by cqwyj @ 2018-11-01 21:24:47
@Voldermod 我傻逼了,网上找了下归纳,好像这类题就没有十万的数据....
by cqwyj @ 2018-11-01 21:27:23
@degage TQL,害怕被两位大佬围观
by Voldermod @ 2018-11-01 21:29:29
@degage Orz
by chen_zhe @ 2018-11-01 21:43:19
@cqwyj 可以
有线性空间的区间众数
by cqwyj @ 2018-11-02 07:18:07
@chen_zhe 大大可以给个相关链接吗
by 142857cs @ 2018-11-24 15:45:05
@cqwyj 应该没有,毕竟是lxl新出的题