K-th Nya Number （数位dp+二分）

K-th Nya Number （数位dp+二分）

Arcueid likes nya number very much. A nya number is the number which has exactly X fours and Y sevens(If X=2 and Y=3 , 172441277 and 47770142 are nya numbers.But 14777 is not a nya number ,because it has only 1 four). Now, Arcueid wants to know the K-th nya number which is greater than P and not greater than Q.

Input The first line contains a positive integer T (T<=100), indicates there are T test cases.

The second line contains 4 non-negative integers: P,Q,X and Y separated by spaces.

( 0<=X+Y<=20 , 0< P<=Q <2^63)

The third line contains an integer N(1<=N<=100).

Then here comes N queries.

Each of them contains an integer K_i (0

Output For each test case, display its case number and then print N lines.

For each query, output a line contains an integer number, representing the K_i-th nya number in (P,Q].

If there is no such number,please output "Nya!"(without the quotes).

Sample Input

1

38 400 1 1

10

1

2

3

4

5

6

7

8

9

10

Sample Output

Case #1:

47

74

147

174

247

274

347

374

Nya!

Nya!

题目大概：

给定p,q,x,y,找出在p和q之间的   含有x个4和y个7的数中   第k大个数。

思路：

这个题和昨天做的一道题，类似，都是最简单的数位dp基础上加上二分就好了。

数位dp部分就不说了，谁都会。

在p和q之间二分，利用查找出来的符合条件的数量减去q的符合条件的数量就是第n大的数，利用二分找出第k大个数，就好了，也是基础二分。

主要是精度控制。

代码：

#include #include #include using namespace std;typedef long long LL;LL INF=0xfffffffffLL;int a[65];LL dp[65][65][65];LL x,y;LL sove(int pos,int q4,int q7,int limit){ if(q4>x||q7>y)return 0; if(pos==-1)return (q4==x)&&(q7==y); if(!limit&&dp[pos][q4][q7]!=-1)return dp[pos][q4][q7]; int end=limit?a[pos]:9; LL ans=0; for(int i=0;i<=end;i++) { if(i==4)ans+=sove(pos-1,q4+1,q7,limit&&i==end); else if(i==7) { ans+=sove(pos-1,q4,q7+1,limit&&i==end); } else ans+=sove(pos-1,q4,q7,limit&&i==end); } if(!limit)dp[pos][q4][q7]=ans; return ans;}LL go(LL x){ int pos=0; while(x) { a[pos++]=x%10; x/=10; } return sove(pos-1,0,0,1);}int main(){ int t; LL n; scanf("%d",&t); for(int j=1;j<=t;j++) { printf("Case #%d:\n",j); memset(dp,-1,sizeof(dp)); LL p,q; int n; scanf("%I64d%I64d%I64d%I64d",&p,&q,&x,&y); scanf("%d",&n); LL w1=go(q); LL w2=go(p); while(n--) { LL k; scanf("%I64d",&k); if(k>w1-w2) { printf("Nya!\n"); continue; } LL l=p,r=q,mid; while(l<=r) { mid=(l+r)/2; if(go(mid)-w2

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。