第二届新生C语言竞赛解题报告.docx

第二届新生C语言竞赛解题报告.docx

《第二届新生C语言竞赛解题报告.docx》由会员分享，可在线阅读，更多相关《第二届新生C语言竞赛解题报告.docx（32页珍藏版）》请在冰点文库上搜索。

第二届新生C语言竞赛解题报告

第二届浙江师范大学C语言程序设计竞赛解题报告

（罗方炜，lfw2565295@,浙师大10计软）

比赛概述

首先是本届比赛的题目：

本次比赛总共十道题，由应宁宸，陈余康，张超，陈新弛，钟浙云组成的编题组负责出题，由罗方炜，詹皇彬组成的验题组负责验题和整体难易程度的把握，同时詹皇彬还负责了服务器的运行维护。

本次比赛的提交统计：

其中A，D，G为简单题，B，E，F，H，J为中等题，C，I为难题，比赛中的提交情况也符合这个题目难易度分类，A，D，G做出的人很多，获奖的人中，这三题基本要保证过掉。

本次比赛前十名的情况：

其中，名字前打”*”的同学是友情参赛人员，他们是ACM集训队大二的女将，为明年的省赛练兵。

剩下的5名同学是本次比赛一等奖的获得者，经过5个小时的角逐，潘旭脱颖而出，解得8道，夺得“新生杯”，曹俆康，任超群，陈政伊，陶柄丞解出6道以上，获得一等奖，恭喜他们。

具体的获奖情况，可以参见

题目讲解

A：

YQ的手表

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 249

Accepted:

 90

Description

小YQ上次很快完成了爸爸给她得任务，爸爸奖励了她一个电子手表。

小YQ非常喜欢她的电子表，没事就盯着她的电子表看。

有天她看见电子表上显示 

“12:

21”，小YQ觉得很漂亮。

现在给你一个时间，格式是xx:

xx，请你判断是否合法（也就是符合电子表显示的数字，比如00:

10合法，02:

30合法，23:

23合法，23:

66不合法，24:

00不合法）。

Input

输入数据一行，为一个字符串，用空格隔开。

表示时间时间，格式为XX:

XX，

Output

合法输出”Yes” 

不合法输出”No” 

SampleInput

00:

10

02:

30

23:

66

24:

00

SampleOutput

Yes

Yes

No

No

思路：

本题虽然是字符串形式输入一个“时间”，但格式比较固定，所以可以用scanf（“%d:

%d”,&a,&b）形式，当成是两个整个的输入，这样判断就很简单了，判断条件就是时针的值在0~23之间，分针的值在0~59之间。

参考代码：

#include

intmain（）

{

intm,n;

scanf（"%d:

%d",&m,&n）;

if（m>=0&&m<24&&n>=0&&n<60）printf（"Yes"）;

elseprintf（"No"）;

return0;

}

B：

Touch

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 133

Accepted:

 35

Description

现有面积无限大的一堵墙，墙上有根一端固定且无限长的杆，初始状态是竖直向上的。

 另外，在墙上有n个钉子。

为研究方便，我们以杆所在的方向为y轴，建立直角坐标系，如图：

现在，杆以下端（固定端）为中心，向右旋转，请问碰到的第一个钉子编号是多少？

针对上图：

即此时，墙上的杆固定端位于（0，4），且此时墙上有3个钉子，则碰到的第一个钉子编号是2.

Input

第一行有两个数y0,n,其中y0表示杆固定端位于（0，y0）,n表示有墙上有n个钉子。

接下来有n行，每行有两个数xi,yi（1<=i<=n）,表示第i个钉子的坐标为（xi,yi）. 

其中输入各数均是正整数，且不超过10000 

注意：

钉子的编号不一定是按x坐标递增来编号的（如样例2） 

Output

输出碰到的第一个钉子编号（输入数据，确保答案只有一个）

SampleInput

43

44

77

105

133

44

105

77

21

44

SampleOutput

2

2

1

Hint

样例1已在题目中描述过

样例2示意图

样例3示意图

思路：

设杆端点坐标为（0，Y），碰到的第一个钉子编号是i，则由该两个点组成的直线的斜率必定是最大的。

即Ki>=Kj（对任何的j!

=i）在比较两个斜率大小时，可以直接用y/x的形式，也可以转化为乘法判断，以避免浮点运算。

参考代码：

#include

#include

