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

1
a
2
aa
bb
3
a
ba
abc

Case #1: 25
Case #2: 1323
Case #3: 18221

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 const ll N=1e5+10;
 6 ll fac[N]={1};
 7 ll temp[27];
 8 ll Hash[27];
 9 bool leap[27];
10 char str[N];
11 struct Node
12 {
13     ll cnt[N];
14     ll id;
15     bool operator<(const Node &p)const
16     {
17         for(ll i=N-1;i>=0;i--)
18         {
19             if(cnt[i]>p.cnt[i])
20                 return true;
21             else if(cnt[i]<p.cnt[i])
22                 return false;
23             else;
24         }
25     }
26 }p[27];
27 int main()
28 {
29     ll n,tcase=1;
30     for(ll i=1;i<N;i++)
31         fac[i]=fac[i-1]*26%mod;
32     while(scanf("%lld",&n)!=EOF)
33     {
34         memset(p,0,sizeof(p));
35         memset(Hash,-1,sizeof(Hash));
36         memset(leap,false,sizeof(leap));
37         ll r=0;
38         for(ll i=1;i<=n;i++)
39         {
40             scanf("%s",str);
41             ll len=strlen(str);
42             r=max(r,len-1);
43             if(len!=1)
44                 leap[str[0]-'a']=1;
45             for(ll i=0;i<len;i++)
46                 p[str[i]-'a'].cnt[len-(i+1)]++;
47         }
48         for(ll i=0;i<26;i++)
49         {
50             for(ll j=0;j<N;j++)
51             {
52                 if(p[i].cnt[j]>=26)
53                 {
54                     p[i].cnt[j+1]+=p[i].cnt[j]/26;
55                     p[i].cnt[j]%=26;
56                 }
57             }
58             p[i].id=i;
59         }
60         sort(p,p+26);
61         for(ll i=0;i<26;i++)
62             Hash[p[i].id]=26-(i+1);
63         for(ll i=0;i<26;i++)
64         {
65             if(leap[p[i].id]&&Hash[p[i].id]==0)
66             {
67                 for(ll j=25;j>=0;j--)
68                 {
69                     if(!leap[p[j].id])
70                     {
71                         for(ll k=25;k>=j+1;k--)
72                         {
73                             Hash[p[k].id]=Hash[p[k-1].id];
74                         }
75                         Hash[p[j].id]=0;
76                         break;
77                     }
78                 }
79                 break;
80             }
81         }
82         ll ans=0;
83         for(ll i=0;i<26;i++)
84         {
85             for(ll j=0;j<N;j++)
86             {
87                 ans=(ans+fac[j]*p[i].cnt[j]*Hash[p[i].id]%mod);
88             }
89         }
90         printf("Case #%lld: %lld\n",tcase++,ans%mod);
91     }
92     return 0;
93 }