hdu 6034 2017 Multi-University Training Contest - Team 1 B Balala Power! (贪心)
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 优
/* ***********************************************
Author :111qqz
Created Time :2017年11月01日 星期三 00时56分26秒
File Name :6034.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7const LL mod =1E9+7;
8int n;
9string st[N];
10int cnt[26][N];
11int maxlen;
12int id[26];
13int power[26];
14LL base26[N];
15bool Beg[26];
16void init()
17{
18 ms(Beg,false);
19 ms(cnt,0);
20 maxlen = 0 ;
21 for ( int i = 0 ; i < 26 ; i++) id[i] = i;
22}
23bool small(int *a,int *b)
24{
25 for ( int i = maxlen-1 ; i >= 0 ; i--)
26 {
27 if (a[i]<b[i]) return true;
28 if (a[i]>b[i]) return false;
29 }
30 return false;
31}
32int main()
33{
34 #ifndef ONLINE_JUDGE
35 freopen("./in.txt","r",stdin);
36 #endif
37 int cas = 0 ;
38 base26[0] = 1;
39 for ( int i = 1 ; i < N ; i++) base26[i] = base26[i-1] * 26 % mod;
40 while (~scanf("%d",&n))
41 {
42 init();
43 for ( int i = 1 ; i <= n ; i++)
44 {
45 cin>>st[i];
46 int len = st[i].length();
47 // cout<<"len:"<<len<<endl;
48 maxlen = max(len,maxlen);
49 for ( int j = 0 ; j < len ; j++)
50 {
51 int v = st[i][j]-'a';
52 cnt[v][len-j-1]++;
53 }
54 //如果只有一个字母，不要打首字母标记
55 if (len>1)
56 Beg[st[i][0]-'a'] = true;
57 //忘了不能右前导0的条件了。。。
58 }
59 for ( int i = 0 ; i < 26 ; i++)
60 {
61 for ( int j = 0 ; j < maxlen ; j++)
62 {
63 cnt[i][j+1] += cnt[i][j]/26;
64 cnt[i][j]%=26;
65 }
66 while (cnt[i][maxlen]>0)
67 {
68 cnt[i][maxlen+1] += cnt[i][maxlen]/26;
69 cnt[i][maxlen]%=26;
70 maxlen++;
71 }
72 }
1 for ( int i = 0 ; i < 26 ; i++)
2 for ( int j = i+1 ; j < 26 ; j++)
3 if (small(cnt[id[i]],cnt[id[j]]))
4 swap(id[i],id[j]);
5// for (int i = 0 ; i < 26 ; i++) printf("id[%d]:%c%c",i,char(id[i]+'a'),i==25?'\n':'\n');
1 int notBEG = -1;
2 if (Beg[id[25]])
3 {
4 for ( int i = 24 ; i >= 0 ; i--)
5 {
6 if (!Beg[id[i]])
7 {
8 notBEG = i;
9 break;
10 }
11 }
12 }
13 //cout<<"notBEG:"<<notBEG<<endl;
14 if (notBEG!=-1)
15 {
16 int tmp = id[notBEG];
17 for ( int i = notBEG +1 ; i < 26 ; i++) id[i-1] = id[i];
18 id[25] = tmp;
19 }
20 //for ( int i = 0 ; i < 26 ; i++) printf("id[%d]:%c\n",i,char(id[i]+'a'));
1 for ( int i = 0 ; i < 26 ; i++) power[id[i]] = 25-i;
2 LL ans = 0;
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 int len = st[i].length();
6 for ( int j = 0 ; j < len ; j++)
7 {
8 int pos = len-j-1;
9 int v = st[i][j]-'a';
10 LL tmp = (base26[pos]*power[v])%mod;
11 // cout<<"tmp:"<<tmp<<endl;
12 ans = (ans + tmp)%mod;
13 }
14 }
15 printf("Case #%d: %lld\n",++cas,ans);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}