F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 5089 >> 暴力自重
GXZlegend @ 2017-11-17 18:49:51
[ Quote ] [ Edit ] [ Delete ] 1#
请自觉n^(5/3)
GXZlegend @ 2017-11-17 19:24:40
[ Quote ] [ Edit ] [ Delete ] 2#
反正你们写暴力的我也不niao你们,开心就好。
自己会不会正解自己心里清楚。
就当你们是交几道Py2B或者nan题
GXZlegend @ 2017-11-17 19:26:00
[ Quote ] [ Edit ] [ Delete ] 3#
暴力过了对我来说也没有坏处,反正出点数据不费多少时间,自己也把这道题A掉了
nzhtl1477 @ 2017-11-17 20:00:18
[ Quote ] [ Edit ] [ Delete ] 4#
可能有n^1.5做法。。。
yanQval @ 2017-11-17 20:14:36
[ Quote ] [ Edit ] [ Delete ] 5#
楼上+1
test_tset @ 2017-11-18 17:04:59
[ Quote ] [ Edit ] [ Delete ] 6#
好像是裸的块状链表吧。。。。。
test_tset @ 2017-11-18 17:05:41
[ Quote ] [ Edit ] [ Delete ] 7#
有没有log的做法呢
nzhtl1477 @ 2017-11-18 17:46:27
[ Quote ] [ Edit ] [ Delete ] 8#
块状链表怎么做啊orz
test_tset @ 2017-11-18 19:19:07
[ Quote ] [ Edit ] [ Delete ] 9#
感觉应该比较简单啊,维护 每个块的 前缀最小值 和后 缀最小值 和整体最小值就行了吧, 难道我又想错了,还是我又读错题了?
test_tset @ 2017-11-18 19:33:26
[ Quote ] [ Edit ] [ Delete ] 10#
我怎么感觉 线段树 就能做到 N*LOG(N)呢?? 还是 先指出我的算法有没有BUG吧。。。
nzhtl1477 @ 2017-11-18 22:01:03
[ Quote ] [ Edit ] [ Delete ] 11#
区间加怎么快速维护块前缀,后缀,整体最小值啊。。。
test_tset @ 2017-11-19 12:57:55
[ Quote ] [ Edit ] [ Delete ] 12#
对于整个快+x直接 将最小值加x就行了,不在整个快,暴力重构嘛,暴力的复杂度当然是sqrt(n)的了。。。
1098643527 @ 2017-11-19 14:52:06
[ Quote ] [ Edit ] [ Delete ] 13#
好像不行吧、、、
test_tset @ 2017-11-19 15:16:38
[ Quote ] [ Edit ] [ Delete ] 14#
暂时没有看出来BUG啊,很多时候 敲的时候发现是死掉了,敲之前死活看不出来死在哪里了啊
nzhtl1477 @ 2017-11-19 15:55:10
[ Quote ] [ Edit ] [ Delete ] 15#
~
test_tset @ 2017-11-19 21:02:48
[ Quote ] [ Edit ] [ Delete ] 16#
啊,是求和啊,加X的时候我当成了一个数字啊。。。。
nzhtl1477 @ 2017-11-20 08:07:28
[ Quote ] [ Edit ] [ Delete ] 17#
额。。。
GXZlegend @ 2017-11-22 14:37:22
[ Quote ] [ Edit ] [ Delete ] 18#
我觉得应该把这帖子顶上去..
GXZlegend @ 2017-11-22 14:37:22
[ Quote ] [ Edit ] [ Delete ] 19#
我觉得应该把这帖子顶上去..
GXZlegend @ 2017-11-22 14:37:22
[ Quote ] [ Edit ] [ Delete ] 20#
我觉得应该把这帖子顶上去..
GXZlegend @ 2017-11-22 14:37:22
[ Quote ] [ Edit ] [ Delete ] 21#
我觉得应该把这帖子顶上去..
save_code @ 2017-11-22 15:48:49
[ Quote ] [ Edit ] [ Delete ] 22#
恩,我又想到了一个算法,还是块状链表:

对于每一个块,维护 3个 长度为块大小的单调队列,分别是前缀,后缀和整体,队列 的权值 单调递减,然后 相邻 两点的斜率 单调递增。。。

