算法

首届哈尔滨理工大学"歌尔创客杯"新生赛(上)

朋友叫我打的,打完来写一下题解吧,题目质量方面,虽然大部分都不是原创题,但作为新生赛还算可以吧,推荐学完基础算法的可以来尝试一下。

传送门

A会长的烦心事

题目描述

最近ACM协会的同学总是利用休息的时间来玩LOL,而且一不小心就玩过头,就耽误了培训时间,这让会长很头疼。玩LOL的同学都知道LOL的全英文名是League of Legends,那么问题来了,如果给你这个单词leagueofl,也就是league这个单词加of这个单词加字母l,然后给你一个全部由小写英文字母组成的字符串,希望这个串中含leagueofl这个单词尽量多。例如串是eagueofaaalltyleagueofl,那么我们可以整理成leagueoflleagueoflaaaty,那么这个串中最多含有两个这个单词。

输入描述:

包含多组数据,输入一串字符串全部有小写英文字母组成。(长度不超过100)

输出描述:

这个串中所包含的最多leagueofl的个数。

输入

eagueofaaalltyleagueofl

输出

2

稍微观察就可以发现这个字符串 leagueofl 这个字符串只有首尾一致并且只有首尾能重合,所以直接统计每个字母的个数,然后注意 3个l能组成2个字符串,但是要2个l才有1个字符串,对l进行特殊处理即可。

#include<bits/stdc++.h>
using namespace std;
int len,a[200],ans;
char str[200];
int main(){
    while(scanf("%s",str+1)!=EOF){
        len=strlen(str+1);
        memset(a,0,sizeof(a));
        for(int i=1;i<=len;++i){
            a[str[i]]++;
        }//ASCII码自查
        ans=min(a[108]-1,min(a[101]/2,min(a[103],min(a[97],min(a[117],min(a[111],a[102]))))));
        printf("%d\n",max(ans,0));
    }
    return 0;
}

B快来秒掉我!

题目描述

不同的游戏有着不同的开始提示,像Are you really?Go!或者Can you start?。再一些大型的比赛中也有一些提示语,像Wa,Ac.等等。所以现在要求你输出一句提示语:Do you want to play ACM?(yes\no)

输入描述:

输出描述:

在一行中输出这一句话,所有符号均为英文符号。一定要仔细

输入

输出

Do you want to play ACM?(yes\no)

说句实话 ,这道题可能是我觉得整场比赛最难的了。。。没有了解这个方面的知识就完全做不出,整道题考的就是 \ 的输出,看代码吧,原理我不是很明白。

#include<bits/stdc++.h>
using namespace std;
int main(){
	printf("Do you want to play ACM?(yes\\no)");//注意是两个\符号
	return 0;
} 

C素数圆环

题目描述

322447 1576403716919 F3CCDD27D2000E3F9255A7E3E2C48800

如图所示为一个由n个圆圈构成的圆环。将自然数1,2,…,n放入圆圈内,并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数,你能给出放置自然数的所有正确方案吗? 注意:圆圈中的数字一定是从1开始的,并且连续不重复。

输入描述:

输入包含多组测试数据。每组输入占一行,为整数n(0<n<20),表示圆圈数。

输出描述:

对于每组输入,输出所有正确的方案,按字典序从小到大排序。每组输出后输出一个空行。具体输出格式见输出样例。

示例1

输入

6
8

输出

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

备注:

注意:只能按照顺时针方向放置数字。

话说我好像之前在别的OJ看到过这道题目,一道简单的搜索题,对于质数可以用质数筛先筛出来,也可以一个一个判断,毕竟这个数比较小,然后直接上搜索即可。

#include<bits/stdc++.h>
using namespace std;
int n,add,cnt,k;
bool book[50],used[50];//book 表示这个数是不是质数,uesd表示是否被使用过
int a[50],b[50];
void prime(int num){//质数筛
	book[1]=1;
	for(int i=2;i<=num;++i){
		if(!book[i]){
			a[++cnt]=i;
		}
		for(int j=1;j<=cnt&&a[j]*i<=num;++j){
			book[a[j]*i]=true;
			if(i%a[j]==0) break;
		}
	}
	return;
}
void dfs(int m,int last){//搜索 m代表当前填第m个空,last表示上个空填的是什么
	if(m>n){
		if(book[last+1]) return;
		for(int i=1;i<n;++i){
			printf("%d ",b[i]);
		}printf("%d\n",b[n]);
		return;
	} 
	for(int i=2;i<=n;++i){
		if(!book[last+i]&&!used[i]){
			used[i]=1;
			b[m]=i;
			dfs(m+1,i);
			b[m]=0;
			used[i]=0;
		} 
	}
}
int main(){
	prime(50);
	while(scanf("%d",&n)!=EOF){
		add++;
		memset(used,0,sizeof(used));
		printf("Case %d:\n",add);
		used[1]=1;b[1]=1;dfs(2,1);
		printf("\n");
	}
	return 0;
} 

D电脑磨损程度

题目描述

