首页 > 代码库 > 2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串，贪心+排序】
2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串，贪心+排序】
Balala Power!
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2668 Accepted Submission(s): 562
Problem Description
Sample Input
1a2aabb3abaabc
Sample Output
Case #1: 25Case #2: 1323Case #3: 18221
Source
2017 Multi-University Training Contest - Team 1
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6034
题意：给你n个由小写字母组成的字符串，让你给26个字母分配0-25，每个字符串形成一个26进制的数字，问怎么分
配权值这n个数的和最大。（不能有前导0，但是单个0可以）
题解：每个字符对答案的贡献都可以看作一个 26 进制的数字，问题相当于要给这些贡献加一个 0 到 25 的权重
使得答案最大。最大的数匹配 25，次大的数匹配 24，依次类推。排序后这样依次贪心即可，唯一注意的是不能出现
前导 0。关键就是排序，其实结构体排序可以按照数组字典序排序的！
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll mod=1e9+7; 5 const ll N=1e5+10; 6 ll fac[N]={1}; 7 ll temp[27]; 8 ll Hash[27]; 9 bool leap[27];10 char str[N];11 struct Node12 {13 ll cnt[N];14 ll id;15 bool operator<(const Node &p)const16 {17 for(ll i=N-1;i>=0;i--)18 {19 if(cnt[i]>p.cnt[i])20 return true;21 else if(cnt[i]<p.cnt[i])22 return false;23 else;24 }25 }26 }p[27];27 int main()28 {29 ll n,tcase=1;30 for(ll i=1;i<N;i++)31 fac[i]=fac[i-1]*26%mod;32 while(scanf("%lld",&n)!=EOF)33 {34 memset(p,0,sizeof(p));35 memset(Hash,-1,sizeof(Hash));36 memset(leap,false,sizeof(leap));37 ll r=0;38 for(ll i=1;i<=n;i++)39 {40 scanf("%s",str);41 ll len=strlen(str);42 r=max(r,len-1);43 if(len!=1)44 leap[str[0]-‘a‘]=1;45 for(ll i=0;i<len;i++)46 p[str[i]-‘a‘].cnt[len-(i+1)]++;47 }48 for(ll i=0;i<26;i++)49 {50 for(ll j=0;j<N;j++)51 {52 if(p[i].cnt[j]>=26)53 {54 p[i].cnt[j+1]+=p[i].cnt[j]/26;55 p[i].cnt[j]%=26;56 }57 }58 p[i].id=i;59 }60 sort(p,p+26);61 for(ll i=0;i<26;i++)62 Hash[p[i].id]=26-(i+1);63 for(ll i=0;i<26;i++)64 {65 if(leap[p[i].id]&&Hash[p[i].id]==0)66 {67 for(ll j=25;j>=0;j--)68 {69 if(!leap[p[j].id])70 {71 for(ll k=25;k>=j+1;k--)72 {73 Hash[p[k].id]=Hash[p[k-1].id];74 }75 Hash[p[j].id]=0;76 break;77 }78 }79 break;80 }81 }82 ll ans=0;83 for(ll i=0;i<26;i++)84 {85 for(ll j=0;j<N;j++)86 {87 ans=(ans+fac[j]*p[i].cnt[j]*Hash[p[i].id]%mod);88 }89 }90 printf("Case #%lld: %lld\n",tcase++,ans%mod);91 }92 return 0;93 }
2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串，贪心+排序】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。