您的位置: 首页  >  IT文章  >  2017 Multi-University Training Contest Add More Zero Balala Power!

2017 Multi-University Training Contest Add More Zero Balala Power!

分类: IT文章 • 2024-09-07 15:37:25

弱校也不打多校，自己也可以咸鱼嘛。水一水，玩一玩

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 643    Accepted Submission(s): 449


Problem Description
There is a youngster known for amateur propositions concerning several mathematical hard problems.

Nowadays, he is preparing a thought-provoking problem on a specific type of supercomputer which has ability to support calculations of integers between k that is suitable for the specific supercomputer.
 
Input
The input contains multiple test cases. Each test case in one line contains only one positive integer 5.
 
Output
For each test case, output "Case #y denotes the answer of corresponding case.
 
Sample Input
1 64
 
Sample Output
Case #1: 0 Case #2: 19
 
Source
2017 Multi-University Training Contest - Team 1
拿数学公式推一推就好了，O（1）的，就是n*log10(2)的下取整
#include <stdio.h>
#include <math.h>
int main() {
    int n,k=1;
    while(~scanf("%d",&n)){
        printf("Case #%d: %d
",k++,(int)(log10(2)*n));
    }
    return 0;
}

Balala Power!

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3268    Accepted Submission(s): 738


Problem Description
2017 Multi-University Training Contest Add More Zero Balala Power!

Talented Mr.Tang has 7.
 
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 #y denotes the answer of corresponding case.
 
Sample Input
1
a
2
aa
bb
3
a
ba
abc
 
Sample Output
Case #1: 25
Case #2: 1323
Case #3: 18221
这个图魔性了，强无敌，其实就是2进制的字符串，假如可以有前导零的话，算下贡献，贡献最大的数是25不就好了，但是不能有前导0的贪心就要后移，自己讨论下并不难，不过这个模拟也不短，等过些日子找个短的代码贴一下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 1e5+5;
ll fac[N]= {1};
int ma[27];
bool lead[27];
char str[N];
void init() {
    for(int i=1; i < N; i++)
        fac[i]=fac[i-1]*26%mod;
}
struct node {
    int cnt[N];
    int id;
    bool operator < (const node &a) const {
        for(int i = N-1; i >= 0; i--) {
            if(cnt[i] > a.cnt[i]) return 1;
            else if(cnt[i] < a.cnt[i]) return 0;
            else ;
        }
    }
} a[27];

int main() {
    int n, k = 1;
    init();
    while(~scanf("%d", &n)) {
        memset(a, 0, sizeof(a));
        memset(ma, -1, sizeof(ma));
        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]++;
        }
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < N; 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++)
            ma[a[i].id] = 26-i-1;
        for(int i = 0; i < 26; i++)
            if(lead[a[i].id] && ma[a[i].id] == 0) {
                for(int j = 25; j >= 0; j--) {
                    if(!lead[a[j].id]) {
                        for(int k = 25; k >= j+1; k--)
                            ma[a[k].id] = ma[a[k-1].id];
                        ma[a[j].id] = 0;
                        break;
                    }
                }
                break;
            }
        ll ans = 0;
        for(int i = 0; i < 26; i++) {
            for(int j = 0; j < N; j++) {
                ans = (ans+fac[j]*a[i].cnt[j]*ma[a[i].id]%mod)%mod;
            }
        }
        printf("Case #%d: %lld
", k++, ans);
    }
    return 0;
}

相关推荐