Balala Power!

Balala Power!

题目来源

2017 Multi-University Training Contest - Team 1 - 1002
HDU 6034

题面

描述

Mr.Wang有n个只含小写字母的字符串。他想要对它们施展巴拉拉能量，可以把a到z中的每个字母变成0到25中的数字，但是两个不同的字母必须变成不同的数字。计算这n个字符串再26进制下的和。
Mr.Wang希望你能让这个总和最大化。注意该问题中的每个字符串不能有前导零除非是字符串“0”。保证至少有一个字母不出现在任何一个字符串的开始。
输出对1e9+7取模。

输入

输入含多组数据。
每组数据中，第一行有一个正整数n，表示字符串的个数(1≤n≤100000)
接下来的n行每行有一个只含小写字母的字符串si。(1≤|si|≤100000,∑|si|≤106)

输出

对于每组数据，输出一行“Case #x: y”（不含引号），x表示数据的组号（从1开始），y表示当前数据的答案。

样例

输入

1
a
2
aa
bb
3
a
ba
abc

输出

Case #1: 25
Case #2: 1323
Case #3: 18221

???

(正文加粗)

嚷嚷着说今天我要翻译
结果因为别人wa了十多发忍不住回去改代码
根本看不懂别人的代码决定自己重敲
因为+1 -1写错wa了两发
留下了单题总共17次提交的好记录┑(￣Д ￣)┍
内心崩溃QAAAAAAAAAAAQ

就题目而言的话
题意明白思路清晰！
属于不可多得的我看完题面就有正解 敲起来顺手顺心的题目233

用26进制统计各个字母对结果出现的总权值
当字符串s的第i位为x时，s[x][i]++
s[x][i]满26进1
最后排序各个字符的权值大小
按照从大到小赋值25到0

看起来很对很简单对不对！
确实很对啊！
所以知道他们wa了十多发我真的是懵逼的
拉了个他们的代码和自己wa的代码对拍
突然
-欸你有考虑前导非零吗？
-啊什么前导？
啊啊啊我翻译写了啊！
而且怎么所有人都没有看到这句话啊！
以后翻译是不是还要带加粗重点标记啊喂！！！

关于前导非零的判断
用一个frst数组记录每个字母能否为零
赋frst初始为true
当字母x出现在长度>1的字符串的最高位时，赋frst[x]=false
在最后排序后对每个字母赋值时
寻找到字符fst，使得该字符在frst[fst]==false的前提下权值最小
则字符fst赋值为0
对于原来应赋值 0 ～ (fst-1) 的 赋值为 1 ～ fst
原来赢赋值 （fst+1） ～ n 的不发生改变
便可求得在满足前导非零的前提下的最大sum

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 100010
#define QAQ 1000000007
using namespace std;
int n;
char str[1000010];
int times[26][MAXN],len[26];
bool frst[26];
int ord[26];
bool cmp(int x,int y)
{
    if (len[x]!=len[y])
        return len[x]<len[y];
    for (int i=len[x];i>=1;i--)
        if (times[x][i]!=times[y][i])
            return times[x][i]<times[y][i];
    return false;
}
int main()
{
    int kase=0;
    while (scanf("%d",&n)==1)
    {
        kase++;
        memset(times,0,sizeof(times));
        memset(len,0,sizeof(len));
        memset(frst,true,sizeof(frst));
        for (int i=1;i<=n;i++)
        {
            scanf("%s",str);
            int l=strlen(str);
            if (l!=1)
                frst[str[0]-'a']=false;
            for (int j=1;j<=l;j++)
            {
                int index=str[l-j]-'a';
                times[index][j]++;
                if (j>len[index])
                    len[index]=j;
                int k=j;
                while (times[index][k]>=26)
                {
                    times[index][k]-=26;
                    times[index][++k]++;
                    if (k>len[index])
                        len[index]=k;
                }
            }
        }
        for (int i=0;i<=25;i++)
            ord[i]=i;
        sort(ord,ord+26,cmp);
        long long ans=0;
        int fst=0;
        while (!frst[ord[fst]])
            fst++;
        for (int i=0;i<fst;i++)
        {
            int x=ord[i],y=i+1;
            long long k=1;
            for (int j=1;j<=len[x];j++)
            {
                ans=(ans+k*y%QAQ*times[x][j]%QAQ)%QAQ;
                k=(k*26)%QAQ;
            }
        }
        for (int i=fst+1;i<=25;i++)
        {
            int x=ord[i],y=i;
            long long k=1;
            for (int j=1;j<=len[x];j++)
            {
                ans=(ans+k*y%QAQ*times[x][j]%QAQ)%QAQ;
                k=(k*26)%QAQ;
            }
        }
        printf("Case #%d: %lld\n",kase,ans);
    }
}