1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB

Submit: 8511 Solved: 3838

[][][]

Description

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

【输入样例一】

1 10

【输入样例二】

25 50

Sample Output

【输出样例一】

【输出样例二】

HINT

【数据规模和约定】

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

题解

f[i][j]表示i位数，最高位为j时的满足条件的数的个数。

先预处理出f数组。

对于一个数x，先算位数比它小的数的个数和，再算位数相等，最高位小于它的数的个数和。

最后算前i位相同的数的个数和。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         const int N=15;int a,b;int f[N][N],num[N];using namespace std;void get_f(){	for(int i=0;i<=9;i++){		f[1][i]=1;	}	for(int i=2;i<=10;i++){		for(int j=0;j<=9;j++){			for(int k=0;k<=9;k++){				if(abs(j-k)>=2)f[i][j]+=f[i-1][k];			}		}	}}int solve(int n){	int len=0,ans=0;	while(n){		num[++len]=n%10;		n/=10;	}	num[len+1]=0;	for(int i=1;i
         
          =0;i--){ if(i==0)ans++; for(int j=0;j
          
           =2)ans+=f[i][j]; } if(abs(num[i]-num[i+1])<2)break; } return ans;}int main(){ get_f(); scanf("%d%d",&a,&b); printf("%d\n",solve(b)-solve(a-1)); return 0;}