首页 > > 程序设计 > C/C++ >

HDU 6034---Balala Power!（搜索+贪心）

2018-06-17 22:10:12来源：未知阅读 ()

题目链接

Problem Description

Talented Mr.Tang has

Input

The input contains multiple test cases.

For each test case, the first line contains one positive integers

Output

For each test case, output "Case #" in one line (without quotes), where

Sample Input

abc

Sample Output

Case #1: 25

Case #2: 1323

Case #3: 18221

题意：有n个小写字母组成的字符串，现在可以对'a'~'z'分别赋值，取0~25之间的一个数，但是每个数只能取一次，那么每个串就变成了一个26进制的数，现在求使这些数的和最大，输出这个最大的和，注意不能有前导零。

思路：对于每个字母先算出它的系数，对于‘ba’ 串，‘a’-->1,'b'-->26 。那么对于题中的数据‘a’-->1+1+26*26=678 ,'b'-->26+26=52 , 'c'-->1 所以对于这些串的和为sum=678a+52b+c,那么和明显对于系数大的字母赋较大的值，贪心的赋值即可。但是由于这个串很长10^5 那么26^100000 早就爆 long long 了，所以不能这样算出他们的系数，然后比较系数大小了。我们可以定义一个数组a[26][100005]，用来标示每个字母对应的几次方有多少个，当然对于值大于25的时候，向前进位，最后利用搜索从最高位向低位进行搜索，对于最高位时，值最大的说明该字符对应的系数肯定是最大的，如果有多个最大值，那么就需要第二高位，依次递推……

代码如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef  long long LL;
const int MAXN=1e5+15;
const LL MOD = 1e9+7;
char str[MAXN];
int k[30][MAXN];
int mp[30];
int ans[30];
int temp;
int check(int a[30])
{
    int num=0;
    for(int i=0;i<30;i++)
        num+=a[i];
    return num;
}
int pp()
{
    for(int i=0;i<30;i++)
        if(mp[i]==1) return i;
}

void dfs(int dep,int o[])
{
    if(dep<0) return ;
    int maxn=-1;
    int oo[30] , ct=0,pos=-1;
    memset(oo,0,sizeof(oo));
    for(int i=0;i<=25;i++)
    {
        if(maxn<k[i][dep]&&o[i]==1)
            maxn=k[i][dep];
    }
    for(int i=0;i<=25;i++)
    {
        if(maxn==k[i][dep]&&o[i]==1)
        {
            oo[i]=1;
            o[i]=0;
            ct++;
            pos=i;
        }
    }
    if(ct==0) return ;
    if(ct==1){
        if(check(mp)==1&&pos==pp()) ans[pos]=25;
        else ans[pos]=temp++;
        mp[pos]=0;
    }
    else if(dep==0){
        for(int i=0;i<26;i++)
        {
            if(maxn==k[i][dep]&&oo[i]==1)
            {
                if(check(mp)==1&&i==pp()) ans[i]=25;
                else ans[i]=temp++;
                mp[i]=0;
            }
        }
    }
    else  dfs(dep-1,oo);
    if(check(o)>0) dfs(dep,o);
}
LL Pow(LL a, LL b){
    LL ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % MOD;
        b>>=1;
        a = (a * a ) % MOD;
    }
    return ans;
}

int main()
{
    int T,n,L,l,cas=1;
    int one[30];
    while(scanf("%d",&n)!=-1)
    {
        L=0;
        for(int i=0;i<26;i++) one[i]=1,mp[i]=1;
        memset(k,0,sizeof(k));
        ///memset(ans,0,sizeof(ans));
        for(int i=0;i<n;i++)
        {
            scanf("%s",str);
            mp[str[0]-'a']=0;
            l=strlen(str);
            if(l>L) L=l;
            for(int j=0;j<l;j++)  k[str[j]-'a'][l-j-1]++;
        }
        for(int i=0;i<26;i++)
        {
            for(int j=0;j<L+10;j++)
            {
                k[i][j+1]+=k[i][j]/26;
                k[i][j]=k[i][j]%26;
            }
        }
        temp=0;
        dfs(L+10,one);
        ///for(int i=0;i<26;i++) cout<<ans[i]<<" "; cout<<endl;
        LL res=0;
        for(int i=0;i<26;i++)
        {
            for(int j=0;j<L+10;j++)
            {
                ///res+=(25-ans[i])*Pow(26,j)*k[i][j];
                res = (res+((25-ans[i])*Pow(26,j) % MOD)*k[i][j]%MOD)%MOD;
            }
        }
        printf("Case #%d: %lld\n",cas++,res);
    }
    return 0;
}