我们每次使用电脑都是会操成一些电脑磨损的,根据ACM协会研究表明,计算机开机后并连续工作4个小时以内会磨损10个单位的磨损(提示:0-4);接下来的4个小时(提示:4-8),每小时会造成2个单位的磨损;之后每小时会造成2.4个单位的磨损(提示:8-正无穷)。电脑最后使用时间既使不到1小时,也当作1小时计算磨损程度。(可以通过重启来结束连续工作,连续工作时间将清零)
一个参赛者可以根据计算机使用总时长合理安排时间,来让电脑的磨损程度降到最低。
例如,整个使用时间为16小时,使用者应该将使用时间分成长度相同的两部分,即在连续使用八小时时进行重启,每部分磨损18个单位,总共磨损了36个单位。如果电脑一直使用,则耗费37.2个单位。。
现在给你整个电脑的使用时间,请你计算使用电脑的最小磨损程度。

输入描述:

输入包含多组测试数据。每组输入一个正整数n(n<10000000),表示整个电脑使用时间。

当n=0时,输入结束。

输出描述:

对于每组输入,输出最小花费。如果需要的话,保留一位小数。

输入

3
9
16
0

输出

10
20.4
36

这道题目在学军OJ上有一道类似的题目,思路都是一样的,这题的思考量对于入门来说还是有的,通过简单的数学运算,我们就可以发现,小于4小时我们的答案直接就是10,小于8小时但是大于4小时我们就可以按照题目所给的公式计算 10+(n-4)*2 求得答案

这道题目的重点思路在于对于大于8小时的我们该怎么处理,首先可以稍加计算,如果是9小时,我们显然是在8小时的基础上继续使用,但是16小时的时候为什么就不能继续使用呢?我们可以发现如果8小时8小时的使用,平均每小时的损耗是18/8=2.25,如果我们继续使用每小时是2.4的损耗,所以我们能8小时的话就8小时使用,剩下的部分如果有多余那么再进行考虑,如果小于4小时,那么可以计算发现它的最小平均损耗为10/4=2.5>2.4,所以不如直接接在上一个8小时上,如果大于4小时我们也可以发现5小时的平均损耗是12/5=2.4,此时和继续接在后面是一样的,但显然如果大于5小时那么使用4-8小时才是最节省的,至此我们的讨论完成。

然后是输出的小问题,它要求如果是整数则输出整数,如果不是保留一位小数,我的处理方法是原数x10,再去考虑模10的余数,以此判断是否有小数位。

#include<bits/stdc++.h>
using namespace std;
int n,k;
double z,ans;
int main(){
    while(scanf("%d",&n)!=0&&n){
        if(n<=4)ans=10;
        else if(n<=8)ans=10+(n-4)*2;
        else{
            ans=n/8*18;
            if(n%8<=4)ans+=n%8*2.4;
            else ans+=10+(n%8-4)*2;
        }k=ans*10;
        k%10?printf("%.1lf\n",ans):printf("%d\n",k/10);
    }
    return 0;
}

EACMer如何拯救小学生

题目描述

你知道c需要中的缩写吗? 或者你知道ACM比赛中一些缩写的词组吗? 像Presentation Error (PE),Wrong Answer (WA),time limit exceeded (TLE)。 往往这些缩写可以带给我们一些方便的好处,也可以相当于一些专业词组。 现在要求你自己来定义缩写,根据你若输入的单词,注意,输入词组,输出他的缩写。

输入描述:

输入的第一行是一个整数T,表示一共有T组测试数据。

接下来有T行,每组测试数据占一行,每行有一个词组,每个词组由一个或多个单词组成;每组的单词个数不超过10个,每个单词有一个或多个大写或小写字母组成;

单词长度不超过10,由一个或多个空格分隔这些单词。

输出描述:

请为每组测试数据输出规定的缩写,每组输出占一行。

输入

3
Cool Down
Attack Disabled Carry
xiao xue sheng

输出

CD
ADC
XXS

说明

每行的单词不仅仅有一个,所以cin/scanf是不行的

此题主要考察的是对字符串的输入,处理,运用。首先要处理的是输入问题,由于scanf和cin %s 都是不可行的,因为每个单词之间是有空格隔开的,那么就需要能读取一行字符串的输入了,此时就可以用到gets了。

然后对于每一个字符串,我们一个一个扫过去,如果出现空格,那么就标记,表示下一个非空格要进行输出了,然后打出这个字符,值得注意的是这题需要判断字母大小写,跟俊ASCII码值很快就可以写出判断程序,同理找到依次类推,就可以写出代码了。

#include<bits/stdc++.h>
using namespace std;
char tmp,s[20][200];
int n,len,k;
bool flag=0;
int main(){
   scanf("%d",&n);tmp=getchar();//注意这里有一个换行符,要把它读取掉
   for(int i=1;i<=n;++i){
       gets(s[i]+1);//tmp=getchar();
   }
   for(int i=1;i<=n;++i){
   	  len=strlen(s[i]+1);flag=0;
      for(int j=1;j<=len;++j){
      	 if(!flag&&s[i][j]!=' '){
      	 	flag=1;k=(int)s[i][j];
      	 	if(s[i][j]>='a') s[i][j]=k-32;
			printf("%c",s[i][j]);
      	 	
      	 } 
      	 if(s[i][j]==' '&&flag) flag=0;
      } printf("\n");
   }
    return 0;
}

发表评论