这题如果N,M加一两个0如何做

P4168 [Violet] 蒲公英

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 用分块,可以实现时间复杂度和空间复杂度都为O(n\sqrt n),是否足够?


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都可能超时,n=4\times 10^5n\sqrt n=2.5\times 10^8,空间大约要1GB,时间空间都不够

我们还是NOIP之后再考虑是否应对这些毒瘤情况吧


by degage @ 2018-11-01 21:17:12

TQL,强势围观两位大佬


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新出的题


| 下一页