题目
求区间 [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<10的时候好算
其他的目前还不知道怎么算

写了有些错误还没改过来
好长
#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;
}

我把三种情况分开了。。。
好难写啊  特别是对于p是两位的 并且十位和个位不一样的情况

#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;
}

稍微修正了一下 不过还是错的。。还没测出来

#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 n+1;
    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)+count2(n%b[i],p)+f2(c[i],a2,i-1,p);

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



    }else
    {
        return (n/b[i])*count2(c[i],p)+count2(n%b[i],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 n+1;
    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)+count3(n%b[i],p)+f3(c[i],a,a2,i-1,p);

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



    }else
    {
        return (n/b[i])*count3(c[i],p)+count3(n%b[i],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;
}

再贴一个 ，，，不知道哪里错了  测了100多组数据 和那个前面那个暴力解得一样啊

#include <iostream>
#include <algorithm>
using namespace std;
long long count2(long long n,long long p);
long long count3(long long n,long long 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(long long n,long long p)
{
if(n<10) {

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

     long long i=0;
     while(b[i+1]<=n) i++;
     long long a=n/b[i];
     if(a==p){
        return (n/b[i])*count1(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(long long n,long long a2,long long d,long long 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(long long n,long long p)
{
    if(n<p) return n+1;
    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)+count2(n%b[i],p)+f2(c[i],a2,i-1,p);

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



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



}
int f3(long long n,long long a1,long long a2,long long d,long long 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(c[d],a1,a2,d-1,p);
    }
        else
        {
        return (m)*count3(c[d],p);
        }





    }else{
        if(m>a1){
            return (m-1)*count3(c[d],p)+count3(n%b[d],p)+f3(c[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(long long n,long long p)
{
if(n<p) return n+1;
    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)+count3(n%b[i],p)+f3(c[i],a,a2,i-1,p);

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



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

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

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

   if(d==1)
   {
     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;
}