本文主要是介绍2017多校联合一1002／hdu6034Balala Power!(搜索，贪心，排序，大数进制)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Balala Power!
题意：
n串字母，总长度不超过1e6，让你给出a-z到0-25的映射，使26进制的字符串对应的数字之和最大。
解题思路：
每个字母所在位置对应权值加和，肯定存不下。
但我们只需要26个字母对应值之间的关系即可，开一个数组a[i][j]分别记录字母i在j这个位置上出现了多少次，对于大于26的值进位，这样我们就得到了26个字母对应的值对应的系数，按照字典序比较的方式去排序即可。
但是要注意，题目虽然说一定有一个字母没有出现在最高位过，保证了一定存在合法的映射，（合法即不能出现前导零），但是排序后的序列可能将出现在最高位过的字母排到最后一位，赋值为0就非法了。所以这种情况需要特判，然后从后往前找第一个没出现在最高位的字母替换到最后，前面依次迁移。
官方题解：
每个字符对答案的贡献都可以看作一个 26 进制的数字，问题相当于要给这些贡献加一个 0 到 25 的权重使得答案最大。最大的数匹配 25，次大的数匹配 24，依次类推。排序后这样依次贪心即可，唯一注意的是不能出现前导 0。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#include <stdlib.h>
#define lowbit(x) (x&-x)
#define e exp(1.0)
//ios::sync_with_stdio(false);
typedef long long ll;
typedef long long LL;
using namespace std;
const int maxn=100005;
const int mod=1e9+7;
string str;
//char str[maxn];
int power[maxn];
int num[26][maxn];
int sum[26];
int a[26];
int n,maxl;
int cas=1;
bool vis[26];bool cmp(int a, int b)
{for (int i = maxl-1; i >= 0; i--)if (num[a][i] != num[b][i])return num[a][i] < num[b][i];return false;
}int main()
{power[0] = 1;for (int i=1;i<maxn;i++)power[i] = (long long)power[i-1] * 26 % mod;while (cin>>n){memset(num, 0, sizeof(num));memset(vis, false, sizeof(vis));memset(sum, 0, sizeof(sum));maxl = 0;for (int i = 0; i < n; i++){cin>>str;//scanf("%s", str);vis[str[0] - 'a'] = true;int len=str.length();//int len = strlen(str);int pos = 0,tmp;for (int j = len-1; j >=0 ; j--){tmp = str[j] - 'a';num[tmp][pos]++;sum[tmp] += power[pos++];sum[tmp]%=mod;}maxl=max(maxl,len);}for (int i = 0; i < 26; i++){for (int j = 0; j < maxl ; j++){num[i][j + 1] += num[i][j] / 26;num[i][j] %= 26;}while (num[i][maxl]){num[i][maxl + 1] += num[i][maxl] / 26;num[i][maxl++] %= 26;}a[i] = i;}sort(a, a + 26, cmp);int first = -1;//除去前导0.for (int i = 0; i < 26; i++){if (!vis[a[i]]){first = a[i];break;}}int ans = 0, x = 25;for (int i = 25; i >=0; i--){if(a[i]!=first){ans += (long long)(x--)*sum[a[i]] % mod;ans %= mod;}}cout<<"Case #"<<cas++<<": "<<ans<<endl;//printf("Case #%d: %d\n", cnt++, ans);}return 0;
}
这篇关于2017多校联合一1002／hdu6034Balala Power!(搜索，贪心，排序，大数进制)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
