A - Olympiad

Description
You are one of the competitors of the Olympiad in numbers. The problem of this year relates to beatiful numbers. One integer is called beautiful if and only if all of its digitals are different (i.e. 12345 is beautiful, 11 is not beautiful and 100 is not beautiful). Every time you are asked to count how many beautiful numbers there are in the interval [a,b](a <= b). Please be fast to get the gold medal!

Input
The first line of the input is a single integer T (T <=1000), indicating the number of testcases.
For each test case, there are two numbers a and b, as described in the statement. It is guaranteed that 1 <= a <= b <= 100000.

Output
For each testcase, print one line indicating the answer.

Sample Input
2
1 10
1 1000

Sample Output
10
738
题意：
求输入的范围内有多少个美丽数（这里说的美丽数是指每一位上的数字都不相同，eg:12345），输入的第一行是单个整数T (T <=1000)，表示测试用例的数量。对于每个测试用例，都要输入两个数字a和b圈定范围。保证1 <= a <= b <= 100000。
这题如果直接用几个循环来暴力求，因为空间复杂度太大，会导致tle，所以想到我们可以借用打表思想。
具体实施：我们可用被调来完成判断大的范围里的每个数是不是美丽数，然后我们另开一个数组用来存美丽数的个数，如果是美丽数就加一，反之不加一。
题解：
判断美丽数：

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int x,c,a[10]={0},j;//a[10]用来计算每位数存在的次数
    scanf("%d",&x);
    while(x>0)//while(x!=0)
    {
        c=x%10;
        a[c]++;
        x/=10;
        for(j=0;j<10;j++)
        {
            if(a[j]>=2)
            {
                printf("不是美丽数\n");
                exit(0);
            }
        }
    }
    if(x<=0)
        printf("是美丽数\n");
    return 0;
}

下面是此英文题完整解法：

#include<stdio.h>
int p[110000],i,j;
//p[i]是用来统计到i这个数之前有多少个美丽数
void sub()
{
    for(i=1;i<=100000;i++)
    {
        int wms=1;
        int a[10]={0};
        int c;
        int x=i;
        while(x>0)
        {
            c=x%10;
            a[c]++;
            x/=10;
        }
        for(j=0;j<10;j++)
        {
            if(a[j]>=2)
            {
                wms=0;
                break;
            }
        }
        if(wms==0)//wms=0说明i这个数不是美丽数
            p[i]=p[i-1];
        else
            p[i]=p[i-1]+1;
        //不是美丽数则次数不加一，反之加一
    }
}
int main()
{
    sub();
    int T,a,b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&a,&b);
        printf("%d\n",p[b]-p[a-1]);
//前b项和为p[b],因为从第一项开始进行
//要计算a到b之间存在的数，a这一项必须包括在内
//故应该要用前b项的和减去前a-1项，即:p[b]-p[a-1];
    }
}

此题还运用了前缀和思想…前缀和简单讲就是累加。

其中a[i]表示初始的单个数据，d[i]表示前i项的和，表示为：d [ i ] = d [ i - 1 ] + a [ i ]
eg：
[3,5]的区间和实际上就可以表示成d[5]-d[2];