intmain（）{

intn;

doublem,x[10001],y[10001];

scanf（"%lf%d",&m,&n）;

if（m<=0||m>10000）while

（1）;

if（n<=0||n>10000）while

（1）;

doublemaxK;

intid;

for（inti=0;i

scanf（"%lf%lf",&x[i],&y[i]）;

if（x[i]<=0||x[i]>10000）while

（1）;

if（y[i]<=0||y[i]>10000）while

（1）;

y[i]-=m;

doublek=y[i]/x[i];

if（i==0）maxK=k,id=i;

elseif（maxK

maxK=k;

id=i;

}

}

for（inti=n-1;i>=0;i--）{//看看ID是不是唯一

if（maxK==（y[i]/x[i]））id=i;

}

printf（"%d\n",id+1）;

}

C：

日期

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 12

Accepted:

 1

Description

YNingC同学在看日历的时候想到一个问题。

问题很简单，今天是12月4日，今天又是星期天（万恶啊，为什么比赛都是安排在星期天啊~），不过好吧，那么纵观历史长河12月4日是星期天的概率是多少的？

假如2012不是世界末日，地球的寿命是无限大等等…… 

Input

数据只有一行,有三个数据，前两个是整数，M,D,表示M月D日，第三个数据是一串字符，为”Mon,Tue,Wed,Thu,Fri,Sat,Sun”,分别表示周一至周日。

Output

每组数据输出一行，输出一个概率保留4位小数，格式见样例。

SampleInput

124Sun

SampleOutput

14.5000%

Hint

用printf（"%%\n"）;输出"%"。

思路：

这题的思路主要就是找循环节，400年为一个循环，所以计算概率的时候，只要找到相应的分子天数与分母的天数就行。

做这道题的前提可以参考另外道计算天数的题，里面有闰年判断方法。

当然本题作为难题，主要因为用计算机程序寻找数字间的规律对新手来说比较难，但这个却是开动思维，探索发现的好题。

参考代码：

#include

#include

#include

usingnamespacestd;

intsum[15][40][10];

