【2017 Multi-University Training Contest

【Link】:http://acm.hdu.edu.cn/showproblem.php?pid=6034

【Description】

给你n个字符串;
每个字符串都仅由小写字母组成;
然后,你可以把每个小写字母都映射成0..25中的任意一个数字;
(两个不同的字母不能映射成相同数字);
组成的26进制数;
问这n个26进制数的最大和是多少;

【Solution】

记录每个字母在哪一位上出现过多少次;
->其实就是记录每个字母在某些位权上的系数;
然后;
把占的位权总和最多的字母优先往前放就好;
可以用一个vector< int > v来完成比较的过程;
v的大小设置为MAXN=105;
这样就能记录每个字母在某一位上的位权了;
(最右边是最低位权,代表26^0)
这样就能按照类似字符串的比较方式进行比较了;
把大的字母放在前面即可;(没必要知道是哪个字母,直接乘上答案就好);
做的时候,每一位都要进位;
这样才能用字符串的比较方式进行比较;
直接用sort会超时;
用冒泡排序;
记录每个字母的最高位权;
如果最高位权不一样;
则直接比较最高位权就好;
这样就没必要整个MAXN的vector都同时比较了;
因为不能有前导0;
所以在做的时候;
需要知道哪些字母是能够为0的;
(长度大于1的字符串的开头字母都不能为0)
做的时候,从最末尾开始,往前找最小的位权,且能够为0;把它放到末尾(表示替换成0);
然后再从后往前整体向左移动一位;
这样能保证合法的情况下最大;

【NumberOf WA】

10+

【Reviw】

贪心那一块没有好好想,错了好几次;
然后最高位权不相同直接判大小的优化也没有一开始就加;
挺挣扎的一道题吧.

【Code】

#include <vector>
#include <cstring>
#include <cstdio>
#define int long long
using namespace std;
const int MAXN =1e5+5;
const int INF = 0x3f3f3f3f;
const int M = 1e9+7;
struct node{
    vector <int> v;
    int ok,mi;
}ar[30];
bool cmp(node a,node b)
{
    return a.v>b.v;
}
char s[MAXN];
int mm[MAXN];
int n;

main()
{
    //freopen("F:\rush.txt","r",stdin);
    //ios::sync_with_stdio(false);
    mm[0] = 1;
    for (int i = 1;i <= MAXN-1;i++)
        mm[i] = (1LL*mm[i-1]*26)%M;
    int ww = 0;
    for (int i = 0;i <= 25;i++){
        ar[i].v.resize(MAXN);
        for (int j = 0;j <= MAXN-1;j++)
            ar[i].v[j] = 0;
    }
    while(~scanf("%lld",&n))
    {
        for (int i = 0;i <= 25;i++){
            for (int j = 0;j <= MAXN-1;j++)
                ar[i].v[j] = 0;
            ar[i].ok = 0;
            ar[i].mi = INF;
        }
        while(n--)
        {
            scanf("%s",s);
            int len = strlen(s);
            if(len!=1)
                ar[s[0]-'a'].ok=1;
            for(int i=len-1,ji=MAXN-1;i>=0;i--,ji--)
            {
                int ind = s[i]-'a';
                ar[ind].v[ji]++;
            }
        }

        for (int i = 0;i <= 25;i++){
            for (int j = MAXN-1;j>=1;j--){
                if (ar[i].v[j]>25){
                    ar[i].v[j-1]+=ar[i].v[j]/26;
                    ar[i].v[j]%=26;
                }
            }
            for (int j = 0;j <= MAXN-1;j++)
                if (ar[i].v[j]){
                    ar[i].mi = j;
                    break;
                }
        }


        bool ok = false;
        while (!ok){
            ok = true;
            for (int i = 0;i <= 24;i++)
                if (ar[i].mi > ar[i+1].mi || (ar[i].mi == ar[i+1].mi && ar[i].v < ar[i+1].v)){
                        swap(ar[i],ar[i+1]);
                        ok = false;
                }
        }

        int i;
        for(i=25;i>=0;i--)
        {
            if(!ar[i].ok)break;
        }
        node temp = ar[i];
        for (int j = i;j<=24;j++)
            ar[j] = ar[j+1];
        ar[25] = temp;

        int ans = 0;
        for(int i=0,j=25;i<=25;i++,j--){
            int temp = 0;
            for (int k = 0,l = MAXN-1;k <= MAXN-1;k++,l--)
                temp= (temp + (mm[l]*ar[i].v[k])%M)%M;

            ans = (ans + 1LL*temp*j%M)%M;
        }
        printf("Case #%lld: %lld
",++ww,ans);
    }
    return 0;
}