CC

自然万物都趋向从有序变得无序

0%

Balala Power! HDU - 6034 贪心

发表于 更新于 分类于 Valine：

题目链接

题目

这里写图片描述

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 1e9+7.

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|≤1e6)

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
a
2
aa
bb
3
a
ba
abc

Sample Output

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

题意:

给你 n 个字符串,其中每个字符代表一个不同的数字 0 - 25, 要求你计算所有字符串的和,并且使得和最大.

思路:

算贡献, 我们用一个数组num[i][j] 表示字母 i 在位置 j 出现了多少次. 然后我们可以把num[i] 看成一个264进制的数,于是我们对它进行排序,然后贪心即可.

代码:

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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 1e5+300;
const int mod = 1e9+7;
int coe[30];
struct ss{
    string s;
    int id;
}a[30];
int num[30][maxn];
bool vis[30];

bool cmp(const ss &q, const ss &p){
return q.s > p.s;
}

int main(){
    int kase = 0;
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n){
        memset(coe,0,sizeof(coe));
        memset(vis,false,sizeof(vis));
        memset(num, 0,sizeof(num));
        int maxlen = 0;
        for(int i = 0; i < n ;++i){
            string s;
            cin>>s;
            int len = s.length();
            maxlen = max(maxlen, len);
            if(len > 1) vis[s[0] - 'a'] = true;//标记首元素
            for(int j = len - 1; j >= 0; --j)
                num[s[j]-'a'][len - j - 1]++;//统计字母出现的位置,
        }for(int i = 0; i < 30; ++i)
            for(int j = 0; j < maxlen + 20; ++j)
                if(num[i][j] >= 26){
                    num[i][j+1] += num[i][j] / 26;//进位
                    num[i][j] %= 26;
                }cout<<"Case #"<<++kase<<": ";
        for(int i = 0; i < 30; ++i){
            string ss = "";
            for(int  j = maxlen + 20; j >= 0; --j)
                ss += num[i][j] + 'a';
            a[i].s = ss;
            a[i].id = i;
        }sort(a,a+30,cmp);//将数字转换成字符串然后排序比较大小
        bool flag = true;
        int tmp = 1;
        for(int i = 25; i >= 0; --i){//从大到小一次赋值
            if(flag && !vis[a[i].id]){
                coe[a[i].id] = 0;
                flag = false;
            }else coe[a[i].id] = tmp++;
        }LL ans = 0, tt;
        for(int i = 0; i < 30; ++i){
            tt = 1;
            for(int j = 0;j < maxlen + 20; ++j){
                ans = (ans + (num[a[i].id][j] * coe[a[i].id]) * tt % mod) % mod;
            tt = tt * 26 %  mod;
            }
        }cout<<(ans % mod + mod ) % mod<<endl;
    }return  0;
}