Bakser's Blog

我是逗比。

bzoj3329 xorequ

| Comments

这题搞了好久。。。。
第二问还比较快看出来了,然后第一问蛋疼了许久。
去问faebdc神犇,然后faebdc神犇秒了。。。。

原方程x xor 3x = 2x
可以看作x xor 2x = 3x
然后x xor 2x =(2x+x)
这就看出来x和2x不能有相同位置的1,2x=x<<1,所以就是x中不能有相邻的1.
先看第二问
n位里不能有两个相邻的1的个数,其实就是斐波那契数,打表或者上定义都可以看出来。
然后第一问

dzy神犇:这就是一个裸的数位dp啊。

将我从用第二问结论构造的泥潭里拯救了出来Orz。
然后还是不会。。。。
我的做法:
f[i][j][k]表示有i位,j是1表示可以比n大,0表示小于等于n,k代表最高位是0或1.
转移比较显然吧。
f[i][j][k]=sigma{l=0、1&l和k不同时为1|f[i-1][j|l<a[i-1]][l]}.
好像faebdc神犇秒题大法就是我写挂很久的正常向数位dp。。。。。

Comments

comments powered by Disqus