intmo[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

inty,m,d,w,T;

chars[20];

boolcheck（）{

if（m!

=2）returntrue;

if（y%4!

=0）returntrue;

if（y%100!

=0）returnfalse;

if（y%400==0）returnfalse;

returntrue;

}

voidadd（）{

w=（w+1）%7;

d++;

if（（d>mo[m]&&check（））||d-mo[m]>=2）{

m++;

d=1;

if（m==13）{

m=1;

y++;

}

}

}

voidinit（）{

for（inti=1;i<=12;i++）{

for（intj=1;j<=31;j++）{

for（intk=0;k<=7;k++）{

sum[i][j][k]=0;

}

}

}

y=2011,m=10,d=3,w=0;

for（inti=0;i<146097;i++）{

sum[m][d][w]++;

sum[m][d][7]++;

add（）;

}

}

voidtrans（）{

if（s[0]=='M'）w=0;

elseif（s[0]=='T'）{

if（s[1]=='u'）w=1;

elsew=3;

}elseif（s[0]=='W'）w=2;

elseif（s[0]=='F'）w=4;

elseif（s[0]=='S'）{

if（s[1]=='a'）w=5;

elsew=6;

}

}

intmain（）{

init（）;

scanf（"%d%d%s",&m,&d,&s）;

trans（）;

printf（"%0.4lf%%\n",sum[m][d][w]*100.0/sum[m][d][7]）;

return0;

}

D：

比大小

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 162

Accepted:

 103

Description

给出三个正整数a，b，c，请判断a2+b2与c2的大小关系

Input

每行有三个正整数a，b，c（不超过10000）

Output

如果满足a2+b2c2，则输出>。

SampleInput

345

112

543

SampleOutput

=

<

>

思路：

这题应该算最简单的题了，输入三个数字a,b,c，然后判断a*a+b*b与c*c的大小就行。

参考代码：

#include

intmain（）

{

inta,b,c;

scanf（"%d%d%d",&a,&b,&c）;

if（a*a+b*b

if（a*a+b*b==c*c）printf（"="）;

if（a*a+b*b>c*c）printf（">"）;

return0;

}

E：

不等式

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 148

Accepted:

 21

Description

FarmerJohn喜欢不等式，但是他数学很差，现在他需要你的帮助，帮他判断能否成功找到n个正整数，a1, a2, ..., an,使得满足下列不等式：

a12 + a22 + ... + an2 ≥ x

a1 + a2 + ... + an ≤ y

Input

输入包含三个整数n,xandy（1 ≤ n ≤ 104, 1 ≤ x ≤ 109, 1 ≤ y ≤ 104）. 

Output

如果能够找到，输出”Yes”，否则输出”No”。

SampleInput

51515

232

SampleOutput

Yes

No

思路：

假如两个数a,b,a+b的和固定，做a*a+b*b运算时，绝对值（a-b）越大,a*a+b*b的值就越大。

所以，可以推出，在保证a0~an都为正整数的前提下，当a0为最大，且a1...ai...an都为1的时候是满足两个不等式最优条件，所以只要判断这种情况的数据就可以了。

参考代码：

#include

intmain（）{

inta,sum;

intn,x,y;

scanf（"%d%d%d",&n,&x,&y）;

if（n>10000）while

（1）;

if（x>1000000000）while

（1）;

if（y>10000）while

（1）;

if（n>y）{

printf（"No\n"）;

return0;

}

sum=n-1;

a=y-（n-1）;

sum+=a*a;

if（sum

else{

printf（"Yes\n"）;

}

return0;

}

F：

又见hello

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 27

Accepted:

 16

Description

小A并不满足于数hello的个数，野心勃勃的他找了篇长文章，奇怪的是这篇文章仅由h、e、l、o四个字符组成。

而小A想去掉文章中的一些字符，仅留下一个hello，小A这次想知道，去字符的方法有几种。

Input

有多个测试文件，每个文件中仅有一行，为一个串，仅由h、e、l、o四个字符组成，串长度不大于200，至少1个字符。

Output

一个整数,去字符的方法种数。

SampleInput

hellollo

hellllo

hhello

hhehhllo

SampleOutput

7

6

2

2

思路：

本题其实为动态规划题.状态定Dp[i][j]表示为到串的第i位为止，得到以j结尾的串的方法个数，也就是将除留下的5个字符外的其它字符全部删除，这样就与原问题等价了。

其中，

j==0为以h结尾。

j==1为以e结尾。

j==2为以第一个l结尾。

j==3为以第二个l结尾。

j==4为以o结尾。

状态转移

Dp[i][j]=Dp[i-1][j];j=0,1,2,3,4.

If（arr[i]==’h’）Dp[i][0]++;

If（arr[i]==’e’）Dp[i][1]+=Dp[i-1][0];

If（arr[i]==’l’）Dp[i][2]+=Dp[i-1][1],Dp[i][3]+=Dp[i-1][2];

If（arr[i]==’o’）Dp[i][4]+=Dp[i-1][3];

状态临界

Dp[i][j]=0，I=0,1,2,3….strlen（arr）;

If（arr[0]==‘h’）Dp[0][0]=1;

最后的答案为

Dp[strlen（arr）-1][4];

但考虑到动态规划的算法对新生太难，几乎没什么人接触过，所以把题目规模变小了，看看大家有没有其他方法做。

果然，解出此题的人几乎都用了暴搜，用5重for循环枚举可能性，本次比赛可以通过，但是当数据规模稍微大点就不行了，所以想进一步入门ACM程序竞赛的同学，有必要学一下动态规划。

参考代码：

#include

#include

intmain（）{

intdp[205][5];//表示到i个字符，组成h,he,hel,hell,hello有多少种

chara[205];

intlen;

scanf（"%s",a）;

len=strlen（a）;

if（len>200）while

（1）;

for（inti=0;i

for（intj=0;j<5;j++）dp[i][j]=0;

}

for（inti=0;i

for（intj=0;j<5;j++）{

if（i）{

dp[i][j]=dp[i-1][j];

}

}

if（a[i]=='h'）dp[i][0]++;

elseif（a[i]=='e'）dp[i][1]+=dp[i-1][0];

elseif（a[i]=='l'）dp[i][2]+=dp[i-1][1],

dp[i][3]+=dp[i-1][2];

elseif（a[i]=='o'）dp[i][4]+=dp[i-1][3];

elsewhile

（1）;

for（intj=0;j<5;j++）if（dp[i][j]>1000000000）while

（1）;

}

printf（"%d\n",dp[len-1][4]）;

}

G：

hello

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 97

Accepted:

 64

Description

礼是中华民族的传统美德，需要我们发扬光大。

最近小A初学英语，刚学会了讲hello，非常地兴奋。

她专注与发现一片文章中hello的数量。

