首页 > ACM题库 > HDU-杭电 > HDU 4151-The Special Number-递推-[解题报告]HOJ
2015
04-16

HDU 4151-The Special Number-递推-[解题报告]HOJ

The Special Number

问题描述 :

In this problem, we assume the positive integer with the following properties are called ‘the special number’:
1) The special number is a non-negative integer without any leading zero.
2) The numbers in every digit of the special number is unique ,in decimal system.
Of course,it is easy to check whether one integer is a ‘special number’ or not, for instances, 1532 is the ‘special number’ and 101 is not. However, we just want to know the quantity of the special numbers that is less than N in this problem.

输入:

The input will consist of a series of signed integers which are not bigger than 10,000,000. one integer per line. (You may assume that there are no more than 20000 test cases)

输出:

The input will consist of a series of signed integers which are not bigger than 10,000,000. one integer per line. (You may assume that there are no more than 20000 test cases)

样例输入:

10
12

样例输出:

9
10

/*
分析:
    哎~,原来n还可以读入负数啊,表示蛋都酥了……
    很少拿第一0.0,思路在代码里,应该挺容易理解的~

                                             2012-07-10
*/

#include"stdio.h"
int main()
{
	int n;
	int t1[10];
	int ans;
	int i,j;
	int a,b,t;
	int num[10],k;
	int hash[10];
	int fac[10];


	fac[0]=1;
	for(i=1;i<10;i++)	fac[i]=fac[i-1]*i;
	t1[0]=1;
	for(i=1;i<10;i++)	t1[i]=9*fac[9]/fac[9-(i-1)];


	while(scanf("%d",&n)!=-1)
	{
		if(n<=0)	{printf("0\n");continue;}
		if(n<10)	{printf("%d\n",n-1);continue;}


		k=0;
		while(n)
		{
			num[k++]=n%10;
			n/=10;
		}
		a=0;
		b=k-1;
		while(a<b)
		{
			t=num[a];
			num[a]=num[b];
			num[b]=t;
			a++;
			b--;
		}


		ans=0;


		for(i=0;i<10;i++)	hash[i]=1;
		for(i=1;i<k;i++)	ans+=t1[i];
		ans+=(num[0]-1)*fac[9]/fac[10-k];
		hash[num[0]]=0;
		for(i=1;i<k;i++)
		{
			for(j=0;j<num[i];j++)
			{
				if(hash[j])	ans+=fac[9-i]/fac[10-k];
			}
			if(hash[num[i]]==0)	break;
			hash[num[i]]=0;
		}


		printf("%d\n",ans);
	}
	return 0;
}

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

参考:http://blog.csdn.net/ice_crazy/article/details/7732841


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”