【题解】首届哈尔滨理工大学（荣成）＂歌尔创客杯＂新生赛
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]);
}
}
投递旷视等公司10个岗位 >
