Balala Power!（26进制模拟）

Power!（26进制模拟）"/>

Balala Power!（26进制模拟）

原题：

题意：

给n个串，例如a、ba、abc（26进制），让abc对应0~25的一个数（两个字母不能映射到一个数），且当一个串长度大于1时，首字母不能为0，求一种映射方式使n个串的和最大

解析：

记录每个字母在所有位置出现的次数，然后模拟26进制，最大的那个附成25，依次下推。

要记录有哪些字母不能为0，当26个字母都出现的时候，一定会有一个需要附为0，那么就在可以为0的字母中选择一个最小的变成0

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
#define debug(i) printf("# %d\n",i)
int ct[26][100009];
char x[100009];
bool lead[26];
int ma[26];
LL val[26];struct node{int id;bool operator < (const node &r)const{if(ma[id]==0&&ma[r.id]==0)return ct[id][0]>ct[r.id][0];if(ma[id]!=ma[r.id]){return ma[id]>ma[r.id];}for(int i=ma[id];i>=0;i--){if(ct[id][i]!=ct[r.id][i]){return ct[id][i]>ct[r.id][i];}}return ct[id][0]>ct[r.id][0];}
}e[26];int main(){int n;int ca=0;while(cin>>n){memset(lead,0,sizeof(lead));memset(ma,0,sizeof(ma));memset(ct,0,sizeof(ct));printf("Case #%d: ",++ca);for(int i=1;i<=n;i++){scanf("%s",x);int len=strlen(x);for(int j=0;j<len;j++){ct[x[j]-'a'][len-1-j]++;ma[x[j]-'a']=max(ma[x[j]-'a'],len-1-j);}if(len>1)lead[x[0]-'a']=true;}for(int i=0;i<26;i++){for(int j=0;j<=ma[i];j++){if(ct[i][j]>=26){int up=ct[i][j]/26;ct[i][j]%=26;ct[i][j+1]+=up;ma[i]=max(ma[i],j+1);}}}for(int i=0;i<26;i++)e[i].id=i;sort(e,e+26);bool have26=1;for(int i=0;i<26;i++)if(ma[i]==1&&ct[i][0]==0)have26=0;if(have26){int co=0;for(int i=25;i>=0;i--){if(lead[e[i].id]){co++;val[e[i].id]=(LL)co;}else{val[e[i].id]=0;memset(lead,-1,sizeof(lead));}}}else{for(int i=0;i<26;i++){val[e[i].id]=25-i;}}LL ans=0;for(int i=0;i<26;i++){LL base=val[i];for(int j=0;j<=ma[i];j++){ans+=base*ct[i][j];ans%=mod;base*=26ll;base%=mod;}}printf("%lld\n",ans);}
}