HDU 6034 Balala Power!

多校第一场的恶心题……因为前几天补题数量太多，博客一直没写，现在补上……

这道题我整整写了一个下午+晚上，mmp，一方面是题目本身恶心，另一方面也反映了我的脑子问题。

题意：
给你指定数量的小写字符串，让你把字母，转化成数字，也就是说 a-z 各自对应 0-25。要求所得数字和最大。
同时转化出的数字不能出现前导零。

思路：
将每个字符的贡献转化成一个25进制的数，用一个 26× 1e5 的数组存储，将其进行排升序。
再是考虑前导零的情况，反向遍历找到第一个不存在前导零的数字标记一下即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int n, len, max_len;
char buf[maxn];
ll mul[maxn];
bool lead[30];
int a[30];

struct ch {
    int num[maxn];
    int pos;
    void init(int id)
    {
        pos = id;
        memset(num, 0, sizeof num);
    }
    bool operator<(const ch& a) const
    {
        for (int i = max_len - 1; i >= 0; i--) {
            if (num[i] != a.num[i])
                return num[i] < a.num[i];
        }
        return false;
    }
} key[27];

int change(char sen[])
{
    int len = strlen(sen);
    for (int i = 0; i < len / 2; ++i) {
        char ch = sen[i];
        sen[i] = sen[len - i - 1];
        sen[len - i - 1] = ch;
    }
    return len;
}

int main()
{
    mul[0] = 1;
    for (int i = 1; i < maxn; i++)
        mul[i] = mul[i - 1] * 26 % mod;
    int cas = 0;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < 26; i++)
            key[i].init(i), lead[i] = false;
        max_len = 0;
        while (n--) {
            scanf("%s", buf);
            len = change(buf);
            if (len > 1)
                lead[buf[len-1] - 'a'] = true;
            max_len = max(max_len, len);
            for (int i = 0; i < len; ++i)
                key[buf[i] - 'a'].num[i]++;
        }
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < max_len; ++j) {
                key[i].num[j + 1] += key[i].num[j] / 26;
                key[i].num[j] %= 26;
            }
            while (key[i].num[max_len] > 0) {
                key[i].num[max_len + 1] += key[i].num[max_len] / 26;
                key[i].num[max_len++] %= 26;
            }
        }
        sort(key, key + 26);
        int zero = -1;
        for (int i = 0; i < 26; ++i)
            if (!lead[key[i].pos]) {
                zero = key[i].pos;
                break;
            }
        ll res = 0, x = 25;
        for (int i = 25; i >= 0; --i) {
            if (key[i].pos != zero) {
                for (int j = 0; j < maxn; j++)
                    res = (res + x * key[i].num[j] * mul[j] % mod) % mod;
                x--;
            }
        }
        printf("Case #%d: %lld\n", ++cas, res);
    }
    return 0;
}