蒟蒻认为桶空间在部分程序中应该开三倍

P1600 [NOIP2016 提高组] 天天爱跑步

Singercoder @ 2020-10-29 16:03:49

原来的深度区间为[1,n],然后需要访问当前点深度-w[i]和+w[i]的桶下标,这个下标区间应当是[-n,2n]的,加了一个偏移量n以后就是[1,3n]的。

当然如果访问下标都到了[2n+1,3n]了那肯定是没有贡献的,特判一下就可以避免这个问题 。

然而实际上不特判开2n桶空间也可以通过luogu数据。


by 素质玩家孙1超 @ 2020-10-29 16:12:06

@Singercoder 然而luogu数据就是当年考场上的官方数据吧


by Singercoder @ 2020-10-29 16:53:22

嗯那应该是当时考场就没能卡掉了


by panyf @ 2020-12-04 18:06:24

两个桶分开不就好了,每个只需要2n


by sleeping_crawlers @ 2022-06-21 08:47:46

考古 + 拜谢!


by carp_oier @ 2023-09-21 15:07:19

@Singercoder

太感谢了!!!!!!!!!

因为这个原因我卡了1h,拜谢。


|