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代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+;
const ll N=1e5+;
ll fac[N]={};
ll temp[];
ll Hash[];
bool leap[];
char str[N];
struct Node
{
ll cnt[N];
ll id;
bool operator<(const Node &p)const
{
for(ll i=N-;i>=;i--)
{
if(cnt[i]>p.cnt[i])
return true;
else if(cnt[i]<p.cnt[i])
return false;
else;
}
}
}p[];
int main()
{
ll n,tcase=;
for(ll i=;i<N;i++)
fac[i]=fac[i-]*%mod;
while(scanf("%lld",&n)!=EOF)
{
memset(p,,sizeof(p));
memset(Hash,-,sizeof(Hash));
memset(leap,false,sizeof(leap));
ll r=;
for(ll i=;i<=n;i++)
{
scanf("%s",str);
ll len=strlen(str);
r=max(r,len-);
if(len!=)
leap[str[]-'a']=;
for(ll i=;i<len;i++)
p[str[i]-'a'].cnt[len-(i+)]++;
}
for(ll i=;i<;i++)
{
for(ll j=;j<N;j++)
{
if(p[i].cnt[j]>=)
{
p[i].cnt[j+]+=p[i].cnt[j]/;
p[i].cnt[j]%=;
}
}
p[i].id=i;
}
sort(p,p+);
for(ll i=;i<;i++)
Hash[p[i].id]=-(i+);
for(ll i=;i<;i++)
{
if(leap[p[i].id]&&Hash[p[i].id]==)
{
for(ll j=;j>=;j--)
{
if(!leap[p[j].id])
{
for(ll k=;k>=j+;k--)
{
Hash[p[k].id]=Hash[p[k-].id];
}
Hash[p[j].id]=;
break;
}
}
break;
}
}
ll ans=;
for(ll i=;i<;i++)
{
for(ll j=;j<N;j++)
{
ans=(ans+fac[j]*p[i].cnt[j]*Hash[p[i].id]%mod);
}
}
printf("Case #%lld: %lld\n",tcase++,ans%mod);
}
return ;
}