（数位dp）吉利数字 区间k大

时间：2022-12-16 11:59:04

【题目描述】

中国人喜欢数字6和8。特别地，一些人喜欢满足含有特定个数6和8的数。现在请求出，在区间[L,R]之间的第K大的含有X个6和Y个8的数。

【输入】

输入的第一行包括4个数字，L,R,X,Y。

接下来的一行给出该组数据的询问数Q。

接下来Q行中，每行有一个整数K。

【输出】

对于某个询问，输出一行，为对应的第K大的数。如果不存在这个数则输出“That's too bad!”

【输入样例】

 1 1000 1 1

10

1

2

3

4

5

6

7

8

9

100

【输出样例】

       68

86

168

186

268

286

368

386

468

That's too bad!

【数据范围】

  对于30%的数据，1<=L<=R<=100000

  对于100%的数据，1<=L<=R<=10^18

对于100%的数据，1<=X,Y<=18, 1<=Q<=30

暴力老鸽二分查找153ms

（数位dp）吉利数字 区间k大（数位dp）吉利数字 区间k大
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=1e5+5;
  4 int tot,e[30];
  5 long long l,r,x,y,q,k;
  6 long long c[30][30][30];
  7 long long n,m;
  8 template<class t>void red(t &x)
  9 {
 10     int w=1;
 11     x=0;
 12     char ch=getchar();
 13     while(ch>'9'||ch<'0')
 14     {
 15         if(ch=='-')
 16             w=-1;
 17         ch=getchar(); 
 18     }
 19     while(ch>='0'&&ch<='9')
 20     {
 21         x=(x<<3)+(x<<1)+ch-'0';
 22         ch=getchar();
 23     } 
 24     x*=w;
 25 } 
 26 void input()
 27 {
 28     freopen("input.txt","r",stdin);
 29 }
 30 void dv(long long z)
 31 {
 32     tot=0;
 33     while(z)
 34     {
 35         e[++tot]=z%10;
 36         z/=10;
 37     } 
 38     e[tot+1]=0;
 39 }
 40 long long dfs(int pos,bool limit,long long num6,long long num8)
 41 {
 42     if(num6>x||num8>y)
 43         return 0;
 44     if(pos==0)
 45     {
 46         if(num6==x&&num8==y)
 47             return 1;
 48         return 0;
 49     }
 50     if(!limit&&~c[pos][num6][num8])
 51         return c[pos][num6][num8];
 52     int up=limit?e[pos]:9;
 53     long long ans=0;
 54     for(int i=0;i<=up;++i)
 55         ans+=dfs(pos-1,limit&&(i==up),num6+(i==6),num8+(i==8));
 56     if(!limit)
 57         c[pos][num6][num8]=ans;
 58     return ans;
 59 }
 60 long long gettot(long long z)
 61 {
 62     if(!z)
 63         return 0;
 64     dv(z);
 65     memset(c,-1,sizeof(c));
 66     return dfs(tot,1,0,0);
 67 }
 68 bool check(long long ll,long long j,long long z,long long &w)
 69 {
 70     w=gettot(j)-gettot(ll-1);
 71     return w<z;
 72 }
 73 long long getnum(long long z)
 74 {
 75     long long ll=l;
 76     long long rr=r;
 77     long long j,w=z;
 78     while(ll<=rr)
 79     {
 80         j=(ll+rr)>>1;
 81         if(check(ll,j,z,w))
 82         {
 83             ll=j+1;
 84             z-=w;
 85         }
 86         else
 87             rr=j-1;
 88     }
 89     return ll;
 90 }
 91 int main()
 92 {
 93     input();
 94     red(l);
 95     red(r);
 96     red(x);
 97     red(y);
 98     red(q);
 99     n=gettot(l-1);
100     m=gettot(r);
101     while(q--)
102     {
103         red(k);
104         if(n+k>m)
105             printf("That's too bad!\n");
106         else
107             printf("%lld\n",getnum(k));
108     } 
109     return 0;
110 }
dfs

 

标签：

相关文章