给定一段只由26个小写字母组成的文章，请输出其中有多少个hello，只有连续的5个字母是hello才算一次。

Input

一组测试数据，里面有一段文章。

只由26个小写字母组成。

文章长度不大于100个字符，至少一个字符。

Output

输出其中有多少个hello。

SampleInput

hellohhhellhellhooohellohhello

SampleOutput

3

思路：

简单模拟题，以文章中的每个字符为开头，查看以它连续的5个字符是不是hello，若是则答案加1。

考察的是对字符串的使用和for循环语句的使用。

参考代码：

#include

#include

intmain（）{

chara[205];

intlen;

inti,res=0;

scanf（"%s",a）;

len=strlen（a）;

if（len>100）while

（1）;

for（i=0;i

if（a[i]<'a'||a[i]>'z'）while

（1）;

if（i+4>=len）continue;

if（a[i]=='h'&&a[i+1]=='e'&&a[i+2]=='l'&&a[i+3]=='l'&&a[i+4]=='o'）res++;

}

printf（"%d\n",res）;

}

H：

可爱的YQ

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 72

Accepted:

 10

Description

小YQ是个即可爱又聪明的小孩子。

有天，爸爸给她一个有意思的任务，就是在电脑的一个文件中，找到特定的文件。

小YQ还不会用搜索文件的的方法，但是她会点鼠标，现在给你文件夹的信息，请你能告诉小YQ，她最少点几次鼠标就能发现这个文件。

Input

输入数据第一行有两个数n（10<=n<=5000），m（1<=m<=10）,n表示字符串str的长度，m表示询问的个数。

第二行一个字符串str，表示文件的信息，字符串中所包含的文件名都不一样。

用括号来表示子文件，用逗号分开文件夹，具体见样例。

接下来m行，每行一个字符串，长度不超过10，表示小YQ要找的文件名。

Output

对于每个询问，输出最少点击鼠标的次数。

如果这个文件不存在，输出"areyoukiddingme?

"

SampleInput

685

zhangc（program（poj（1000,1001,1002）,hdu（1003,1004）,zjnu（1005,1006）））

poj

1002

1003

1006

zju

SampleOutput

2

3

3

3

areyoukiddingme?

思路：

此题比较简单，数据不大直接暴力查找就好了。

查找到当前文件时，要点击的鼠标次数就是在此之前左括号的个数总和减去右括号的个数总和。

注意一下子串问题,在匹配前后判断一下是否为非字母,保证询问的文件匹配到的是一个完整的文件名。

这题对新手来说，还是考察字符串和for循环语句的操作，只是难度比上一题大了。

参考代码：

#include

#include

#defineM5005

charfile[M];

charstr[20];

intmain（）{

intn,m;

inti,j,k;

scanf（"%d%d",&n,&m）;

scanf（"%s",file）;

if（n<10||n>5000）while

（1）;

if（m>10）while

（1）;

while（m--）{

scanf（"%s",str）;

intlen=strlen（str）;

if（len>10）while

（1）;

intcnt=0;

for（i=0;i<=n-len;i++）{

if（file[i]=='（'）cnt++;

elseif（file[i]=='）'）cnt--;

else{

if（!

（i==0||file[i-1]==','||file[i-1]=='（'））continue;

for（j=0;j

if（file[i+j]!

=str[j]）break;

if（j>=len）{

charbehind=file[i+j];

if（behind=='（'||behind==','||behind=='）'||behind=='\0'）

break;

}

}

}

if（i<=n-len）printf（"%d\n",cnt）;

elseprintf（"areyoukiddingme?

\n"）;

}

return0;

}

I：

菱形

TimeLimit:

 1000MS

MemoryLimit:

 32768K

TotalSubmissions:

 17

Accepted:

 1

Description

菱形是对称性质很好的一种图形，我们用Dia（x0,y0,r1,r2）来表示一个菱形，它是由菱形的中心坐标以及对角线信息确定的，其中（x0,y0）表示中心坐标，r1为水平对角线长度的一半，r2为竖直对角线长度的一半，如图所示：

现有两个菱形Dia（x0,y0,r1,r2），Dia（x0’,y0’,r1’,r2’）,请判断该两个菱形的位置关系 

如果相交，请输出intersection 

如果是包含关系，请输出containing 

如果是相离关系，请输出away 

注意：

1.只要两菱形在边界上有公共点，此时就认为两菱形