hdu 6034 Balala Power! （2017 Multi-University Training Contest

/*
题意：给出只含有小写字母的字符串，分别与0-25相匹配，然后把字符串看成是26进制，求所有字符串转化后的总和
解析：记录字母出现在每个字符串的位置以及出现的总次数，按照其权值从大到小分配25，24，23，...
官方题解:每个字符对答案的贡献都可以看作一个26进制的数字，问题相当于要给这些贡献加一个0到25的权重使得答案最大。
最大的数匹配25，次大的数匹配24依次类推。
排序后这样依次贪心即可，唯一注意的是不能出现前导 0。
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cmath>
#include <cstring>
typedef long long LL;
const LL N = 100000 + 100;
const LL mod = 1000000007;
using namespace std;
struct ss {
    char sc;
    //str用于记录某个字符在个十百千...位置上分别出现的次数
    int str[N];
    int id;
    bool operator < (const ss &a)const
    {
        for(int i = 0; i < N; i++)
            if(str[i] != a.str[i])
                return str[i] > a.str[i];
        return str[N - 1] > a.str[N - 1];
    }
} num[30];
LL k[N] = {1};
void init()
{
    for(LL i = 1; i < N; i++)
        k[i] = (k[i - 1] * 26) % mod;
}
int main()
{
    int n, tim = 1;
    init();
    while(~scanf("%d%*c", &n)) {
        char s[N];
        int ma = 0;
        int tt[30];
        for(int i = 0; i < 26; i++) {
            tt[i] = 0;
            memset(num[i].str, 0, sizeof(num[i].str));
        }
        for(int i = 0; i < n; i++) {
            scanf("%s", s);
            int len = strlen(s);
            //记录不能为前导0的字母，若是只有一个字母，不算是前导0
            if(len > 1)
                tt[s[0] - 'a']++;
            for(int j = 0; j < len; j++) {
                num[s[j] - 'a'].str[len - 1 - j]++;
            }
        }
        int flag = 0;
        for(int i = 0; i < 26; i++) {
            num[i].sc = i + 'a';
            for(int j = 0; j < N; j++) {
                //26进制，所以满26进一
                num[i].str[j + 1] += num[i].str[j] / 26;
                num[i].str[j] = num[i].str[j] % 26 ;
            }
            int c;
            //交换前后位置，权值按照从大到小的顺序
            for(int j = 0; j < N / 2; j++) {
                c = num[i].str[j];
                num[i].str[j] = num[i].str[N - j - 1];
                num[i].str[N - 1 - j] = c;
            }
        }
        sort(num, num + 26);
        int i;
        //排除前导0
        for(i = 25; i >= 0; i--) {
            if(tt[num[i].sc - 'a'] == 0) {
                break;
            }
        }
        ss t;
        for(int j = 25; j >= 0 && j > i; j--) {
            t = num[i];
            num[i] = num[j];
            num[j] = t;
        }
        LL sum = 0;
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < N; j++) {
                if(num[i].str[j]) {
                    sum = (sum + ((25 - i) * num[i].str[j] % mod) * k[N - 1 - j]) % mod;
                }
            }
        }
        printf("Case #%d: %lld
", tim++, sum);
    }
    return 0;
}