2017多校第一场补题

落下的题目慢慢补~~

HDU：6033~6044

Add More Zero

题意：计算2^m-1有多少位。

思路：log10(2^m) = m*log10(2)即可。

# include <iostream>
# include <cstdio>
# include <cmath>
using namespace std;
int main()
{
    int m,cas=0;
    while(~scanf("%d",&m))
        printf("Case #%d: %d\n",++cas,(int)(m*log10(2)));
    return 0;
}

Balala Power!

题意：给N个小写字母字符串，给每个字母分配一个值0~25，两个字母的值不可冲突，然后对N个串的26进制值求和，问最大是多少？

思路：将26个字母拆开成独立的数，从大到小排一排序，按照贪心显然将25~0降序分配给这些数。由于不能有前导零，当26个字母全出现过时，若排在最后那个字母充当了前导，就需要提到前面去。

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 1e5+30;
char s[maxn];
struct node
{
    int len;
    int bit[maxn];
}a[26];
int id[26];
bool head[26];
bool cmp(int x, int y)
{
    if(a[x].len != a[y].len) return a[x].len > a[y].len;
    for(int i=a[x].len; ~i; --i)
        if(a[x].bit[i] != a[y].bit[i]) return a[x].bit[i] > a[y].bit[i];
    return 0;
}
int main()
{
    int n,cas=0;
    while(~scanf("%d",&n))
    {
        LL ans = 0;
        for(int i=0; i<26; ++i)
        {
            head[i] = false;
            id[i] = i;
            a[i].len = -1;
            memset(a[i].bit, 0, sizeof(a[i].bit));
        }
        int p = 0;
        while(n--)
        {
            scanf("%s",s);
            int len=strlen(s), cnt=0;
            if(len > 1) head[s[0]-'a'] = true;
            for(int i=len-1; ~i; --i,++cnt)
            {
                ++a[s[i]-'a'].bit[cnt];
                a[s[i]-'a'].len = max(a[s[i]-'a'].len, cnt);
            }
        }
        for(int i=0; i<26; ++i)
        {
            if(a[i].len == -1) continue;
            for(int j=0;j<=a[i].len; ++j)
            {
                if(a[i].bit[j] >= 26)
                {
                    a[i].bit[j+1] += a[i].bit[j]/26;
                    a[i].bit[j] %= 26;
                    a[i].len = max(a[i].len, j+1);
                }
            }
        }
        sort(id, id+26,cmp);
        if(a[id[25]].len != -1 && head[id[25]])
        {
            for(int i=25; ~i; --i)
            {
                if(!head[id[i]])
                {
                    for(int j=i;j<25; ++j)
                        swap(id[j], id[j+1]);
                    break;
                }
            }
        }
        for(int i=0,b=25; i<26; ++i,--b)
        {
            int j = id[i];
            if(a[j].len == -1) break;
            LL t = 1LL;
            for(int k=0; k<=a[j].len; ++k,t=t*26%mod)
                ans = (ans + a[j].bit[k]*t%mod*b%mod)%mod;
        }
        printf("Case #%d: %lld\n",++cas,ans);
    }
    return 0;
}