【2017多校】第一场B题：Balala Power!

时间：2021-07-09 00:18:24

题目：

Balala Power!

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: >131072/131072 K (Java/Others)
Total Submission(s): 4809 Accepted Submission(s): 387

Problem Description

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 >anged 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.

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

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

思路及心路历程：

一开始并没有读懂题目，sjy说了一句26进制。然后壮壮拿笔刷刷刷写了几个数，加起来正好是样例的输出。

读懂题目之后开始思考算法。我和壮壮的第一个想法是，把最长的那一串的首字母赋最大值，即25，这样最大化利用位权。但我马上想到一种情况，次高位有27个没有在最高位出现过的字母，这样则用数量抵消了位权。或者次次高位有 2726 个一样没在次高位出现的字母。最多有十万位，不可能这样一直找下去。首先会超范围，再就是会浪费时间。

想到这种情况之后，我们假设一位位找下去，确定了一个字母的最优方案，但是却没有考虑到其他字母的最优方案。即只考虑了局部最优解，而没有顾及整体的利益。

就在我们一筹莫展的时候，超超提出，对于一个字母，可以从最低位开始，每出现26次即向高位进位，这样即可获得在既考虑到每个字母出现次数，又考虑到位权的情况下，获得每个字母的“特征值”。

之后这道题由壮壮开始码。首先用一个 26×100000 的数组，存下每个字母在每一位出现了多少次。然后进行进位计算，得到类似如下所示的一张表。

字母 万 千 百 十 个
f 0 1 2 2 0
a 1 2 14 3 0
b 1 5 7 15 11
⋯ ⋯ ⋯ ⋯ ⋯ ⋯

然后对这张表进行排序。因为实现是用的二维数组，每个字母对应一行，所以无法用STL里自带的sort函数进行排序，只好自己手写。用的是冒泡排序，从最高位的权值开始比较，若当前位权值相同，则往下一位找。

可以用 swap() 函数交换两行。

提前打好位权的表，数据类型要用 longlong ，同时要遵照题意取模。

这时考虑前导零的情况，题意保证，必有至少一个字符不是其他任意字符串的前缀。这就保证了，最坏情况下， 0值也是可以被赋出去的。

对每一个输入进来的字符串进行遍历，若从第二个字母开始，所有的字母都和头字母相同，则这个字母是可以被赋0的。

但还要小心先出现 aab ，后出现 aaa 的情况，不要让后面这种情况把原先记录的a不能被赋0给顶替掉。

期间七七八八改了8、9次，最后五分钟我从头检查了一遍，改了一个小细节，然后A掉了。所以就算到最后也不要放弃，从头再把代码看一遍，也许会有收获。

代码

/***********************
author : Meng Xiangcong
***********************/
//#include <bits/stdc++.h>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <climits>
#include <ctype.h>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

#define PI acos(-1)
#define INF (1<<30)
#define EPS 1e-6
#define SETDATA memset(data, 0, sizeof(data))
#define SET(a, b) memset(a, b, sizeof(a))
typedef long long LL;

const int mod = 1e9 + 7;
int x[26][100000 + 5];

int main()
{
long long poww[100000 + 5] = {1, 0};
for(int i = 1; i <= 100000; ++i)
    {
        poww[i] = 26 * poww[i - 1];
        poww[i] %= mod;
    }

int n;
char str[100000 + 5];
int maxlen, len;
long long sum;
int xi[26];
int xx = 1;
int xxx[26];
while(~scanf("%d", &n))
    {
        maxlen = 0;
        sum = 0;
memset(x, 0, sizeof(x));
memset(xi, 0, sizeof(xi));
memset(xxx, 0, sizeof(xxx));
for(int i = 0; i < 26; ++i)
        {
            x[i][100002] = i;
        }
while(n--)
        {
int flagg = 0;
scanf("%s", str);
            len = strlen(str);
if(len > maxlen) maxlen = len;
if(len > 1)
            {
for(int i = 0; i < len - 1; ++i)
                {
if(str[i] != str[i + 1])
                    {
                        flagg = 1;
break;
                    }
                }
            }

if(flagg) xi[str[0]-'a'] = 1;// no

int i,j;
for(i = len - 1, j = 0; i >= 0; --i, ++j)
            {
                ++x[str[i] - 'a'][j];
            }
        }
for(int i = 0; i < 26; ++i)
        {
for(int j = 0; j <= maxlen; ++j)
            {
                x[i][j + 1] += x[i][j] / 26;
                x[i][j] %= 26;
            }
        }
for(int ii = 0; ii < 25; ++ii)
        {
for(int j = 0, k = maxlen + 1; j < 25; ++j, k = maxlen)
            {
while(x[j][k] == x[j + 1][k] && k != 0)
                {
                    --k;
                }
if(x[j][k] < x[j + 1][k])
                {
                    swap(x[j], x[j + 1]);
                }
            }
        }
for(int i = 25; i >= 0;)
        {
if(xi[x[i][100002]])
            {
                --i;
            }
else
            {
for(int j = i; j < 25; ++j)
                {
                    swap(x[j], x[j + 1]);
                }
break;
            }
        }
for(int i = 0; i < 26; ++i)
        {
for(int j = 0; j <= maxlen + 1; ++j)
            {
                sum += (poww[j] * x[i][j] % mod * (25 -  i) % mod);
                sum %= mod;
            }
        }
printf("Case #%d: %lld\n", xx, sum);
        ++xx;
    }
return 0;
}
标签：

相关文章