Balala Power!
time limit per test 2 second memory limit per test 256 megabytes
Talented Mr.Tang has n strings consisting of only lower case characters. He wants to charge them with Balala Power (he could change each character ranged from a to z into each number ranged from 0 to 25, but each two different characters should not be changed into the same number) so that he could calculate the sum of these strings as integers in base 26 hilariously.

Mr.Tang wants you to maximize the summation. Notice that no string in this problem could have leading zeros except for string “0”. It is guaranteed that at least one character does not appear at the beginning of any string.

The summation may be quite large, so you should output it in modulo 109+7.

传送门:HDU6034

Input

The input contains multiple test cases.

For each test case, the first line contains one positive integers n, the number of strings. (1≤n≤100000)

Each of the next n lines contains a string si consisting of only lower case letters. (1≤|si|≤100000,∑|si|≤106)

Output

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

Sample Input

1
2
3
4
5
6
7
8
9
1
a
2
aa
bb
3
a
ba
abc

Sample Output

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

题解

贪心策略: 记录每个字母在每一位出现的次数 (不要忘记进位) 然后从高位比较,将26个字母排个序 按字母的位权高低从大到小赋值 前置0的情况只有26个字母都出现的情况才会出现 那么找可以作为首位的字母且位权最小的赋值为零 比赛时以为要开26×(1e6+100) 写了个邻接表 多开100是为了防止进位进上去 其实只要26×(1e5+100)
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
//数组法
import java.io.*;
import java.util.*;
public class Main {
static long mod=(long) (1e9+7);
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int count=0;
while(sc.hasNext()){
int n=sc.nextInt();
count++;
String[]node=new String[n];
int[]bj=new int[26];
A[]alpha=new A[26];
HashSet<Character>set=new HashSet<Character>();
for(int i=0;i<26;i++)alpha[i]=new A(i);
boolean[]z=new boolean[26];
int shu=25;
Arrays.fill(bj, -1);
Arrays.fill(z, true);
pw.print("Case #"+count+": ");
for(int i=0;i<n;i++){
String s=sc.next();
node[i]=s;
for(int j=0;j<s.length();j++){
alpha[s.charAt(j)-'a'].ws[s.length()-j]+=1;
if(alpha[s.charAt(j)-'a'].ws[s.length()-j]>=26){
alpha[s.charAt(j)-'a'].ws[s.length()-j]=0;
alpha[s.charAt(j)-'a'].ws[s.length()-j+1]+=1;
}
set.add(s.charAt(j));
}
if(s.length()>1){
z[s.charAt(0)-'a']=false;
}
}
Arrays.sort(alpha);
if(set.size()==26){
for(int i=25;i>=0;i--){
if(z[alpha[i].index]){
bj[alpha[i].index]=0;
break;
}
}
for(int i=0;i<26;i++){
if(bj[alpha[i].index]!=0)
bj[alpha[i].index]=shu--;
}
}else{
for(int i=0;i<26;i++){
bj[alpha[i].index]=shu--;
}
}
long sum=0;
for(int i=0;i<n;i++){
long t=0;
for(int j=0;j<node[i].length();j++){
t=(t*26+bj[node[i].charAt(j)-'a'])%mod;
}
sum=(sum+t)%mod;
}
pw.println(sum);
pw.flush();
}

}
}
class A implements Comparable<A>{
long []ws=new long[(int) (1e5+100)];
int index;
A(int i){
index=i;
}
@Override
public int compareTo(A o) {
for(int i=100099;i>=0;i--){
if(this.ws[i]>o.ws[i])return -1;
else if(this.ws[i]<o.ws[i])return 1;
}
return 0;
}
}

//写得比较烦的邻接表法
import java.io.*;
import java.util.*;
public class Main {
static long mod=(long) (1e9+7);
public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int count=0;
A[]alpha=new A[26];
while(sc.hasNext()){
int n=sc.nextInt();
count++;
String[]node=new String[n];
int[]bj=new int[26];
HashSet<Character>set=new HashSet<Character>();
for(int i=0;i<26;i++)alpha[i]=new A(i);
boolean[]z=new boolean[26];
Arrays.fill(z, true);
int shu=25;
Arrays.fill(bj, -1);
pw.print("Case #"+count+": ");
for(int i=0;i<n;i++){
String s=sc.next();
node[i]=s;
for(int j=0;j<s.length();j++){
if(!alpha[s.charAt(j)-'a'].map.containsKey(s.length()-j)){
alpha[s.charAt(j)-'a'].map.put(s.length()-j, 1);
}else{
if(alpha[s.charAt(j)-'a'].map.get(s.length()-j)==25){ //进位
if(!alpha[s.charAt(j)-'a'].map.containsKey(s.length()-j+1))
alpha[s.charAt(j)-'a'].map.put(s.length()-j+1, 1);
else{
alpha[s.charAt(j)-'a'].map.put(s.length()-j+1,alpha[s.charAt(j)-'a'].map.get(s.length()-j+1)+1);
}
alpha[s.charAt(j)-'a'].map.remove(s.length()-j);
}else
alpha[s.charAt(j)-'a'].map.put(s.length()-j, alpha[s.charAt(j)-'a'].map.get(s.length()-j)+1);
}
set.add(s.charAt(j));
}
if(s.length()>1){
z[s.charAt(0)-'a']=false;
}
}
Arrays.sort(alpha);
if(set.size()==26){
for(int i=25;i>=0;i--){
if(z[alpha[i].index]){
bj[alpha[i].index]=0;
break;
}
}
for(int i=0;i<26;i++){
if(bj[alpha[i].index]!=0)
bj[alpha[i].index]=shu--;
}
}else{
for(int i=0;i<26;i++){
bj[alpha[i].index]=shu--;
}
}
long sum=0;
for(int i=0;i<n;i++){
long t=0;
for(int j=0;j<node[i].length();j++){
t=(t*26+bj[node[i].charAt(j)-'a'])%mod;
}
sum=(sum+t)%mod;
}
pw.println(sum%mod);
pw.flush();
}

}
}
class A implements Comparable<A>{
TreeMap<Integer,Integer> map;
int index;
A(int i){
map=new TreeMap<Integer,Integer>();
index=i;
}
@Override
public int compareTo(A o) {
ArrayList<B>list1=new ArrayList<B>();
ArrayList<B>list2=new ArrayList<B>();
for(int i:this.map.keySet()){
list1.add(new B(i,this.map.get(i)));
}
for(int i:o.map.keySet()){
list2.add(new B(i,o.map.get(i)));
}
Collections.sort(list1);
Collections.sort(list2);
int i=0;
int j=0;
while(i<list1.size()&&j<list2.size()){
if(list1.get(i).index>list2.get(j).index)return -1;
if(list1.get(i).index<list2.get(j).index)return 1;
if(list1.get(i).shu>list2.get(j).shu)return -1;
if(list1.get(i).shu<list2.get(j).shu)return 1;
i++;
j++;
}
return 0;
}
}
class B implements Comparable<B>{
int index;
int shu;
B(int a,int b){
index=a;
shu=b;
}
public int compareTo(B o) {
if(this.index>o.index)return -1;
if(this.index<o.index)return 1;
return 0;
}

}