第十届北大青鸟杯浙江师范大学程序设计竞赛解题报告.docx
- 文档编号:17955379
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:40
- 大小:802.79KB
第十届北大青鸟杯浙江师范大学程序设计竞赛解题报告.docx
《第十届北大青鸟杯浙江师范大学程序设计竞赛解题报告.docx》由会员分享,可在线阅读,更多相关《第十届北大青鸟杯浙江师范大学程序设计竞赛解题报告.docx(40页珍藏版)》请在冰点文库上搜索。
第十届北大青鸟杯浙江师范大学程序设计竞赛解题报告
第十届“北大青鸟”杯浙江师范大学程序设计竞赛解题报告
(罗方炜,lfw2565295@,浙师大10计软)
比赛概述
首先是本届比赛的题目:
总共11题
本次比赛的提交统计:
其中A,C,K相对简单,B,D,F为中等题,E,G,H为稍难题,I,J没人解出
本次比赛前十名的情况:
有两名同学成功解出8道,还有1名同学解出7道,6道的有些数量,同时恭喜前6名获得本次比赛的一等奖,同时前十名获得比赛奖品——T恤。
题目讲解
A:
YesOrNo
TimeLimit:
1000MS
MemoryLimit:
65536K
TotalSubmissions:
596
Accepted:
94
Description
在二维平面上有两点P1(x1,y1),P2(x2,y2),现今,P1想向P2靠拢,但只能往斜上方走(x1+1,y1+1),或往斜下方走(x1+1,y1-1)。
请问P1能否抵达P2,如果可以输出Yes,否则输出No。
Input
第一行为一个正整数t(t<=100),代表测试组数。
每一组测试数据:
一行有四个整数x1,y1,x2,y2。
(各数值均大于等于0且小于等于100000)
Output
对于每一组测试数据,输出一行结果:
如果P1能够抵达P2,输出Yes
否则,输出No
SampleInput
3
0011
0020
0030
SampleOutput
Yes
Yes
No
Hint
没忘记初中方程组就秒了这题拿下SecondBlood吧~
思路:
此题被作为简单题,意思是从一个点A要走到另外一个点B是否可行,而行走的办法只能是两种,即从(x,y)点出发,下一步只能到(x+1,y+1)(*)或者(x+1,y-1)(**),这可以设一个方程,设(*)走了a次,(**)走了b次,那么联立以后就是x1+a+b=x2;y1+a-b=y2;那么方程就是求是否有a>=0和b>=0满足这个方程组,很多同学卡在这题是因为根本没有想到这个方法。
参考代码:
#include
#include
intx1,y1,x2,y2;
intmain()
{
intt,n;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
n=x2-x1+y2-y1;
if(n%2==1){
printf("No\n");
}else{
n/=2;
if(n>=0&&n<=x2-x1){
printf("Yes\n");
}elseprintf("No\n");
}
}
return0;
}
B:
勇士出征
TimeLimit:
1000MS
MemoryLimit:
65536K
TotalSubmissions:
144
Accepted:
43
Description
一个神奇的梦,把你带到了三国时代,你变成了蜀国的大将。
正是蜀魏对阵之时,刘备召集部下,欲派出勇士与敌军大将单挑,现在蜀国大将们排成一纵队,由刘备亲检查队首的这名大将是否可以出战,判断的原则是:
如果队首的这名大将的战斗力是当前队列中最强的,则由他出战,否则他将会被掉到队列的尾部,出战过的大将不会在回到出战的队列中,由于蜀国大将甚多,你现在最关心的就是你是第几个出战的。
Input
第一行一个整数case(case<=100),表示测试数据的组数。
对于每组测试数据,第一行两个整数,N和K,表示当前队伍中的人数和你所在的位置。
接下来N个数,表示表示队伍中每个大将的战斗力。
(0 Output 对于每组测试数据输出一个整数,表示你是第几个出战的。 SampleInput 3 11 5 43 1234 61 119111 SampleOutput 1 2 5 思路: 此题比较简单,用队列直接模拟即可,对于队首元素,判断队列中是否有元素比它大,有比它大的,就把它放到队尾,如果没有,就直接出队列。 用数组写起来会很方便,可用两个变量L,H表示队首和队尾下标。 此题考察的是大家是否能模拟整个队列循环的过程,只要在程序的写法上注意点小小的优化还是比较简单的,可能很多同学不知道队列的知识,需要参考数据结构里的知识。 参考代码: #include #defineM105 structnode{ intnum,id; }Q[M*M]; intmain(){ intcas,i,k,L,R,my; scanf("%d",&cas); while(cas--&&scanf("%d%d",&R,&my)){ for(i=1;i<=R;i++){ scanf("%d",&Q[i].num); Q[i].id=i; } L=0; intcnt=1; while(L<=R){ k=L; for(i=L+1;i<=R;i++) if(Q[i].num>Q[k].num)k=i; if(Q[k].id==my)break; cnt++; for(i=L;i Q[++R]=Q[i]; L=k+1; } printf("%d\n",cnt); } return0; } C: 寻找acm TimeLimit: 2000MS MemoryLimit: 65536K TotalSubmissions: 143 Accepted: 94 Description 作为一个acmer,应该具备团队合作能力和分析问题能力。 给你一个只有a,c和m的字符串,你要依次取3个字母使之恰好为acm。 比如串 accmmmca你可以取 12345678 ac_m____ ac__m___ ac___m__ a_cm____ a_c_m___ a_c__m__共6种。 你只要给出给你的串有多少种方案能组成acm。 Input 一个只有acm3种字母的串(长度<2000) Output 一个整数一行,表示给你的串有多少种方案能组成acm。 SampleInput accmmmca SampleOutput 6 思路: 此题是一道字符串题目,题目意思就是给一串字符串,问里面有多少个带有acm的子串,本题方法很多,而我想到的就是枚举c的位置,接着把c之前的a个数和c之后m的个数的乘积累加起来就好了,这样的复杂度为O(n)比赛中很多同学使用了暴力的方法,最高的复杂度为O(n^3),但也可以通过。 参考代码: #include #include charT[100000]; intmain() { gets(T); intl=strlen(T); inta=0,m=0; for(inti=0;i { if(T[i]=='m')m++; } intans=0,x,y; for(inti=0;i if(T[i]=='a')a++; elseif(T[i]=='m')m--; elseif(T[i]=='c')ans+=a*m; elseprintf("WA"); } printf("%d\n",ans); } D: 街亭之战 TimeLimit: 2000MS MemoryLimit: 65536K TotalSubmissions: 55 Accepted: 16 Description 公元228年春天,诸葛亮出兵伐魏,南安、安定、天水三城望风而降。 此后,在军事要地街亭的防守中,诸葛亮没有使用宿将赵云以及魏延,而是使用了虽然智谋过人,与诸葛亮多次英雄所见略同,但缺少临阵经验的马谡。 派马谡带领五万多人马做先锋,到军事重镇街亭去抵御魏军。 魏国的大将军曹真派张郃为先锋,带领五万人来应敌。 马谡自小熟谙兵法,军中共有N支分队(N<=20),每支部队已知人数,马谡决定从中挑选K(K<=N)支分队前去抵御魏军。 诸葛亮临行前嘱托,部队总人数为素数时,可以摆出八卦阵以制魏军! 马谡熟谙兵法,但数学差得很,只知道素数是只能被1和自身整除的数,他请你帮忙计算有多少种调兵遣将的方法可以摆开八卦阵。 观今夜天象,知天下大事。 Input 第一行是测试数据组数T(T<=10),第二行开始,每组测试数据先给出N,K,然后是另起一行N个数字,表示N支部队的人数。 Output 每组测试数据输出一个答案,表示方案种数。 SampleInput 1 52 2389999 SampleOutput 4 Hint 2+3,2+9,8+9,3+8都是素数 思路: 此题题目是从一堆数字中找K个数,使得这K个数的和是素数,用的方法是C(N,K)的DFS复杂度搜索出K个数的所有可能种类,接着判断下是否是素数,因为要用到数据结构的东西,很多没有学过的同学就很麻烦了,但对集训队员来说,要算基本功了。 从N个队伍中选取K个队伍显然是C(N,K)的组合,极限数据C(20,10)=184756种,然后依次判断是否素数,可以用最朴素的1——sqrt(n)的判断也不会超时。 C(N,K)的组合数选取可以用2^N的“选”或“不选”的深搜方法: Dfs(now,s,sum)其中now表示当前需要考虑的编号,s表示已选取个数,sum表示已选取的数的和,那么dfs(now+1,s,sum)表示跳过now这个数,“不取”;dfs(now+1,s+1,sum+A[now])表示选上now这个数,最后当已选了K个人就进行一次判素数,如果是素数最后答案+1. 这题用于考验选手编程功底,不需要什么想法,只要能实现出来,AC就没问题。 参考代码: #include #include #include longn,k,a[21],used[21]={0},ans=0; intprime(longx){ longi; if(x==1)return0; elseif(x==2)return1; else{ for(i=2;i<=sqrt(x);i++) if(x%i==0) return0; return1; } } voiddfs(longkk,longss,longsum){ longi; if(kk>=k){ if(prime(sum)==1) ans++; }else{ for(i=ss+1;i<=n;i++) if(! used[i]){ used[i]=1; dfs(kk+1,i,sum+a[i]); used[i]=0; } } } voidwrite(){ printf("%d\n",ans); } intmain(){ longi; inttt; scanf("%d",&tt); while(tt--){ scanf("%ld%ld",&n,&k); ans=0; for(i=1;i<=n;i++) scanf("%ld",&a[i]); dfs(0,0,0); write(); } return0; } E: 太空行走 TimeLimit: 1000MS MemoryLimit: 65536K TotalSubmissions: 6 Accepted: 4 Description 宇航员在太空中迷失了方向,在他的起始位置现在建立一个虚拟xyz坐标系,称为绝对坐标系,宇航员正面的方向为x轴正方向,头顶方向为z轴正方向,则宇航员的初始状态如下图所示: 现对六个方向分别标号,x,y,z正方向分别为0,1,2,负方向分别为3,4,5;称它们为绝对方向。 宇航员在宇宙中只沿着与绝对坐标系xyz轴平行的方向行走,但是他不知道自己当前绝对坐标和自己面向的绝对方向。 任务描述: 请根据宇航员对自己在相对方向上移动的描述确定宇航员最终的绝对坐标和面向的绝对方向。 对在相对方向上移动的描述及意义如下: forwardx 向前走x米。 backx 先转向后,再走x米。 leftx先转向左,再走x米。 rightx先转向右,再走x米。 upx先面向上,再走x米。 downx先面向下,再走x米。 其中向上和向下如下图所示: Input 第一行一个正整数m,表示测试数据的组数。 每组测试数据第一行是一个正整数n(1<=n<=10000)表示宇航员行走的次数,下面n行每行输入一次相对行走,格式如上所述,其中(1<=x<=10000为正整数)。 Output 对于每组输入数据输出一行,xyzp,中间用空格隔开,xyz是宇航员的位置的绝对坐标,p是宇航员面向的绝对方向编号(0<=p<=5)。 SampleInput 1 6 left10 right11 up12 down13 forward14 back15 SampleOutput 23-10123 思路: 此题是一道模拟题,但是有各种方向需要判断,所以稍微有点繁琐,不过只要耐心,细心慢慢写if,else条件语句,也能很快做出来,代码虽然长点,但是思考的部分不用很多。 另外一种方法就是总结些规律,可以把很多类似的代码集成,初始化数组判方向,这样就可以写的很精简了,在比赛中,倒还是推荐前者的方法。 参考代码: #include ! #include intHead,Nova,x,y,z; intDirect[6][3]={{1,0,0},{0,1,0},{0,0,1},{-1,0,0},{0,-1,0},{0,0,-1}}; intLeft[6][6]={{-1,2,4,-1,5,1},{5,-1,0,2,-1,3},{1,3,-1,4,0,-1},{-1,5,1,-1,2,4},{2,-1,3,5,-1,0},{4,0,-1,1,3,-1}}; intreverse(inti){return(i+3)%6;} voidforward(intfoot){x+=Direct[Nova][0]*foot;y+=Direct[Nova][1]*foot;z+=Direct[Nova][2]*foot;} voidback(intfoot){Nova=reverse(Nova);forward(foot);} voidleft(intfoot){Nova=Left[Nova][Head];forward(foot);} voidright(intfoot){Nova=reverse(Left[Nova][Head]);forward(foot);} voidup(intfoot){inttemp=Head;Head=reverse(Nova);Nova=temp;forward(foot);} voiddown(intfoot){inttemp=Nova;Nova=reverse(Head);Head=temp;forward(foot);} intmain(){ inttest,i,n,foot; charstr[100]; scanf("%d",&test); while(test--){ Nova=0;Head=2;x=0;y=0;z=0; scanf("%d",&n); for(i=0;i scanf("%s",str);scanf("%d",&foot); if(strcmp(str,"forward")==0)forward(foot); elseif(strcmp(str,"back")==0)back(foot); elseif(strcmp(str,"left")==0)left(foot); elseif(strcmp(str,"right")==0)right(foot); elseif(strcmp(str,"up")==0)up(foot); elseif(strcmp(str,"down")==0)down(foot); }printf("%d%d%d%d\n",x,y,z,Nova); } return0; } F: 头脑风暴 TimeLimit: 1000MS MemoryLimit: 65536K TotalSubmissions: 128 Accepted: 32 Description YNingC是一位数学专业的学生,平时他喜欢玩一些数字,特别是一些趣味的数学问题。 正因为如此,很多同学都会把自己遇到的一些有趣的数学问题告诉YNingC,更多的时候是想寻求他的帮助,希望他能解决这些关于数学和数字的问题。 可是最近由于繁忙的学业和一些课外活动,使得有时候YNingC同学没有时间帮助同学解决问题,可帮助同学一直是YNingC所热爱的,所以他就把遇到的问题交给聪明的Programmers,希望你们能用最快的速度帮助他解决这个问题。 问题是这样子的,有这么一个数列 而现在找到这样的一个j,对任意的k(k从1到n)使得Sjk都为正数,但是这个的j有很多个,现在需要求得有多少个这样的j。 Input 有多组测试数据。 第一行,输入T(1<=T<=30)表示一共有多少个测试数据。 接下来是T组测试数据。 每组测试数据的第一行输入n(1<=n<=200,000),接下来一行是n个数据ai。 Output 输出一行表示一个数字M,M表示有M个不同的j满足条件。 SampleInput 2 5 1-11-11 7 1111111 SampleOutput 1 7 思路: 题目是给定一串a[],求有多少个j满足对任意Sjk都是正数。 最初的想法就是对j=1的情况,求出所有s0k,并令s00=0,记xj=min{s0k|k<=j},yj=min{s0k|k>=i},那么对0 不过显然有更漂亮的做法,因为答案其实就是1的个数减去-1的个数! 所以可以写的很简单,比赛中通过的同学基本上都是猜到了这个结论。 参考代码: #include #include usingnamespacestd; inta[200001]; ints[200001]; intx[200001]; inty[200001]; intmain(){ intcas; cin>>cas; while(cas--){ intn;scanf("%d",&n); s[0]=0; for(inti=1;i<=n;i++){ scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; if(i==1)x[i]=s[i]; elsex[i]=min(s[i],x[i-1]); } y[n+1]=10000000; for(inti=n;i>=1;i--){ y[i]=min(y[i+1],s[i]); } intret=0; for(inti=1;i<=n;i++){ if(s[i] ret++; } } printf("%d\n",ret); } return0; } G: 血战当阳 TimeLimit: 1000MS MemoryLimit: 65536K TotalSubmissions: 95 Accepted: 7 Description 血战当阳: 长坂,又名长坂坡,当阳市西南郊。 相传刘备部将赵云(字子龙)单枪匹马,七次杀进重围,救出甘夫人及幼主刘禅。 而新三国志英杰传的这一关就是要消灭这些敌人。 此关敌人众多(N<1000),而且我方只有赵云一人,所以本人用了强大的修改器,问你赵云至少需要多少血能消灭光这些敌人,而自己不死。 所谓一回合是这样的: 敌人回合,所有存活的敌人对我方某人攻击,我方减血。 我方回合,所有存活的我方人员对敌人某人攻击,敌方减血。 敌方每个人都有一个血量Hi,当血量<=0时,判为死亡,从战场消失。 赵云一次攻击可以造成某个敌人减少Di。 Input 第一行一个整数N,表示有N个敌人。 接下来有N行,每行三个整数,第i+1行表示第i个敌人的血量Hi,受到赵云攻击时减少的血量Di,以及他能对赵云造成血量Fi的伤害。 (i=1,2,3...N) Output 一个整数一行,表示赵云至少需要多少血能消灭光这些敌人,而自己不死。 (答案int内) SampleInput 2 511 311 SampleOutput 12 Hint 解释: 前三回合敌人两个都对赵云造成伤害,赵云都杀第二个敌兵,第三回合结束杀死第二个敌兵,每回合受到2伤害,伤害6; 第4-8回合赵云受到第一个敌兵的1伤害,5回合杀死,伤害5。 此时赵云至少1血。 所以赵云初始至少12血。 思路: 题目的解法是杀死第i个人需要xi回合,他每回合对赵云有yi伤害。 设i,j两个敌人,分别是第k,k+1个杀死的。 那么第k个是i的情况,赵云受到的伤害为T1=xi*(yi+yj)+xj*yj; 如果第k个是j的情况,赵云受到的伤害为T2=xj*(yi+yj)+xi*yi。 (当然T1,T2中没有除了i,j外的人对赵云的伤害,但是下面是看他们的差,两次应该相等而不影响) T=T1-T2=xi*yj-xj*yi。 所以,如果T<0(即xi*yj 所以核心的部分仅仅是个排序。 参考代码: #include
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十 北大 青鸟 浙江 师范大学 程序设计 竞赛 解题 报告