Safecracker(搜索)
Safecracker(搜索)
1944864971 发表于2年前
Safecracker(搜索)
  • 发表于 2年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

http://acm.hdu.edu.cn/showproblem.php?pid=1015
/
题意;
从所给的一串字符串中选出5个字母假如是(A B C D E)使得A-B^2+C^3-D^4+E^5等于前面的数字
如果有多种答案,就输出字典序最大的五个
已知A=1 B=2 C=3......................
/

include

include

include

int tarNum;
char secret[25];//存放输入的字符串
int num[5];//存放的是选出来的5个字符所对应的数字
int charNum[26];//存放输入某一字符的个数,下标代表哪种字符,charNum[i]代表这种字符有多少个;
int power(int x,int n)//求x的n次方
{
int sum=1;
for(int i=1; i<=n; i++)
sum=sum*x;
return sum;
}
int dfs(int n)
{
if(n==5)
{
int sum=power(num[0],1)-power(num[1],2)+power(num[2],3)-power(num[3],4)+power(num[4],5);
if(sum==tarNum)return 1;//能找到返回1
return 0;//否则返回0
}
for(int i=25; i>=0; i--)//倒着找找到的第一个就是字典序最大的,找到之后就不用在找了
{
if(charNum[i])//如果这个字符没有用完 就继续使用
{
charNum[i]--;//当前使用过一次
num[n]=i+1;//如果不加一那么25代表的就是z了,但是26代表的是z
if(dfs(n+1))//如果搜到就返回不在搜了,因为你是倒着搜的,搜到的第一个就是最大的
return 1;
charNum[i]++;//记得还原,以便下一组用到
}
}
return 0;
}
int main()
{
while(scanf("%d %s",&tarNum,secret))
{
if(tarNum==0&&strcmp("END",secret)==0)break;
int length=strlen(secret);
memset(num,0,sizeof(num));
memset(charNum,0,sizeof(charNum));
for(int i=0; i<length; i++)//假如输入 ABBCCDDD
charNum[secret[i]-'A']++;//charNum[0]=1 charNum[1]=2 charNum[2]=2 charNum[3]=3
if(dfs(0))
{
for(int i=0; i<5; i++)
{
printf("%c",num[i]-1+'A');
}
printf("\n");
}
else printf("no solution\n");
}
return 0;
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: