传送门：
多校第一场B题
题意：
把字符串每个字符对应0~25的数，进制是26进制，求最大贡献。最大的数匹配 25，次大的数匹配 24，依次类推。排序后这样依次贪心即可，唯一注意的是不能出现前导 0。
下面说下必要的几点处理：
1.前导0，如果排序出来最小贡献的那个数，且现在出现了1~25的赋值，选0的时候，这个字符如果出现在某个串的第一个，那么这个字符就不能赋值为0.
这时候要取到非首字母的第一个最小的数为0。
2.排序，如果直接num[][]，在这个题里面超时和超内存，这里可以把这个二维数组映射到一个a[26]，num[i][j]字符i位数为j的个数，a[]---贡献字符，sum[a[]]---当前贡献字符的贡献，a[26]为按照贡献排序的进制的26个字符的不同贡献。
3.进位的的处理，如果当前num[i][j]的个数超过26个,位数要进1,特判到达最高位，最长L要+1。
4.取模的处理。
#includeusing namespace std;typedef long long LL;const int N = 100020;const int Q = 1e9 + 7;int n , L;int num[26][N];//num[i][j]字符i位数为j的个数int power[N] , sum[N];//sum[i]为i字母的基数进制和，乘以本身值即结果bool ban[26]; char str[N]; int a[26]; //从小到大 bool cmp(int A , int B) { //从高位开始比，位数高的肯定大一些 for (int i = L - 1 ; i >= 0 ; -- i) { if (num[A][i] != num[B][i]) { return num[A][i] < num[B][i]; } } return 0; } void work() { memset(num , 0 , sizeof(num)); memset(ban , 0 , sizeof(ban)); memset(sum , 0 , sizeof(sum)); L = 0; for (int i = 0 ; i < n ; ++ i) { scanf("%s" , str); int len = strlen(str); //字符串长度等于1的时候随便了 if (len > 1) { //标记这个字符，这个串的第一个字符不能为0 ban[str[0] - 'a'] = 1; } //abc，第一个遍历的a，倒过来就是cba,a下标2，便于加上对应的基数 reverse(str , str + len); for (int j = 0 ; j < len ; ++ j) { ++ num[str[j] - 'a'][j]; sum[str[j] - 'a'] += power[j]; if (sum[str[j] - 'a'] >= Q) { sum[str[j] - 'a'] -= Q; } } L = max(L , len); } //进位 for (int i = 0 ; i < 26 ; ++ i) { for (int j = 0 ; j < L ; ++ j) { num[i][j + 1] += num[i][j] / 26; num[i][j] %= 26; } while (num[i][L]) { num[i][L + 1] += num[i][L] / 26; num[i][L ++] %= 26; } a[i] = i; } sort(a , a + 26 , cmp); int zero = -1; for (int i = 0 ; i < 26 ; ++ i) { //不能非0的最后一个字符赋值为0 if (!ban[a[i]]) { zero = a[i]; break; } } int res = 0 , x = 25; //x是从最大开始为字母赋值 for (int i = 25 ; i >= 0 ; -- i) { if (a[i] != zero) { res += (LL)(x --) * sum[a[i]] % Q; res %= Q; } } static int ca = 0; printf("Case #%d: %d\n" , ++ ca , res); } int main() { // freopen("in.txt","r",stdin); power[0] = 1; for (int i = 1 ; i < N ; ++ i) { power[i] = (LL)power[i - 1] * 26 % Q; } while (~scanf("%d" , &n)) { work(); } return 0; }
我们队改进后的写法：
#includeusing namespace std;typedef long long ll;const int maxn = 1e5 + 5;const ll Mod = 1e9 + 7;int len,ltt[26][maxn];char s[maxn]; bool apr[26]; ll pow26[maxn]; void init() { int len = strlen(s); for(int i = 0; i < len; i++) ltt[s[i]-'a'][len - 1 - i]++; } bool cmp(int A, int B) { for (int i = len - 1 ; i >= 0 ; -- i) { if (ltt[A][i] != ltt[B][i]) return ltt[A][i] < ltt[B][i]; } return 0; } int main() { // freopen("in.txt","r",stdin); int n; int kase = 1; pow26[0] = 1; for(int i = 1; i < maxn; i++) pow26[i] = pow26[i-1]*26%Mod; while(~scanf("%d", &n)) { memset(apr, 0, sizeof(apr)); memset(ltt, 0, sizeof(ltt)); len = 0; for(int i = 0; i < n; i++) { scanf("%s",s); int len1 = strlen(s); if(len1 > 1) apr[s[0] - 'a'] = 1; len = max(len,len1); init(); } int a[26]; //a数组是ltt数组的映射 //进位 for(int i = 0; i < 26; i++) { for(int j = 0; j < len; j++) { ltt[i][j+1] += ltt[i][j]/26; ltt[i][j] %= 26; } while(ltt[i][len]) { ltt[i][len+1] += ltt[i][len]/26; ltt[i][len++] %= 26; } a[i] = i; } sort(a, a + 26, cmp); int num[26] = {0}; if(len > 1) { bool flag = 1; int v = 1; for(int i = 0; i < 26; i++) { if(flag && !apr[a[i]]) { num[i] = 0; flag = 0; } else num[i] = v++; } } else { for(int i = 0; i < 26; i++) num[i] = i; } ll res = 0; for(int i = 0; i < 26; i++) for(int j = 0; j < len; j++) res = (res + num[i]*ltt[a[i]][j]*pow26[j])%Mod; printf("Case #%d: %I64d\n", kase++, res); } return 0; }