竞赛讨论区 > 【题解】首届哈尔滨理工大学(荣成)"歌尔创客杯"新生赛
头像
王清楚
发布于 2019-12-21 18:22
+ 关注

【题解】首届哈尔滨理工大学(荣成)"歌尔创客杯"新生赛

A、会长的烦心事

水题
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
	int l,e1,b[10],i,pp,qq;
	char a[1100];
	while(scanf("%s",a)!=EOF)
	{
		l=e1=0;
		memset(b,0,sizeof(b));
		for(i=0;i<strlen(a);i++)
		{
			if(a[i]=='l')l++;
		else	if(a[i]=='e')e1++;
		else	if(a[i]=='a')b[0]++;
		else	if(a[i]=='g')b[1]++;
		else	if(a[i]=='u')b[2]++;
		else	if(a[i]=='f')b[3]++;
		else	if(a[i]=='o')b[4]++;
			
		}
		sort(b,b+5);
		pp=l/2;
		qq=e1/2;   
		if(pp>qq)pp=qq;
		if(pp>b[0])pp=b[0];
		printf("%d\n",pp);
	}
}

B、快来秒掉我!

格式控制
直接复制粘贴。

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

C、素数圆环


用的dfs暴力求解。枚举所有情况,看哪一种情况符合就输出哪一种情况。


D、电脑磨损程度

贪心
分析:
  1. .不足 4 小时肯定磨损 10
  2. 4-8 小时第二段直接计算
  3. 超过 8 小时优先看 8 小时的第二段与第一段的混合,超过 8 小时最后的部分在 4 以内走 2.4 磨损那段(肯定比 10 磨损合算,那个单算还 2.5 磨损),在 4-8 的话还走第二段。
核心代码:
if(n>8)
{ 
    while(n>=8) 
    {
        sum+=18;
        n-=8; 
    }  
    if(n<=4) 
    { 
        sum+=2.4*n;
    } 
    else 
    { 
        sum+=10+(n-4)*2; 
    } 
} 

E、ACMer如何拯救小学生


字符串处理
题意:提取字符串每个单词首字母,并且每个首字母均为大写。

方法:

1.注意回车有可能被当成字符读入缓冲区,造成错误。所以在每一个字符串

读入之前”\n”做处理,如下:

if(j==0)   
 getchar(); gets(a);
2..之后遍历每个字符串,O(n)的时间复杂度。

F、当会长和一群手贱的耗子在电梯相遇

数学问题
题意:看到去 n 楼的电梯灯亮或者灭,亮了返回 TRUE,否则时 FLASE。
方法:开辟一个一维数组,一遍遍历一遍标记就行吗?不过,n 数很大,一定超时,爆内存。
事实上,我们只需要 n 层所在的电梯灯,是亮是灭即可。也就是看 Ni 和 Ni 的倍数,是不是要去的电梯层数,而不对所有的电梯层数挨个操作。


G、当会长和一群手贱的耗子在电梯相遇

贪心 or dp

题意:求最少需要人民币的张数,动态规划或者贪心都可求解,在本题中贪心是可以求得最优解的。两层循环,平方级的时间复杂度完全 OK。

方法:
while(cin>>n)
{
    c=0;
    while(n!=0)
    {
        cin>>m;
        for(i=0; i<7; i++)
        {
            if (a[i]>m)
                continue;
            k=m/a[i];
            m=m-k*a[i];
            c=c+k;
        }
        n--;
    }
    cout<<c<<endl;
}

H、放轻松

简单排序
方法:注意数位的精度,在进行简单排序就可以 AC;(插排,冒泡,交换,选择,
快排,堆排不限)。

I、ACM协会晚会

数学问题
分析:简单数学问题,求 Cmn 的排列数即可。

J、会长爱旅游

DFS
分析:简单数学问题,求 Cmn 的排列数即可。
题意:对一个 N 的顶点的图进行遍历,找到对应关系。
第二种,用队列处理,起点入队,然后出队,找到跟起点相连的城市进队,那么这些城市的前一步就是出队的城市了,然后开始不停地出队入队,直到队空为止。思路不错,但是依旧会超时。城市 N 的数目很大,Queue 太过笨重。
此外如果直接建立二维数组 a[n][n],n 太大了,这样的二维数组用来记录城市关系绝对超出内存。用一个动态数组 Vector,利用 Vector 第一维定长为 MAX,第二维任意的特性。很好的避免了内存溢出。EX: vector<int>v[100005]; 所以,深搜(回溯)思想处理最正确。
伪码描述:
//深搜起点为 s,f 数组记录访问过的城市。
void dfs(int s)
{
    int i;
    for (i = 0; i < v[s].size(); i++)
    {
        if (f[v[s][i]])
            continue;
        f[v[s][i]] = s;
        dfs(v[s][i]);
    }
}


全部评论

(3) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