题目链接：HDOJ3943

题意：在（P，Q】区间内，第K大的满足条件的数是多少

条件是：数位中有X个4，Y个7


分析：

有X个4，Y个7是很简单的数位dp

dp【pos】【x】【y】：当前pos位，现在已经有了x个4，y个7

注意可以有个小剪枝，即x不能超过X，y不能超过Y


二分的方法与HDOJ 3271 SNIBB相同

题解在这儿呢：HDOJ3271SNIBB

注意开闭区间


二分的时候，求符合条件的解的时候，用个变量记录每次二分后，符合条件的值

分析见代码


注意2的63次方，需要long long


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1050
#define maxnum 1000050
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

LL dp[25][25][25];
int digit[25];
int X,Y;

LL dfs(int pos,int x,int y,bool flag){
	if (pos==0) return x==X&&y==Y;
	if (flag&&dp[pos][x][y]!=-1) return dp[pos][x][y];
	int up=flag?9:digit[pos];
	LL ans=0;
	for(int i=0;i<=up;i++){
		if (x==X&&i==4) continue;
		if (y==Y&&i==7) continue;
		ans+=dfs(pos-1,x+(i==4?1:0),y+(i==7?1:0),flag||i<up);
	}
	if (flag) dp[pos][x][y]=ans;
	return ans;
}

LL calc(LL x){
	int len=0;
	while(x){
		digit[++len]=x%10;
		x/=10;
	}
	return dfs(len,0,0,0);
}

int main(){
	//input;
	int T,n;
	scanf("%d",&T);
	for(int Case=1;Case<=T;Case++){
		memset(dp,-1,sizeof(dp));
		LL P,Q;
		scanf("%I64d%I64d%d%d%d",&P,&Q,&X,&Y,&n);
		LL limit=calc(P);
		printf("Case #%d:\n",Case);
		for(int i=0;i<n;i++){
			LL l=P+1,r=Q+1,K,m;
			//l是第一个符合条件的数
			//r是第一个不符合条件的数
			//在二分判断的过程中，用l做可行解的记录
			//相当于添加了一个ans变量 
			scanf("%I64d",&K);
			while(l<r){
				m=(l+r)>>1;
				if (calc(m)-limit<K) l=m+1;
				else r=m;
			}
			if (l==Q+1) cout<<"Nya!"<<endl;
			else printf("%I64d\n",l);
		}
	}
	return 0;
}