---------------------------------------------------------------------
看到题就懵逼了..
2016.2.17测试总结
2016年2月17日 22:38
-------------------------------------------------------------------------------
NOIP集训-10.26总结
2015年10月26日 17:17
T1T3的暴力都挂了，就靠T2的打表拿了点分...
----------------------------------------------------------------------
[ZJOI2010]count 数字计数
2015年7月08日 23:30
好累...我真的再也不想做数位DP了...
啊，要统计[l,r]以内0~9出现的次数，减一减然后这道题就变成了求(0,k)以内各个数位出现的次数
[1,9]都是一样的，0比较特(e)殊(xin),一会儿再说，先说怎么处理[1,9]的情况
先假设当前要处理的数位为j(1 <= j <= 9)，可以DP得到f[i][j]为i位以内(即(0,10^i)以内)j出现的次数
然后就是讨论3种情况:
(设k十进制共l位，从低到高第p位为b(p))
①首位为0 (f[l - 1][j])
②首位为[1,b(l) - 1] ((b(l) - 1) * f[l - 1[j] ,若b(l) >= j则再加上10^(l - 1))
③首位为b(l),这个情况比较复杂，不过仔细思考一下还是能得出的（具体的看代码吧..)
然后是待求数位为0的情况，首先需要维护两个数组:f[i][0]和h[i],其中f[i][0]的含义和前面一样，h[i]表示算上前缀0，刚好i位的数中0出现次数，这两个都可以DP求（吧...）(反正我是用组合求的...)
然后还是讨论上面三种情况，公式基本不变(还是有些变动，不过都是很好推的，具体看代码吧...)，但是有些地方f[i][j]要换成h[i]
注意有些地方区间的开闭，还有精度啊啥啥的，基本上这道题就可以A了...
[SCOI2009]windy数
2015年7月06日 22:06
写完这道题感觉心好累...这辈子都不想再做数位DP的题了，然而他们说这是道入门题...
首先可以DP得到位数为i，最高位为j的windy数个数g(i,j)
然后对于(0,k)内的windy数个数，可以讨论3种情况：（感觉数位DP就是大讨论..）
（假设总位数为l,假设k的从高到低第t位为bit(t) ）
①最高位为0，位数为[1,l - 1]的windy数个数(Σ(q=1,l-1) Σ(p=1,9) g(p,q))
②最高位为[1,k - 1]，位数为l的windy数个数(Σ(q=1,k-1) g(l,q))
③最高位为k的windy数个数，这个比较复杂，总之是从高位到低位依次确定，伪代码如下：
for i = (len - 1) to 1 , step -1:
for q = 1 to bit(i) - 1 (#) , step 1:
if(|q - bit(i + 1)| > 2)
sum <- sum + g(i,q)
endif
endfor
endfor
注意打#的地方，这里取bit(i) - 1是因为求的是开区间（闭区间的话会麻烦一点）
