1、第十届北大青鸟杯浙江师范大学程序设计竞赛解题报告第十届“北大青鸟”杯浙江师范大学程序设计竞赛解题报告（罗方炜，lfw2565295 ,浙师大10计软）比赛概述首先是本届比赛的题目：总共11题本次比赛的提交统计：其中A,C,K相对简单，B,D,F为中等题，E,G,H为稍难题，I,J没人解出本次比赛前十名的情况：有两名同学成功解出8道，还有1名同学解出7道，6道的有些数量，同时恭喜前6名获得本次比赛的一等奖，同时前十名获得比赛奖品T恤。题目讲解A：Yes Or NoTime Limit:1000MSMemory Limit:65536KTotal Submissions:596Accepted:9
2、4Description在二维平面上有两点P1(x1,y1)，P2(x2,y2)，现今，P1想向P2靠拢，但只能往斜上方走(x1+1，y1+1)，或往斜下方走(x1+1,y1-1)。请问P1能否抵达P2，如果可以输出Yes,否则输出No。Input第一行为一个正整数t（t=0和b=0满足这个方程组，很多同学卡在这题是因为根本没有想到这个方法。参考代码：#include#includeint x1,y1,x2,y2;int main() int t,n; scanf(%d,&t); while(t-) scanf(%d%d%d%d,&x1,&y1,&x2,&y2); n=x2-x1+y2-y1;
3、 if(n%2=1) printf(Non); else n/=2; if(n=0&n=x2-x1) printf(Yesn); else printf(Non); return 0;B：勇士出征Time Limit:1000MSMemory Limit:65536KTotal Submissions:144Accepted:43Description一个神奇的梦，把你带到了三国时代，你变成了蜀国的大将。正是蜀魏对阵之时，刘备召集部下，欲派出勇士与敌军大将单挑，现在蜀国大将们排成一纵队，由刘备亲检查队首的这名大将是否可以出战，判断的原则是：如果队首的这名大将的战斗力是当前队列中最强的，则由他出
4、战，否则他将会被掉到队列的尾部，出战过的大将不会在回到出战的队列中，由于蜀国大将甚多，你现在最关心的就是你是第几个出战的。Input第一行一个整数case(case = 100)，表示测试数据的组数。对于每组测试数据，第一行两个整数，N和K，表示当前队伍中的人数和你所在的位置。接下来N个数，表示表示队伍中每个大将的战斗力。（0 N = 100,0 K = N）Output对于每组测试数据输出一个整数，表示你是第几个出战的。Sample Input31 154 31 2 3 46 11 1 9 1 1 1Sample Output1 25思路：此题比较简单，用队列直接模拟即可，对于队首元素，判断
5、队列中是否有元素比它大，有比它大的，就把它放到队尾，如果没有，就直接出队列。用数组写起来会很方便，可用两个变量L，H 表示队首和队尾下标。此题考察的是大家是否能模拟整个队列循环的过程，只要在程序的写法上注意点小小的优化还是比较简单的，可能很多同学不知道队列的知识，需要参考数据结构里的知识。参考代码：#include#define M 105struct node int num, id; QM*M;int main() int cas, i, k, L, R, my; scanf(%d, &cas); while (cas- & scanf(%d %d, &R, &my) for (i = 1
6、; i = R; i+) scanf(%d, &Qi.num); Qi.id = i; L = 0; int cnt = 1; while (L = R) k = L; for (i = L + 1; i Qk.num)k = i; if (Qk.id = my)break; cnt+; for (i = L; i k; i+) Q+R = Qi; L = k + 1; printf(%dn, cnt); return 0;C：寻找acmTime Limit:2000MSMemory Limit:65536KTotal Submissions:143Accepted:94Description
7、作为一个acmer，应该具备团队合作能力和分析问题能力。给你一个只有a，c和m的字符串，你要依次取3个字母使之恰好为acm。比如串accmmmca 你可以取12345678ac_m_ac_m_ac_m_a_cm_a_c_m_a_c_m_共6种。你只要给出给你的串有多少种方案能组成acm。Input一个只有acm3种字母的串 （长度2000）Output一个整数一行，表示给你的串有多少种方案能组成acm。Sample InputaccmmmcaSample Output6思路:此题是一道字符串题目，题目意思就是给一串字符串，问里面有多少个带有acm的子串，本题方法很多，而我想到的就是枚举c的位置
8、，接着把c之前的a个数和c之后m的个数的乘积累加起来就好了，这样的复杂度为O(n)比赛中很多同学使用了暴力的方法，最高的复杂度为O(n3)，但也可以通过。参考代码：#include#includechar T100000;int main() gets(T); int l=strlen(T); int a=0,m=0; for(int i=0;il;i+) if(Ti=m)m+; int ans=0,x,y; for(int i=0;il;i+) if(Ti=a)a+; else if(Ti=m)m-; else if(Ti=c)ans+=a*m; else printf(WA); print
9、f(%dn,ans);D：街亭之战Time Limit:2000MSMemory Limit:65536KTotal Submissions:55Accepted:16Description公元228年春天，诸葛亮出兵伐魏，南安、安定、天水三城望风而降。此后，在军事要地街亭的防守中，诸葛亮没有使用宿将赵云以及魏延，而是使用了虽然智谋过人，与诸葛亮多次英雄所见略同，但缺少临阵经验的马谡。派马谡带领五万多人马做先锋，到军事重镇街亭去抵御魏军。魏国的大将军曹真派张郃为先锋，带领五万人来应敌。马谡自小熟谙兵法，军中共有N支分队(N=20)，每支部队已知人数，马谡决定从中挑选K(K=N)支分队前去抵御魏
10、军。诸葛亮临行前嘱托，部队总人数为素数时，可以摆出八卦阵以制魏军！马谡熟谙兵法，但数学差得很，只知道素数是只能被1和自身整除的数，他请你帮忙计算有多少种调兵遣将的方法可以摆开八卦阵。观今夜天象，知天下大事。Input第一行是测试数据组数T(T=10)，第二行开始，每组测试数据先给出N,K，然后是另起一行N个数字，表示N支部队的人数。Output每组测试数据输出一个答案，表示方案种数。Sample Input15 22 3 8 9 999Sample Output4Hint2+3,2+9,8+9,3+8都是素数思路：此题题目是从一堆数字中找K个数，使得这K个数的和是素数，用的方法是C(N,K)的
11、DFS复杂度搜索出K个数的所有可能种类，接着判断下是否是素数，因为要用到数据结构的东西，很多没有学过的同学就很麻烦了，但对集训队员来说，要算基本功了。从N个队伍中选取K个队伍显然是C(N,K)的组合，极限数据C(20,10) = 184756种，然后依次判断是否素数，可以用最朴素的1sqrt(n)的判断也不会超时。C(N,K)的组合数选取可以用2N的“选”或“不选”的深搜方法：Dfs(now,s,sum)其中now表示当前需要考虑的编号，s表示已选取个数，sum表示已选取的数的和，那么dfs(now+1,s,sum)表示跳过now这个数，“不取”；dfs(now+1,s+1,sum+Anow)
12、表示选上now这个数，最后当已选了K个人就进行一次判素数，如果是素数最后答案+1.这题用于考验选手编程功底，不需要什么想法，只要能实现出来，AC就没问题。参考代码：#include #include #include long n, k, a21, used21 = 0, ans = 0;int prime(long x) long i; if (x = 1) return 0; else if (x = 2) return 1; else for (i = 2; i = k) if (prime(sum) = 1) ans+; else for (i = ss + 1; i = n; i+)
13、 if (!usedi) usedi = 1; dfs(kk + 1, i, sum + ai); usedi = 0; void write() printf(%dn, ans);int main() long i; int tt; scanf(%d,&tt); while (tt-) scanf(%ld%ld, &n, &k); ans = 0; for (i = 1; i = n; i+) scanf(%ld, &ai); dfs(0, 0, 0); write(); return 0;E：太空行走Time Limit:1000MSMemory Limit:65536KTotal Sub
14、missions:6Accepted:4Description宇航员在太空中迷失了方向，在他的起始位置现在建立一个虚拟xyz坐标系，称为绝对坐标系，宇航员正面的方向为x轴正方向，头顶方向为z轴正方向，则宇航员的初始状态如下图所示：现对六个方向分别标号，x，y，z正方向分别为0，1，2，负方向分别为3，4，5；称它们为绝对方向。宇航员在宇宙中只沿着与绝对坐标系xyz轴平行的方向行走，但是他不知道自己当前绝对坐标和自己面向的绝对方向。任务描述：请根据宇航员对自己在相对方向上移动的描述确定宇航员最终的绝对坐标和面向的绝对方向。对在相对方向上移动的描述及意义如下：forward x 向前走x米。bac
15、k x先转向后，再走x米。left x 先转向左，再走x米。right x 先转向右，再走x米。up x 先面向上，再走x米。down x 先面向下，再走x米。其中向上和向下如下图所示：Input第一行一个正整数m，表示测试数据的组数。每组测试数据第一行是一个正整数n(1 = n = 10000)表示宇航员行走的次数，下面n行每行输入一次相对行走，格式如上所述，其中( 1 = x = 10000 为正整数)。Output对于每组输入数据输出一行，x y z p, 中间用空格隔开，x y z是宇航员的位置的绝对坐标，p是宇航员面向的绝对方向编号（0=p =5）。Sample Input16lef
16、t 10right 11up 12down 13forward 14back 15Sample Output23 -10 12 3思路：此题是一道模拟题，但是有各种方向需要判断，所以稍微有点繁琐，不过只要耐心，细心慢慢写if,else条件语句，也能很快做出来，代码虽然长点，但是思考的部分不用很多。另外一种方法就是总结些规律，可以把很多类似的代码集成，初始化数组判方向，这样就可以写的很精简了，在比赛中，倒还是推荐前者的方法。参考代码：#include /需要面向方向和头顶方向双决定！#includeint Head,Nova,x,y,z;int Direct63=1,0,0,0,1,0,0,0,
17、1,-1,0,0,0,-1,0,0,0,-1;int Left66=-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;int reverse(int i) return (i+3)%6; void forward(int foot) x+=DirectNova0*foot; y+=DirectNova1*foot; z+=DirectNova2*foot; void back(int foot) Nova=reverse(Nova); forward(foot); void l
18、eft(int foot) Nova=LeftNovaHead; forward(foot); void right(int foot) Nova=reverse(LeftNovaHead); forward(foot); void up(int foot) int temp=Head; Head=reverse(Nova); Nova=temp; forward(foot); void down(int foot) int temp=Nova; Nova=reverse(Head); Head=temp; forward(foot); int main() int test,i,n,foot
19、; char str100; scanf(%d,&test); while(test-) Nova=0; Head=2; x=0; y=0; z=0; scanf(%d,&n); for (i=0;in;i+) scanf(%s,str); scanf(%d,&foot); if (strcmp(str,forward)=0) forward(foot); else if (strcmp(str,back)=0) back(foot); else if (strcmp(str,left)=0) left(foot); else if (strcmp(str,right)=0) right(fo
20、ot); else if (strcmp(str,up)=0) up(foot); else if (strcmp(str,down)=0) down(foot); printf(%d %d %d %dn,x,y,z,Nova); return 0;F：头脑风暴Time Limit:1000MSMemory Limit:65536KTotal Submissions:128Accepted:32DescriptionYNingC是一位数学专业的学生，平时他喜欢玩一些数字，特别是一些趣味的数学问题。正因为如此，很多同学都会把自己遇到的一些有趣的数学问题告诉YNingC，更多的时候是想寻求他的帮助
21、，希望他能解决这些关于数学和数字的问题。可是最近由于繁忙的学业和一些课外活动，使得有时候YNingC同学没有时间帮助同学解决问题，可帮助同学一直是YNingC所热爱的，所以他就把遇到的问题交给聪明的Programmers，希望你们能用最快的速度帮助他解决这个问题。问题是这样子的，有这么一个数列而现在找到这样的一个j，对任意的k（k从1到n）使得Sjk都为正数，但是这个的j有很多个，现在需要求得有多少个这样的j。Input有多组测试数据。第一行，输入T (1 = T = 30) 表示一共有多少个测试数据。接下来是T组测试数据。每组测试数据的第一行输入n (1 = n = 200,000)，接下来
22、一行是n个数据ai。Output输出一行表示一个数字M，M表示有M个不同的j满足条件。Sample Input251 -1 1 -1 171 1 1 1 1 1 1Sample Output17思路：题目是给定一串a，求有多少个j满足对任意Sjk都是正数。最初的想法就是对j=1的情况，求出所有s0k，并令s00=0，记xj=mins0k|k=i，那么对0in如果有s0iyi+1，且s0is0n+xi，那么答案+。不过显然有更漂亮的做法，因为答案其实就是1的个数减去-1的个数！所以可以写的很简单，比赛中通过的同学基本上都是猜到了这个结论。参考代码：#include#includeusing na
23、mespace std;int a200001;int s200001;int x200001;int y200001;int main() int cas; cincas; while(cas-) int n;scanf(%d,&n); s0=0; for(int i=1;i=1;i-) yi=min(yi+1,si); int ret=0; for(int i=1;i=n;i+) if(si0) ret+; printf(%dn,ret); return 0;G：血战当阳Time Limit:1000MSMemory Limit:65536KTotal Submissions:95Acce
24、pted:7Description血战当阳：长坂，又名长坂坡，当阳市西南郊。相传刘备部将赵云(字子龙)单枪匹马，七次杀进重围，救出甘夫人及幼主刘禅。而新三国志英杰传的这一关就是要消灭这些敌人。此关敌人众多（N 1000），而且我方只有赵云一人，所以本人用了强大的修改器，问你赵云至少需要多少血能消灭光这些敌人，而自己不死。所谓一回合是这样的：敌人回合，所有存活的敌人对我方某人攻击，我方减血。我方回合，所有存活的我方人员对敌人某人攻击，敌方减血。敌方每个人都有一个血量Hi，当血量=0时，判为死亡，从战场消失。赵云一次攻击可以造成某个敌人减少Di。Input第一行一个整数N，表示有N个敌人。接下来有
25、N行，每行三个整数，第i+1行表示第i个敌人的血量Hi，受到赵云攻击时减少的血量Di，以及他能对赵云造成血量Fi的伤害。（i=1,2,3.N）Output一个整数一行，表示赵云至少需要多少血能消灭光这些敌人，而自己不死。（答案int内）Sample Input25 1 13 1 1Sample Output12Hint解释：前三回合敌人两个都对赵云造成伤害，赵云都杀第二个敌兵，第三回合结束杀死第二个敌兵，每回合受到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。所以，如果T0（即xi*yjxj*yi，即xi/yixj/yj），先杀i,否则先杀j。所以核心的部分仅仅是个排序。参考代码：#include
