【题解】首届哈尔滨理工大学（荣成）＂歌尔创客杯＂新生赛

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、电脑磨损程度

贪心

分析：

.不足 4 小时肯定磨损 10
4-8 小时第二段直接计算
超过 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]); } }