题目
求区间 [L,R] 内，满足下面条件的整数n有多少个：
n包含整数p，包含是指p的十进制形式是n的十进制形式一部分，例如123456就包含了1、2、3、123、234、123456等等整数，但不包含7、35、235等。

（作者：Lyd）




输入格式

输入的第一行是一个整数T(T<=1000)，表示一共有T组数据。
接下来是T行，每一行是三个非负整数L R p (0<=L,R<=10^8 , L<=R, p<100 , 三个数均不含前导零(即没有多余的0在整数前面,p也不会等于0))。



输出格式

对于每组数据，输出一行，表示满足条件的整数的个数。



输入样例

4
11 13 2
13 19 2
11 13 12
11 113 12



输出样例

1
0
1
2

代码
#include <iostream>
#include <algorithm>
using namespace std;
long long l,r,k;
long long b[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL};
long long countn(long long n, long long p)
{long long d=1,m=p,sum=0;
    while((m=m/10)>0){d++;}
    for(int i=d;i<=10;i++)
    {


        long long temp=n/b[i]-(p==0);
        sum+=temp*b[i-d];
        temp=(n%b[i])/b[i-d];
        if(temp>p)  
        {
            sum+=b[i-d];
        }else if(temp==p)
        {
            sum+=n%b[i-d]+1;
        }


if(b[i]>n) break;

    }



    return sum;

}


int main()
{
    int t;
    cin>>t;
    while(t--)
{cin>>l>>r>>k;
if(l>r) swap(l,r);
cout<<countn(r,k)-countn(l-1,k)<<endl;

}
    return 0;
}
我想问的是，为什么wa了  不明白啊

菜鸟飘过，不是很懂什么意思

题目是：给定一个区间和p，求这个区间内有几个数包含了p
比如5 到100
包含了20个5 有
哦我明白了 算错了
应该是19个  因为55  是一个  我理解错题意

暂时想不出状态转移式
帮忙想下
因为f(n)和f(n/10)关系很多交叉
比如0到100000里面有多少包含121
可能是这样的数  
12121

若是按上面算的话 要减去算重的部分。。。不知怎么减

我这里有个算法, 但是耗时很长, 要不是看题目中有p<100, 我都不贴上来了, (L = 1, R = 100000000, p = 99, 的情况下, 光标要闪20下才出结果)
希望能讨论一下:
1. 0 < L, R <= 10^8, 用32位的int就可以保存了.
2. 用一个大小为8的字符型数组保存每个L的各个位.
3. 你说的像12121中包含121这种情况, 可以用一个变量标记数L有没有测试过.
样例测试和你后面加的两个样例输出都OK,

#include<iostream>

using namespace std;

int main(void)
{
    int n, m, i;
    int L, r, p;
    int k, s;             // 保存L的中间值.
    int t, nt;            // t是测试次数. nt是包含p的个数
    int flat;             // 标记变量, 当L测试过时, 值为1, 否则为0;
    char a[9];

    cin >> t;            // 输入测试次数
    for (; t >= 0; t--) {
        cin >> L >> r >> p;   // 输入一组数

        nt = 0;
        for (; L <= r; L++) {     // 测试从L到R的各个数
            k = L;               
            i = 0;
            flat = 0;
            while (k){                // 取各位数保存到数组
                a[i++] = k%10 + '0';
                k /= 10;
            }
            for (m = i-1; m >= 0; m--) {
                s = 0;
                for (n = m; n >= 0; n--) {
                            s = s * 10 + (a[n] - '0');
                            if (s == p) {
                                nt++;
                                flat = 1;
                                break;
                            }
                            else
                                if (s > p || s == 0)
                                    break;
                        }
                if (flat == 1)
                    break;
            }
        }
            cout << nt << endl;
    }
        return 0;
}

没想出数学的方法去除重复，先给你个暴力遍历的

#include <stdio.h>

int main(void)
{
    unsigned T;
    scanf( "%u", &T );

    for( unsigned i=0; i<T; ++i )
    {
        unsigned L, R, P;
        scanf( "%u%u%u", &L, &R, &P );

        unsigned P_BASE = 1; // 求得P为多少位的数
        for( unsigned m=P; m!=0; P_BASE*=10, m/=10 );

        unsigned num = 0;
        for( unsigned j=L; j<=R; ++j )
        {
            // 判断j是否包含P
            for( unsigned k=j; k>=P; k/=10 )
            {
                if( k%P_BASE == P ) // 包含
                {
                    ++num;
                    break;
                }
            }
        }

        printf( "%u\n", num );
    }

    return 0;
}

