1
20
2015
0

BZOJ3576: [Hnoi2014]江南乐 $O(M \times \ln{M} \times \log{M})$

又被标算虐……虐代码长度虐常数
考虑暴力:对于每个$n$,$sg[n]=mex\{(-1)^{n\%d} sg[n/d+1]\ xor\ (-1)^{d-n\%d}sg[n/d]\}$
可以把sg值压位解决mex。
考虑枚举d,枚举d的倍数之间的区间,把区间内奇偶性相同的位置都|=一个值。用线段树。
但是sg[n/d]的计算顺序不一定对。
所以应该枚举n/d,再枚举d,对每个d扩展一下。
但是这个做法在f<=2时还是不对。
所以特判打表。
这样复杂度就是$O(M \times \ln{M} \times \log{M})$

最近真的是弱到渣了,代码能力奇弱,几乎没有1A的。冬令营都没得去。人生真的是希望渺茫了。会考真的是……

 

 

Category: 未分类 | Tags: | Read Count: 481

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com