HDU 5936 Difference 搜索

392人浏览 / 1人评论

题目链接

  • Difference
    • 首先根据f函数的性质可知,f(y,K)的值只与y的各个数位上的数字有关,而与y值本身的大小无关。这一性质暗示可能需要枚举y的数位数字。
    • 根据数据范围进行推算,题中涉及的数的大小不超过10位。
    • 原式x=f(y,K)-y可改写为y=f(y,K)-x。
    • 枚举y的各个数字(0-9)出现的个数,总和上界为10,判断算出的y是否真的符合条件即可。

代码:

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const long long max_bound=(long long)pow(10,10)-1;
int x,k,digits[10],real_digits[10];
long long cnt=0;
inline long long f()
{
	long long res=0;
	for(int i=1;i<=9;++i)
	{
		if(digits[i])
		{
			long long temp=1;
			for(int j=0;j<k;++j)
			{
				temp*=i;
			}
			res+=temp*digits[i];
		}
	}
	return res;
}
inline bool check(long long f)
{
	long long y=f-x;
	if(y<=0||y>max_bound)
	{
		return false;
	}
	memset(real_digits,0,sizeof(real_digits));
	for(int i=0;i<10;++i)
	{
		++real_digits[y%10];
		y/=10;
	}
	for(int i=0;i<=9;++i)
	{
		if(real_digits[i]!=digits[i])
		{
			return false;
		}
	}
	return true;
}
void dfs(int i,int num)
{
	if(i==10||!num)
	{
		int sum=0;
		for(int j=0;j<=9;++j)
		{
			sum+=digits[j];
		}
		if(sum==10&&check(f()))
		{
			++cnt;
		}
		return;
	}
	for(int j=0;j<=num;++j)
	{
		digits[i]=j;
		dfs(i+1,num-j);
		digits[i]=0;
	}
}
int main()
{
	int T,kcase=0;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&x,&k);
		cnt=0;
		dfs(0,10);
		printf("Case #%d: %lld\n",++kcase,cnt);
	}
	return 0;
}

全部评论