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
1 a 2 aa bb 3 a ba abc
Sample Output
Case #1: 25 Case #2: 1323 Case #3: 18221
Source
题意：给你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 Node 12 { 13 ll cnt[N]; 14 ll id; 15 bool operator<(const Node &p)const 16 { 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 }
