首页 > ACM题库 > HDU-杭电 > HDU 3943-K-th Nya Number-动态规划-[解题报告]HOJ
2015
04-14

HDU 3943-K-th Nya Number-动态规划-[解题报告]HOJ

K-th Nya Number

问题描述 :

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.

输入:

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<K_i <2^63).

输出:

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<K_i <2^63).

样例输入:

1
38 400 1 1
10
1
2
3
4
5
6
7
8
9
10

样例输出:

Case #1:
47
74
147
174
247
274
347
374
Nya!
Nya!

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents          
by—cxlove

HDU 3943 K-th Nya Number

http://acm.hdu.edu.cn/showproblem.php?pid=3943

用X个4和Y个7的数为规定的数,然后就是区间统计。

先预处理好dp[i][j][k]表示I位的数中有j个4和k个7的数量。

之后就可以通过高位开始枚举,求出区间内有多少个规定的数,如果询问大于总数,则输出"Nya!";

之后是怎么找到第K大数。

首先可以确定出位数,dp[i][x][y]表示i位时的满足数,那么大于dp[len-1][x][y]而小于dp[len][x][y],len表示目标位数。

确定了位数之后,依旧从高位开始。比如说高位首先是0,而dp[len-1][x][y]小于k,说明0开头的目标说小于所求,所以往后继续找,记得要把之前的减掉。

还得注意一些细节,出现了4和7的情况。

貌似有题解说的是二分查找,没有过多的了解。

另外坑的是 这里的区间是左开右闭。

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100005
#define inf 1<<29
#define MOD 9973
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
LL dp[25][25][25];  
//dp[i][j][k]表示i位的数,有j个4,k个7的数量
LL l,r;
int x,y;
void Init(){
	memset(dp,0,sizeof(dp));
	dp[0][0][0]=1;
	for(int i=1;i<21;i++){
		for(int j=0;j<i;j++)
			for(int k=0;k<i;k++)
				if(j+k<i){
					dp[i][j][k+1]+=dp[i-1][j][k];
					dp[i][j+1][k]+=dp[i-1][j][k];
					dp[i][j][k]+=dp[i-1][j][k]*8; 
					//在高位加上除了4、7以外的8个数字
				}
	}
}
LL get_count(LL n){
	int bit[25],len=0;
	while(n){
		bit[++len]=n%10;
		n/=10;
	}
	LL  ans=0;
	int cx=x,cy=y;
	for(int i=len;i;i--){
		//从高位开始枚举
		for(int j=0;j<bit[i];j++)
			if(j==4){
				if(cx)
			    	ans+=dp[i-1][cx-1][cy];
			}
			else if(j==7){
				if(cy)
					ans+=dp[i-1][cx][cy-1];
			}
			else
				ans+=dp[i-1][cx][cy];
		if(bit[i]==4)
			cx--;
		if(bit[i]==7)
			cy--;
		//如果高位出现的4、7数量已经超过要求,则退出
		if(cx<0||cy<0)
			break;
	}
	return ans;
}
LL slove(LL k){
	int len=1;
	while(1){
		//找到目标数的长度
		if(dp[len-1][x][y]<k&&dp[len][x][y]>=k)
			break;
		len++;
	}
	LL ret=0;
	int cx=x,cy=y;
	for(int i=len;i;i--){
		//从高位开始从小枚举
		for(int j=0;j<10;j++){
			int tx=cx,ty=cy;
			if(j==4){
				tx--;
				if(tx<0)
					continue;
			}
			if(j==7){
				ty--;
				if(ty<0)
					continue;
			}
			if(dp[i-1][tx][ty]>=k){
				ret=ret*10+j;
				cx=tx;
				cy=ty;
				break;
			}
			k-=dp[i-1][tx][ty];
		}
	}
	return ret;
}
int main(){
	int t,cas=0;
	scanf("%d",&t);
	Init();
	while(t--){
		scanf("%I64d%I64d%d%d",&l,&r,&x,&y);
		LL a=get_count(r+1);
		LL b=get_count(l+1);  //注意是左开区间,悲剧了好久
		int q;
		scanf("%d",&q);
		printf("Case #%d:\n",++cas);
		while(q--){
			LL k;
			scanf("%I64d",&k);
			if(k>a-b)
				puts("Nya!");
			else
	        	printf("%I64d\n",slove(k+b));
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7822804


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。