OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2009】windy数

【题目描述】

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 

windy想知道,在A和B之间,包括A和B,总共有多少个windy数?

【输入】

两个整数,A,B。

【输出】

一个整数。

【输入样例】

1 10

【输出样例】

9

【数据范围】

20%的数据,满足 1 <= A <= B <= 1000000 。 

100%的数据,满足 1 <= A <= B <= 2000000000 。

【题解】

一道比较简单的数位统计题,首先用DP预处理一个数组f[i][j],表示长度为i、首位为j的windy数数量,则有:

f[i][j]=Σf[i-1][k],|j-k|>1

接下来是统计,待求解区间[A,B]满足区间减法,所以转化为[0,B]-[0,A-1],为了方便,把右区间变为开区间,即[0,B+1)-[0,A),这样就可以直接按位统计了。

【代码】

位运算大展神威,代码相当短。

http://paste.ubuntu.com/7273457/

评论

© OI技术宅 | Powered by LOFTER