HDU 6043 Balala Power! 思维 + 码力

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6034

　　题目大意：有n个由小写字母组成的字符串，每种小写字母只能表示0~25的一个数字，且不能开头字母表示的数字不能为0，求字母表示的26进制数最大是多少，结果对1e9+7求余，保证有解

　　题目思路：首先我们要确定一个标准，这个标准就是每种字母的重要程度，只有这种字母足够重要我们才能够将它赋予更大的值，决定一种字母的重要程度有两个因素，一个是它的位数，一个是它出现的次数，我们要找到的标准就是这两个的综合，我们可以用一个二维数组来表示，第一维下标表示字母种类，每一整行表示它的重要性（26进制数），再对这个结构体数组排序就能知道每种字母的重要性了，然后挨个赋值，这里我用结构体数组的原因是二维数组不好排序，但是结构体数组排序记住写好拷贝构造函数，还有一个问题就是不能有前导零，解决方法就是ishead[i]维护字母i是不是开头字母，若是，将其自己++，向后移动到下一个不重要的字母，直到ishead[i] == 0 break掉。

　　代码：错误代码，在这里先存一下，今晚调试

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

typedef long long ll;
int isHead[30]; // 是否当做过开头
int vis[30]; // 出现过的字母
int n;
const int MAXN = 100000+5;
const int MOD = 1e9 + 7;
string a[MAXN];
int maxLen;
struct Node {
    int a[MAXN];
};
int value[30];

Node cnt[30]; // cnt[i].a[j]表示字母i在第j位出现的次数

int cmp( Node & n1, Node & n2 ) {
//    cout << "func" << endl;
    for( int i = maxLen - 1; i >= 0; i-- ) {
        if( n1.a[i] < n2.a[i] ) return 1;
        if( n1.a[i] > n2.a[i] ) return 0;
    }
    return 1;
}
int cases = 0;
int main() {
    while( cin >> n ) {
        memset(isHead, 0, sizeof(isHead));
        memset(a, 0, sizeof(a));
        memset(vis, 0, sizeof(vis));
        maxLen = 0;
        for( int i = 0; i < n; i++ ) {
            cin >> a[i];
            char temp = a[i][0];
            isHead[temp-'a'] = 1;
        }
        for( int i = 0; i < n; i++ ) {
            int len = (int)a[i].length();
            maxLen = maxLen > len ? maxLen : len;
            int temp = 0;
            for( int j = len-1; j >= 0; j-- ) {
                vis[a[i][j]-'a'] = 1;
                cnt[a[i][j]-'a'].a[temp]++;
                temp++;
            }
        }
//        for( int i = 0; i < 26; i++ ) {
//            for( int j = 0; j < maxLen; j++ ) {
//                cout << cnt[i].a[j] << " ";
//            }
//            cout << endl;
//        }
        for( int i = 0; i < 26; i++ ) {
            for( int j = 0; j < maxLen-1; j++ ) {
                if( cnt[i].a[j] >= 26 ) {
                    cnt[i].a[j+1] += cnt[i].a[j] / 26;
                    cnt[i].a[j] %= 26;
                }
            }
        }
        for( int i = 0; i < 26; i++ ) {
            cnt[i].a[maxLen] = i;
        }
        
        sort(cnt, cnt+26, cmp);
        
//        for( int i = 0; i < 26; i++ ) {
//            for( int j = 0; j <= maxLen; j++ ) {
//                cout << cnt[i].a[j] << " ";
//            }
//            cout << endl;
//        }
        int i;
        int temp = 25;
        memset(value, -1, sizeof(value));
        for( i = 25; i >= 0; i-- ) {
            if( !vis[cnt[i].a[maxLen]] ) break;
            value[cnt[i].a[maxLen]] = temp;
            temp--;
        }
        if( i == -1 ) { // 26个字母满了
            
            int j;
            for( j = 0; j < 26; j++ ) {
                if( !isHead[cnt[j].a[maxLen]] ) {
                    value[cnt[j].a[maxLen]] = 0;
                    break;
                }
                value[cnt[j].a[maxLen]]++;
            }
        }
//        for( int i = 0; i < 26; i++ ) {
//            cout << cnt[i].a[maxLen] << " " << value[cnt[i].a[maxLen]] << endl;
//        }
        ll ans = 0;
        int cc;
        for( int i = 0; i < n; i++ ) {
            int len = (int)a[i].length();
            cc = 1;
            for( int j = len-1; j >= 0; j-- ) {
                ans = ans + (value[a[i][j]-'a'] * cc) % MOD;
                cc = (cc * 26) % MOD;
            }
        }
        cout << "Case #" << ++cases << ": " << ans << endl;
    }
    return 0;
}

View Code

　　思考：自己的代码能力还是不够，思考问题还是不全面不细致。