最近先做其他去了。没有想这个。p<10的时候好算
其他的目前还不知道怎么算

直接计算包含p的数量，去重是个问题。不如先计算不包含p的数量，再用总数减去。这样DP可行。

写了有些错误还没改过来
好长
#include <iostream>
#include <algorithm>
using namespace std;
long long count2(int n,int p);
long long count3(int n,int p);
long long l,r,k;
long long b[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL};
long long c[]={0,9,99,999,9999,99999,999999,9999999,99999999,999999999LL,9999999999LL,99999999999LL};

long long count1(int n,int p)
{   if(n<0) return 0;
if(n<10) {

    return 1+n-(n>=p);
}

    int i=0;
     while(b[i+1]<n) i++;
     int a=n/b[i];
     if(a==p){
        return count1(n-b[i]+c[i],p);

     }
     else if(a>p) {

        return (n/b[i]-1)*count1(c[i],p)+count1(n%b[i],p);

     }
     else{
       return (n/b[i])*count1(c[i],p)+count1(n%b[i],p);

     }

}
long long f2(int n,int a2,int d,int p)
{

    if(n/b[d]==0&&a2==0) return 0;
    if(n<10) return n+1-(n>=a2);
    int m=n/b[d];
    if(m==0){
        return count2(n,p);
    }
    else{
    if(m>a2)
    {  return (m-1)*count2(c[d],p)+count2(n%b[d],p);

    }else if(m==a2)
    {  return (m)*count2(c[d],p);

    }else{
        return m*count2(c[d],p)+count2(n%b[d],p);

    }

    }


}
long long count2(int n,int p)
{
    if(n<p) return 0;
    if(n<100) return n+1-(n>=p);
    int a=p/10;
    int a2=p%10;
     int i=0;
     while(b[i+1]<n) i++;


    if(n/b[i]>a) {
        return (n/b[i]-1)*count2(c[i],p)+f2(n%b[i],a2,i-1,p);

    }else if(n/b[i]==a){
        return (n/b[i])*count2(c[i],p);



    }else
    {
        return (n/b[i]-1)*count2(c[i],p)+f2(n%b[i],a2,i-1,p);
    }



}
int f3(int n,int a1,int a2,int d,int p )
{
    if(n/b[d]==0&&a2==0) return 0;
    if(n<10) return n+1-(n>=a2);
    int m=n/b[d];
    if(m==0){
        return count3(n,p);
    }
    else{
    if(m>a2)
    {   if(m>a1){
    return (m-2)*count3(c[d],p)+count3(n%b[d],p)+f3(c[d],a1,a2,d-1,p );

    }
        else if(m==a1){
       return (m-1)*count3(c[d],p)+f3(n%b[d],a1,a2,d-1,p );
        }
        else{
             return (m-1)*count3(c[d],p)+count3(n%b[d],p);
        }


    }else if(m==a2)
    {  if(m>a1){
     return (m-1)*count3(c[d],p)+f3(n%b[d],a1,a2,d-1,p);
    }
        else
        {
        return (m)*count3(c[d],p);
        }





    }else{
        if(m>a1){
            return (m-1)*count3(c[d],p)+f3(n%b[d],a1,a2,d-1,p);
        }
        else if(m==a1){
           return m*count3(c[d],p)+f3(n%b[d],a1,a2,d-1,p);
        }
        else
        return m*count3(c[d],p)+count3(n%b[d],p);

    }

    }


}
long long count3(int n,int p)
{
if(n<p) return 0;
    if(n<100)  return n+1-(n>=p);
    int a=p/10;
    int a2=p%10;
    int i=0;
    while(b[i+1]<n) i++;
     if(n/b[i]>a) {
        return (n/b[i]-1)*count3(c[i],p)+f3(n%b[i],a,a2,i-1,p);

    }else if(n/b[i]==a){
        return (n/b[i])*count3(c[i],p);



    }else
    {
        return (n/b[i]-1)*count3(c[i],p)+f3(n%b[i],a,a2,i-1,p);
    }

}
long long countn(int n,int p)
{

   if(n<0) return 0;
   long long d=0,m=p,res=0;
   while(m!=0) {m=m/10;d++;}

   if(d==1)
   {
//cout<<p<<endl;
     res=count1(n,p);


   }else{
   int a=p/10;
   int b=p%10;

if(a==b) res=count2(n,p);
   else res=count3(n,p);


   }

return res;
}


int main()
{
    int t;
    cin>>t;
    while(t--)
{
    cin>>l>>r>>k;
if(l>r) swap(l,r);
//
cout<<r-l+1-countn(r,k)+countn(l-1,k)<<endl;

}
    return 0;
}