Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://acm.hdu.edu.cn/showproblem.php?pid=6034
题意：#
有一个仅由小写字母组成的字符串，要求将a..z的字母，对应到0..25，每个数字只能被一个字母对应，得到一个26进制的数，现在问这个数最大是多少。注意不允许有前导0，除非这个数本身就是0.
思路：#
贪心。看哪个字母的权值最大。
可以用类似高精度加法的方式处理。
对于前导0的部分，用一个bool标记首位（如果字符串长度为1就不标记）
对于26个高精度数的排序，可以用交换id的技巧。
以及，如果排序之后，发现权值最小的数被对应到数字0，但是又在某个长度大于1的字符串的首字母位置出现过。
我初始想当然得，把该字母和最小的可以出现在首位的字母交换….
然而这很错啊？
实际上，更优秀做法是，找到第一个可以出现在首位的字母，然后从该字母后面到结尾，依次前移一位，最后把这个可以出现在首位的字母放在最后。
比如这组数据：
7 abcdefghijklmnopqrstuvwxyz zz yy xx ww uu vv
权值按照从大到小排列
z u v w x y t 显然不如 u v w x y z t 优
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月01日 星期三 00时56分26秒
4File Name :6034.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23const int N=1E5+7;
24const LL mod =1E9+7;
25int n;
26string st[N];
27int cnt[26][N];
28int maxlen;
29int id[26];
30int power[26];
31LL base26[N];
32bool Beg[26];
33void init()
34{
35 ms(Beg,false);
36 ms(cnt,0);
37 maxlen = 0 ;
38 for ( int i = 0 ; i < 26 ; i++) id[i] = i;
39}
40bool small(int *a,int *b)
41{
42 for ( int i = maxlen-1 ; i >= 0 ; i--)
43 {
44 if (a[i]<b[i]) return true;
45 if (a[i]>b[i]) return false;
46 }
47 return false;
48}
49int main()
50{
51 #ifndef ONLINE_JUDGE
52 freopen("./in.txt","r",stdin);
53 #endif
54 int cas = 0 ;
55 base26[0] = 1;
56 for ( int i = 1 ; i < N ; i++) base26[i] = base26[i-1] * 26 % mod;
57 while (~scanf("%d",&n))
58 {
59 init();
60 for ( int i = 1 ; i <= n ; i++)
61 {
62 cin>>st[i];
63 int len = st[i].length();
64 // cout<<"len:"<<len<<endl;
65 maxlen = max(len,maxlen);
66 for ( int j = 0 ; j < len ; j++)
67 {
68 int v = st[i][j]-'a';
69 cnt[v][len-j-1]++;
70 }
71 //如果只有一个字母，不要打首字母标记
72 if (len>1)
73 Beg[st[i][0]-'a'] = true;
74 //忘了不能右前导0的条件了。。。
75 }
76 for ( int i = 0 ; i < 26 ; i++)
77 {
78 for ( int j = 0 ; j < maxlen ; j++)
79 {
80 cnt[i][j+1] += cnt[i][j]/26;
81 cnt[i][j]%=26;
82 }
83 while (cnt[i][maxlen]>0)
84 {
85 cnt[i][maxlen+1] += cnt[i][maxlen]/26;
86 cnt[i][maxlen]%=26;
87 maxlen++;
88 }
89 }
90
91 for ( int i = 0 ; i < 26 ; i++)
92 for ( int j = i+1 ; j < 26 ; j++)
93 if (small(cnt[id[i]],cnt[id[j]]))
94 swap(id[i],id[j]);
95// for (int i = 0 ; i < 26 ; i++) printf("id[%d]:%c%c",i,char(id[i]+'a'),i==25?'\n':'\n');
96
97 int notBEG = -1;
98 if (Beg[id[25]])
99 {
100 for ( int i = 24 ; i >= 0 ; i--)
101 {
102 if (!Beg[id[i]])
103 {
104 notBEG = i;
105 break;
106 }
107 }
108 }
109 //cout<<"notBEG:"<<notBEG<<endl;
110 if (notBEG!=-1)
111 {
112 int tmp = id[notBEG];
113 for ( int i = notBEG +1 ; i < 26 ; i++) id[i-1] = id[i];
114 id[25] = tmp;
115 }
116 //for ( int i = 0 ; i < 26 ; i++) printf("id[%d]:%c\n",i,char(id[i]+'a'));
117
118 for ( int i = 0 ; i < 26 ; i++) power[id[i]] = 25-i;
119 LL ans = 0;
120 for ( int i = 1 ; i <= n ; i++)
121 {
122 int len = st[i].length();
123 for ( int j = 0 ; j < len ; j++)
124 {
125 int pos = len-j-1;
126 int v = st[i][j]-'a';
127 LL tmp = (base26[pos]*power[v])%mod;
128 // cout<<"tmp:"<<tmp<<endl;
129 ans = (ans + tmp)%mod;
130 }
131 }
132 printf("Case #%d: %lld\n",++cas,ans);
133
134 }
135
136
137 #ifndef ONLINE_JUDGE
138 fclose(stdin);
139 #endif
140 return 0;
141}