POJ6034---Balala Power!（2017多校聯賽B題）

【題目來源】：http://acm.hdu.edu.cn/showproblem.php?pid=6034

【題意】

26個英文字母，要求用0~25的數字給每一個英文字母指派，把每一個字元串變成一個個數字，然後，求和。有以下幾點，這些構成的數字是26進制，還有，為了求最大的和，必須合理配置設定每一個數字代表哪個字母，并且，這些數字不會有前導0，也就是說，0這個數字不能夠指派給任意字元串的第一個字母。

【思路】

解釋一下樣例1：隻有一個字元串，一個字母，指派為25，最大和值是25。

樣例2：兩個字元串，a在第二位（相當于十位）上有一個，在第一位（相當于個位）上有一個，記成：1 1

b同理，位1 1，那麼這兩個的誰賦最大值25都一樣，得：1*25+1*25*26，1*24+1*24*26，之和便是答案。（至于為啥乘26，想一下十進制，，，每次都乘以10）

樣例3：

字母a在第一位上有2個，在第三位上有一個，記為：2 0 1

字母b在第二位上有兩個，記為：0 2 0

字母c在第一位上有一個，記為：1 0 0

那麼現在進行比較，給哪個賦哪個比較合适，因為各自的最終結果格式都是：第一位數字指派+第二位數字指派26+第三位數字指派*26*26。

思考過後，會發現給a指派25，b指派為24，c指派為23較為合理。

我的大緻思路基本上已經在樣例裡說清楚了，總的來說，就是用數組記下每種字母的位置的個數，然後利用自定義cmp函數進行比較，貪心。

【代碼】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=+;
typedef long long LL;
char s[+];
int len;
struct pp
{
    bool index;//判斷是否在第一位
    bool ervis;//為了标記是不是要指派為0
    bool vis;//标記是否出現過這種字母
    int a[+];
} t[+];
bool cmp(pp u,pp v)
{
    for(int i=len-; i>=; i--)//從高位到低位，逐次比較
    {
        if(u.a[i]>v.a[i])
            return ;
        else if(u.a[i]<v.a[i])
            return ;
    }
    return ;
}
int main()
{
    int n,cases=;
    while(~scanf("%d",&n))
    {
        getchar();
        memset(t,,sizeof(t));
        len=;
        for(int i=; i<=n; i++)
        {
            scanf("%s",s);
            int les=strlen(s);
            t[s[]-'a'].index=;
            for(int j=les-; j>=; j--)
            {
                int x=s[j]-'a';
                if(t[x].vis!=) t[x].vis=;     
                t[x].a[les-j-]++;
            }
            len=max(les,len);//為了使長度一緻，選最大的
        }
        for(int i=; i<; i++)
        {
            for(int j=; j<len-; j++)
            {
                if(t[i].a[j]>)
                {
                    t[i].a[j+]+=t[i].a[j]/;//為了防止出現100 0 和0 1這種情況，先進行字母數量的26進制進位
                    t[i].a[j]%=;
                }
            }
        }
        sort(t,t+,cmp);

        bool flag=;//為了判斷是否需要給字母賦上0
        for(int i=; i>=; i--)
        {
            if(!t[i].vis)
            {
                flag=;
                break;
            }
        }
        if(!flag)//需要的話，就從後往前找沒有出現在字元串首位的字母
        {
            for(int i=; i>=; i--)
            {
                if(!t[i].index)
                {
                    t[i].ervis=;
                    break;
                }
            }
        }
        printf("Case #%d: ",cases++);
        LL sum=;
        int res=;
        for(int i=; i<; i++)
        {
            if(t[i].vis&&!t[i].ervis)
            {
                LL tmp=;
                for(int j=; j<len; j++)
                {
                    if(t[i].a[j])
                        sum=(sum+tmp*t[i].a[j]*res)%mod;
                    tmp=(tmp*)%mod;
                }
                res--;
            }
        }
        printf("%lld\n",sum);
    }
}