Balala Power!

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2668 Accepted Submission(s): 562

Problem Description

Sample Input

1

a

2

aa

bb

3

a

ba

abc

Sample Output

Case #1: 25

Case #2: 1323

Case #3: 18221

Source

2017 Multi-University Training Contest - Team 1

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6034

题意：给你n个由小写字母组成的字符串，让你给26个字母分配0-25，每个字符串形成一个26进制的数字，问怎么分

配权值这n个数的和最大。（不能有前导0，但是单个0可以）

题解：每个字符对答案的贡献都可以看作一个 26 进制的数字，问题相当于要给这些贡献加一个 0 到 25 的权重

使得答案最大。最大的数匹配 25，次大的数匹配 24，依次类推。排序后这样依次贪心即可，唯一注意的是不能出现

前导 0。关键就是排序，其实结构体排序可以按照数组字典序排序的！

下面给出AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll mod=1e9+;

 const ll N=1e5+;

 ll fac[N]={};

 ll temp[];

 ll Hash[];

 bool leap[];

 char str[N];

 struct Node

 {

     ll cnt[N];

     ll id;

     bool operator<(const Node &p)const

     {

         for(ll i=N-;i>=;i--)

         {

             if(cnt[i]>p.cnt[i])

                 return true;

             else if(cnt[i]<p.cnt[i])

                 return false;

             else;

         }

     }

 }p[];

 int main()

 {

     ll n,tcase=;

     for(ll i=;i<N;i++)

         fac[i]=fac[i-]*%mod;

     while(scanf("%lld",&n)!=EOF)

     {

         memset(p,,sizeof(p));

         memset(Hash,-,sizeof(Hash));

         memset(leap,false,sizeof(leap));

         ll r=;

         for(ll i=;i<=n;i++)

         {

             scanf("%s",str);

             ll len=strlen(str);

             r=max(r,len-);

             if(len!=)

                 leap[str[]-'a']=;

             for(ll i=;i<len;i++)

                 p[str[i]-'a'].cnt[len-(i+)]++;

         }

         for(ll i=;i<;i++)

         {

             for(ll j=;j<N;j++)

             {

                 if(p[i].cnt[j]>=)

                 {

                     p[i].cnt[j+]+=p[i].cnt[j]/;

                     p[i].cnt[j]%=;

                 }

             }

             p[i].id=i;

         }

         sort(p,p+);

         for(ll i=;i<;i++)

             Hash[p[i].id]=-(i+);

         for(ll i=;i<;i++)

         {

             if(leap[p[i].id]&&Hash[p[i].id]==)

             {

                 for(ll j=;j>=;j--)

                 {

                     if(!leap[p[j].id])

                     {

                         for(ll k=;k>=j+;k--)

                         {

                             Hash[p[k].id]=Hash[p[k-].id];

                         }

                         Hash[p[j].id]=;

                         break;

                     }

                 }

                 break;

             }

         }

         ll ans=;

         for(ll i=;i<;i++)

         {

             for(ll j=;j<N;j++)

             {

                 ans=(ans+fac[j]*p[i].cnt[j]*Hash[p[i].id]%mod);

             }

         }

         printf("Case #%lld: %lld\n",tcase++,ans%mod);

     }

     return ;

 }

巴特西

2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串，贪心+排序】

Balala Power!

最新文章

热门文章