Balala Power!

19415 단어 알고리즘다 교
제목: 소문 자로 구 성 된 문자열 n 개 를 드 리 겠 습 니 다. 26 개의 알파벳 에 0 - 25 를 할당 하 라 고 합 니 다. 각 문자열 은 26 진수 의 숫자 를 만 들 고 어떻게 나 누 느 냐 고 물 었 습 니 다.
배 권 치 는 이 n 개의 수의 합 이 가장 크다.(선도 0 은 안 되 지만 한 개 0 은 가능 합 니 다)
문제 풀이: 모든 문자 가 답 에 기여 하 는 것 은 26 진법 의 숫자 로 볼 수 있 습 니 다. 문 제 는 이러한 공헌 에 0 에서 25 의 가중치 를 더 해서 답 을 가장 크게 하 는 것 과 같 습 니 다.최대 수 는 25 와 일치 하고, 큰 수 는 24 와 일치 하 며, 순서대로 유추 합 니 다.정렬 후 이렇게 순서대로 욕심 을 부리 면 되 는데, 유일 하 게 주의 하 는 것 은 선도 0 이 나타 나 면 안 된다 는 것 이다.
#include
#include
#include
#include
typedef long long ll;
const int mod =1e9+7;
const int maxn =1e5+5;
using namespace std;

ll fac[maxn]= {1};   // 26   
int Hash[27];       //         
bool lead[27];      //     
char str[maxn];

struct node
{
    int cnt[maxn];//          
    int id; //   
    bool operator < (const node &a)const
    {
        for(int i=maxn-1; i>=0; i--) //       
        {
            if( cnt[i] >a.cnt[i] ) return 1;
            else if(cnt[i] < a.cnt[i]) return 0;
        }
    }
} a[27];
int main()
{
    //freopen("in.txt","r",stdin);
    for(int i=1; i<maxn; i++)
    {
        fac[i]=fac[i-1]*26%mod;
    }
    int n,ca=1;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        memset(Hash,-1,sizeof(Hash));
        memset(lead,0,sizeof(lead));
        for(int i=1; i<=n; i++)
        {
            scanf("%s",str);
            int len=strlen(str);
            if(len != 1)
                lead[str[0]-'a']=1;
            for(int i=0; i<len; i++)
            {
                a[str[i]-'a'].cnt[len-i-1]++;
            }
        }
        //    , 26        
        for(int i=0; i<26; i++)
        {
            for(int j=0; j<maxn; j++)
            {
                if(a[i].cnt[j] >=26)
                {
                    a[i].cnt[j+1] += a[i].cnt[j]/26;
                    a[i].cnt[j] %= 26;
                }
            }
            a[i].id=i;
        }
        sort(a,a+26);
        for(int i=0; i<26; i++) //       
        {
            Hash[a[i].id]= 26-i-1;
        }


        for(int j = 25; j >= 0; j--)
        {
            if(!lead[a[j].id])
            {
                for(int k = 25; k >= j+1; k--)
                    Hash[a[k].id] = Hash[a[k-1].id];
                Hash[a[j].id] = 0;
                break;
            }
        }


        ll ans=0;
        for(int i=0; i<26; i++)
        {
            for(int j=0; j<maxn; j++)
            {
                ans= (ans+ fac[j]*a[i].cnt[j]*Hash[a[i].id]%mod) %mod;
            }
        }
        printf("Case #%d: %lld
"
, ca++, ans); } }

좋은 웹페이지 즐겨찾기