然后 对于 一个快+x 如果队列开头 的差值<x 删除对头元素,这样应该是 根号N的算法 啊,感觉也不难嘛。。。。
GXZlegend @ 2017-11-22 15:50:06
[ Quote ] [ Edit ] [ Delete ] 23#
但是重构一个块的时间复杂度是size^2的啊,毕竟要把所有长度的子区间取出来啊..
save_code @ 2017-11-22 15:52:16
[ Quote ] [ Edit ] [ Delete ] 24#
重构一个快是size吧, 预处理出sum[i] 吧
save_code @ 2017-11-22 15:53:11
[ Quote ] [ Edit ] [ Delete ] 25#
额,好像是平方的,我有时间了再想想
GXZlegend @ 2017-11-22 15:57:16
[ Quote ] [ Edit ] [ Delete ] 26#
所以解决方法就是令size=n^1/3
然而这样就被暴力shi过了..
save_code @ 2017-11-22 16:01:02
[ Quote ] [ Edit ] [ Delete ] 27#
btw, 把块的大小设为 n^(1/3)是不是就变成了 n^(5/3)
GXZlegend @ 2017-11-22 16:03:29
[ Quote ] [ Edit ] [ Delete ] 28#
是的..
save_code @ 2017-11-22 16:07:31
[ Quote ] [ Edit ] [ Delete ] 29#
n^(5/3)已经很接近 N^2了,是不好卡,可以 继续优化标算,看能不能搞出复杂度更低的算法呀。。。
GXZlegend @ 2017-11-22 18:30:49
[ Quote ] [ Edit ] [ Delete ] 30#
要不把N开到10^6?然后一组数据100s
nzhtl1477 @ 2017-11-22 18:34:11
[ Quote ] [ Edit ] [ Delete ] 31#
这个题有nsqrt( n )做法。。。
nzhtl1477 @ 2017-11-22 18:37:10
[ Quote ] [ Edit ] [ Delete ] 32#
不过常数还是巨大无比
GXZlegend @ 2017-11-22 18:52:40
[ Quote ] [ Edit ] [ Delete ] 33#
nsqrt(n)。。。怎么做啊
nzhtl1477 @ 2017-11-22 18:54:51
[ Quote ] [ Edit ] [ Delete ] 34#
暂时不打算透露。。(打算出到YNOI吧)
GXZlegend @ 2017-11-22 18:57:57
[ Quote ] [ Edit ] [ Delete ] 35#
好吧。。。
nzhtl1477 @ 2017-11-22 18:59:20
[ Quote ] [ Edit ] [ Delete ] 36#
而且这个常数似乎也是非常大
nzhtl1477 @ 2017-11-22 18:59:34
[ Quote ] [ Edit ] [ Delete ] 37#
而且感觉很难写。。
nzhtl1477 @ 2017-11-22 19:01:20
[ Quote ] [ Edit ] [ Delete ] 38#
我已经写了两天了。。。
GXZlegend @ 2017-11-22 19:03:05
[ Quote ] [ Edit ] [ Delete ] 39#
如果有n^{5/3}跑不过n^2的话,
n^{3/2}也不一定跑得过n^{5/3}吧。。
nzhtl1477 @ 2017-11-22 19:03:56
[ Quote ] [ Edit ] [ Delete ] 40#
n^(5/3)跑不过n^2是因为n^2是暴力
n^(3/2)跑过n^(5/3)应该是绝对性的
GXZlegend @ 2017-11-22 19:08:04
[ Quote ] [ Edit ] [ Delete ] 41#
希望是吧...别再让暴力踩了...
nzhtl1477 @ 2017-11-22 19:08:43
[ Quote ] [ Edit ] [ Delete ] 42#
希望能写出来。。。
GXZlegend @ 2017-11-22 19:09:18
[ Quote ] [ Edit ] [ Delete ] 43#
dalao加油。。。
nzhtl1477 @ 2017-11-22 19:10:25
[ Quote ] [ Edit ] [ Delete ] 44#
不过有可能是我写法太sb了。。。
1430586275 @ 2017-11-25 08:00:36
[ Quote ] [ Edit ] [ Delete ] 45#
讲道理,出题人出这个题的时候没有点b tree吗?
GXZlegend @ 2017-11-25 08:16:27
[ Quote ] [ Edit ] [ Delete ] 46#
要不您暴力跑得过我正解也行啊
cghAndy @ 2017-11-25 10:36:10
[ Quote ] [ Edit ] [ Delete ] 47#
请问怎样可以优化得更快?
GXZlegend @ 2017-11-25 10:50:15
[ Quote ] [ Edit ] [ Delete ] 48#
块的大小设为2*cbrt(n)比较快
nzhtl1477 @ 2017-11-25 12:23:52
[ Quote ] [ Edit ] [ Delete ] 49#
nsqrt( n )算法本机1e5可以卡暴力3倍。。。
不过bzoj上面好像calloc相当的慢所以并没有明显优势
nzhtl1477 @ 2017-11-25 12:26:37
[ Quote ] [ Edit ] [ Delete ] 50#
不过我写的的确很丑
[Top] [Previous Page] [Next Page]

HOME Back