hdu-6034-Balala Power!

向右看齐 2022-06-11 00:59 72阅读 0赞

##  Balala Power! ##

时间限制: 4 Sec   内存限制: 128 MB

## 题目描述 ##

![C642-1002-1.jpg][]

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.

## 输入 ##

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)

## 输出 ##

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.

## 样例输入 ##

1
    a
    2
    aa
    bb
    3
    a
    ba
    abc

## 样例输出 ##

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

题意：给出 n个字符串，字符包括 a~z，分别给它们赋值 0~25，使得这些串表达成26进制时的和最大

官方题解：每个字符对答案的贡献都可以看作一个 26 进制的数字，问题相当于要给这些贡献加一个 0 到 25 的权重使得答案最大。最大的数                    匹配 25，次大的数匹配 24，依次类推。排序后这样依次贪心即可，唯一注意的是不能出现前导 0。

思路：用二维数组num\[ \] \[ \],记录每个字母在哪一位出现了多少次，即num\[字母\] \[出现的位数\]=字母在位数出现的次数，另外用sum\[ \]数组存储             字母的“贡献”，即sum\[字母\]=该字母的贡献，另外开一个数组ban\[ \],来处理前导零问题，各个字符串统计好之后，根据每个字母的贡献              对字母进行排序（用num数组而不用sum数组），按着贪心思想，给字母分配权重，得出答案；

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 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 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="width:100%; vertical-align:text-top; background-color:rgb(239,239,239)"> 
 <div style="margin:7px"> 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 typedef&nbsp; 
 long&nbsp; 
 long&nbsp;LL; 
 
 
 const&nbsp; 
 int&nbsp;N&nbsp;=&nbsp; 
 100020; 
 
 const&nbsp; 
 int&nbsp;Q&nbsp;=&nbsp;1e9&nbsp;+&nbsp; 
 7; 
 
 int&nbsp;n,&nbsp;L; 
 
 int&nbsp;num[ 
 26][N];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///num[字母][该字母在的位数]=字母在该位出现的次数 
 int&nbsp;power[N],&nbsp;sum[N];&nbsp;&nbsp;&nbsp;&nbsp; 
 ///sum[字母]=该字母目前的贡献，pow[位数]=该位的贡献（26^x）; 
 bool&nbsp;ban[ 
 26];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///处理前导零 
 
 char&nbsp;str[N]; 
 
 int&nbsp;a[ 
 26]; 
 
 
 ///根据在每位出现的次数进行排序，因为位数高的占的权重比较大， ///所以先从高位开始，按权重从小到大排序 
 bool&nbsp;cmp( 
 int&nbsp;A,&nbsp; 
 int&nbsp;B) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;i&nbsp;=&nbsp;L&nbsp;-&nbsp; 
 1&nbsp;;&nbsp;i&nbsp;&gt;=&nbsp; 
 0&nbsp;;&nbsp;--&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(num[A][i]&nbsp;!=&nbsp;num[B][i]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;num[A][i]&nbsp;&lt;&nbsp;num[B][i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 
 void&nbsp;work() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(num,&nbsp; 
 0,&nbsp; 
 sizeof(num)); 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(ban,&nbsp; 
 0,&nbsp; 
 sizeof(ban)); 
 &nbsp;&nbsp;&nbsp;&nbsp;memset(sum,&nbsp; 
 0,&nbsp; 
 sizeof(sum)); 
 &nbsp;&nbsp;&nbsp;&nbsp;L&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;i&nbsp;=&nbsp; 
 0&nbsp;;&nbsp;i&nbsp;&lt;&nbsp;n&nbsp;;&nbsp;++&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%s",&nbsp;str); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;len&nbsp;=&nbsp;strlen(str); 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(len&nbsp;&gt;&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ban[str[ 
 0]&nbsp;-&nbsp; 
 'a']&nbsp;=&nbsp; 
 1; 
 ///如果该字母在第一位，则ban[**]=1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;reverse(str,&nbsp;str&nbsp;+&nbsp;len); 
 ///倒置数组 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;j&nbsp;=&nbsp; 
 0&nbsp;;&nbsp;j&nbsp;&lt;&nbsp;len&nbsp;;&nbsp;++&nbsp;j) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;++&nbsp;num[str[j]&nbsp;-&nbsp; 
 'a'][j];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///该字母在j位出现的次数加一 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum[str[j]&nbsp;-&nbsp; 
 'a']&nbsp;+=&nbsp;power[j];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///该字母的贡献增加 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(sum[str[j]&nbsp;-&nbsp; 
 'a']&nbsp;&gt;=&nbsp;Q) 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum[str[j]&nbsp;-&nbsp; 
 'a']&nbsp;=&nbsp;&nbsp;sum[str[j]&nbsp;-&nbsp; 
 'a']%Q; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;L&nbsp;=&nbsp;max(L,&nbsp;len); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///对每个字母出现的次数进行进位处理，（以26进制） &nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;i&nbsp;=&nbsp; 
 0&nbsp;;&nbsp;i&nbsp;&lt;&nbsp; 
 26&nbsp;;&nbsp;++&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;j&nbsp;=&nbsp; 
 0&nbsp;;&nbsp;j&nbsp;&lt;&nbsp;L&nbsp;;&nbsp;++&nbsp;j) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[i][j&nbsp;+&nbsp; 
 1]&nbsp;+=&nbsp;num[i][j]&nbsp;/&nbsp; 
 26; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[i][j]&nbsp;%=&nbsp; 
 26; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while&nbsp;(num[i][L]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[i][L&nbsp;+&nbsp; 
 1]&nbsp;+=&nbsp;num[i][L]&nbsp;/&nbsp; 
 26; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[i][L&nbsp;++]&nbsp;%=&nbsp; 
 26; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a[i]&nbsp;=&nbsp;i; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///排序 &nbsp;&nbsp;&nbsp;&nbsp;sort(a,&nbsp;a&nbsp;+&nbsp; 
 26,&nbsp;cmp); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;zero&nbsp;=&nbsp;- 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;i&nbsp;=&nbsp; 
 0&nbsp;;&nbsp;i&nbsp;&lt;&nbsp; 
 26&nbsp;;&nbsp;++&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///找出贡献比较小，不在第一位的（可以为零），给它赋值为零，使最后结果最大 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(!ban[a[i]]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;zero&nbsp;=&nbsp;a[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 break; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;res&nbsp;=&nbsp; 
 0,&nbsp;x&nbsp;=&nbsp; 
 25; 
 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;i&nbsp;=&nbsp; 
 25&nbsp;;&nbsp;i&nbsp;&gt;=&nbsp; 
 0&nbsp;;&nbsp;--&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if&nbsp;(a[i]&nbsp;!=&nbsp;zero) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res&nbsp;+=&nbsp;(LL)(x&nbsp;--)&nbsp;*&nbsp;sum[a[i]]&nbsp;%&nbsp;Q; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res&nbsp;%=&nbsp;Q; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 static&nbsp; 
 int&nbsp;ca&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "Case&nbsp;#%d:&nbsp;%d\n",&nbsp;++&nbsp;ca,&nbsp;res); 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;power[ 
 0]&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for&nbsp;( 
 int&nbsp;i&nbsp;=&nbsp; 
 1&nbsp;;&nbsp;i&nbsp;&lt;&nbsp;N&nbsp;;&nbsp;++&nbsp;i) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;power[i]&nbsp;=&nbsp;(LL)power[i&nbsp;-&nbsp; 
 1]&nbsp;*&nbsp; 
 26&nbsp;%&nbsp;Q;&nbsp;&nbsp; 
 ///power[i]=26^i； &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while&nbsp;(~scanf( 
 "%d",&nbsp;&amp;n)) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;work(); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

[C642-1002-1.jpg]: /images/20220611/584edfca4e354664bd20e9bf80142096.png