xtu oj 1131 凹数
Description | ||
| 如果一个十进制数的数码从左到右是先严格单调下降，然后严格单调上升，我们称这个数为凹数。比如说43212，这个数数码从4到1，然后从1到2，为一个凹数；另外比如4352，这个数从4到3，然后从3到5，然后又从5到2，所以不是个凹数。请计算在[a,b]（100<=a<=b<1,000,000）之间有多少个凹数。 输入 第一行是一个整数N，表示样例的个数。 以后每行两个整数a和b。 输出 每行输出一个样例的结果。 | ||
Sample Input | ||
2 100 110 1000 1000000 | ||
Sample Output | ||
9 23532 |
#include<stdio.h>
#define N 1000010
int f[N]={};
void init(){int i,j,k;f[100]=0;for(i=100;i<N;i++){int a[105]={};int t=0,n=i,cnt=0;while(n){a[cnt]=n%10;n/=10;cnt++;}int flag=1;;for(j=0;j<cnt-1;j++){if(a[j]==a[j+1])flag=0;else if(a[j+1]>a[j]){t=j+1;if(t==1)flag=0;break;}}if(t==0)flag=0;for(j=t;j<cnt-1;j++){if(a[j+1]<=a[j]){flag=0;break;}}if(flag)f[i]=1;}for(i=100;i<N;i++){f[i]+=f[i-1];}
}
void sol(){int a,b;scanf("%d%d",&a,&b);printf("%d\n",f[b]-f[a-1]);
}
int main(){int T;scanf("%d",&T);init();while(T--){sol();}
}