2019-08-09 19:46 已编辑算法工程师

关注

[多校补题]2017 Multi-University Training Contest 1 solutions BY 北京航空航天大学

1001. Add More Zero

Add More Zero

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

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

Input

The input contains multiple test cases. Each test case in one line contains only one positive integer

Output

For each test case, output " Case #

Sample Input

   
    1
64

Sample Output

   
    Case #1: 0
Case #2: 19

题意就是10的m次方能转换成2的多少次方，直接求下对数变形一下，得k=m*lg2。

每次O(1)输出即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const double lg=0.30103;


int main(){
	int tt=1;
	int m;
	cout<<log(3)<<endl;
	while(~scanf("%d",&m)){
//			cout<<m*lg<<endl;
//		int res = m*lg;
//		printf("Case #%d: %d\n",tt++,res);
	}
	return 0;	
}

1002. Balala Power!

Balala Power!

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

Problem Description

</center>
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 #

Sample Input

    
     1
a
2
aa
bb
3
a
ba
abc

Sample Output

    
     Case #1: 25
Case #2: 1323
Case #3: 18221

每个字符对答案的贡献都可以看作一个 26 进制的数字，问题相当于要给这些贡献加一个 0 到 25 的权重使得答案最大。最大的数匹配 25，次大的数匹配 24，依次类推。排序后这样依次贪心即可，唯一注意的是不能出现前导 0。

因为题目里的数字很大，但是转化成26进制也就100000位，所以考虑用数组的方法储存这些书。先统计每个字母在各个位置上的贡献值，因为你每个位置上的贡献值可能是大于26的，所以要模拟进位。然后按照这个贡献值进行排序，因为题目保证有一个字母是没有出现过的，所以把这个未出现过的字母调到数组首，其余的元素按照贡献值递增排序，之后就按照数组顺序从0到25对他们赋值。这就完成了确定。然后接下来只需要按照每个字母的权值*这个字母在26^j位上的贡献*j位的权重累加即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
const  ll mod=1e9+7;
char s[120000];
int a[27][120000+5];	//第i个字母在第j个位置（26^j）的贡献 
int b[27];				//排序数组 对字母的贡献进行排序 
int c[27];				//权重数组 记录每个字母最终的贡献权重 
ll d[120000];			//每个位的数值的大小 26^d[i] 
int e[27];				//记录字母在字符串首是否出现 若未出现过则将其设为0 若都出现则找贡献值最小的那个作为0 

void init(){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c)); 
	memset(e,0,sizeof(e)); 
	memset(s,0,sizeof(s)); 
}

bool cmp(int x,int y){
	for(int i=110000;i>=0;i--){
		if(a[x][i]!=a[y][i])
			return a[x][i]<a[y][i];
	}
	return 0;
}

int main(){
	d[1]=1;
	for(int i=2;i<110000;i++)d[i]=(d[i-1]*26)%mod;
	int cnn=1;
	int n;
	while(~scanf("%d",&n)){
		init();
		for(int i=0;i<n;i++){
			scanf("%s",s);
			int len = strlen(s);
			for(int j=len-1;j>=0;j--){//统计各个元素在各个位置出现的次数 
				a[s[j]-'a'][len-j]++;
				if(j==0)e[s[j]-'a']=1;
			}
		}
		for(int i=0;i<26;i++){
			for(int j=1;j<=110000;j++){
				if(a[i][j]>=26){
					a[i][j+1]+=a[i][j]/26;
					a[i][j]%=26;
				}
			}
		} 
		for(int i=0;i<26;i++)b[i]=i;
		sort(b,b+26,cmp);
		if(e[b[0]]==1){
			int start =1;
			while(e[b[start]]==1&&start<26){
				start++;
			}
			int temp = b[start];
			for(int i=start-1;i>=0;i--){
				b[i+1]=b[i];
			}
			b[0]=temp;
		}
		for(int i=0;i<26;i++)c[b[i]]=i;
		long long ans=0;
		for(int i=0;i<=26;i++){
			for(int j=1;j<=110000;j++){
				ans=(ans+c[i]*a[i][j]*d[j])%mod;
			}
		} 
		printf("Case #%d: %lld\n",cnn++,ans);	
	}
	return 0;
	
}

1006. Function（待补）

Function

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

Problem Description

You are given a permutation

Input

The input contains multiple test cases.

For each case:

The first line contains two numbers

Output

For each test case, output " Case #

Sample Input

Sample Output

    
     Case #1: 4
Case #2: 4

考虑置换

<nobr style="border&#58;0px&#59; padding&#58;0px&#59; margin&#58;0px&#59; max&#45;width&#58;none&#59; max&#45;height&#58;none&#59; min&#45;width&#58;0px&#59; min&#45;height&#58;0px&#59; vertical&#45;align&#58;0px&#59; line&#45;height&#58;normal"> f (i) = b f (a i) = b b f (a a i) = b \dots b f (i)      l times b </nobr>

那么

而如果

答案就是

这道题不会做啊....理解不了题意...

已知f(i)=b[f(a(i)]，则
f(0) = b[f(a[0])] = b[f(2)]
f[1] = b[f(a[1])] = b[f(0)]
f[2] = b[f(a[2])] = b[f(1)]
其实这道题可以转化为求环的问题，有多少种方式可以构成题目要求的环，即b的环可以有多少种方式画成a的环。

1011. KazaQ's Socks

KazaQ's Socks

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

Problem Description

KazaQ wears socks everyday.

At the beginning, he has

Input

The input consists of multiple test cases. (about

Output

For each test case, output " Case #

Sample Input

Sample Output

   
    Case #1: 3
Case #2: 1
Case #3: 2

找规律若是前n天就直接1-n的穿从第n+1天开始以一个周期进行循环比如n=4 就是1 2 3 4 | 1 2 3 | 1 2 4 | 1 2 3 | 1 2 4 .....

所以有很明显的周期性，每个周期只会改变最后一个数字，在最大的两个数字中周期循环。

#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    long long n,k;
    int t = 1;
    while(scanf("%lld %lld",&n,&k)!=EOF)
    {    
        if(k <= n)
        {
            printf("Case #%d: %lld\n",t,k);
            t++;
        }
    
        else
        {
            long long temp = (k-n)% (n-1);
            long long shang = (k-n) / (n-1);
            
            if(temp == 0)
            {
                if(shang % 2 == 0)    
                    printf("Case #%d: %lld\n",t,n);
                else 
                    printf("Case #%d: %lld\n",t,n-1);
                t++;
            }
            
            else 
            {
                printf("Case #%d: %lld\n",t,temp);
                t++;
            }
        }
            
    } 
    
    return 0;
}

第一场官方题解： BestCoder官方博客