百度之星Astar2012程序设计大赛初赛试题及参考答案.doc

《百度之星Astar2012程序设计大赛初赛试题及参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、百度之星Astar2012程序设计大赛初赛试题13/13百度之星Astar2012程序设计大赛初赛试题（第一场）————及B题答案比赛说明百度之星初赛：2012年6月2日、6月3日10：00Am～12：00Pm本次大赛的初赛的初赛采取在线答题、编译，离线判题的形式，选手报名后，可以在6月2日、6月3日任选一天参加比赛，也可选择两场都参加。针对每题，交题后，系统将给出程序编译是否正确的结果，但不会给出程序是否通过全部测试数据的评价；当场比赛结束后，所有选手的针对每题所写的程序将被离线评判，每题根据程序通过测试数据的数目计算得分。每场初赛根据单场

2、所有题目总分计算成绩，选出当场成绩在前400名的选手进入复赛（第一场已经进入复赛的选手参加第二场比赛如果再次晋级，将被不在第二场参与排名）。2012年6月2日，2012百度之星Astar2012程序设计大赛初赛打开大幕。这里提供了初赛第一场的题目，供有未进初赛和其它有兴趣的朋友研究。初赛第一场共4题。分别是度度熊就是要第一个出场、小小度刷礼品、集合的交与并、轮子上的度度熊。目录比赛说明·······················1·A：度度熊就是要第一个出场··············2·B：小小度刷礼品··················

3、·5·C：集合的交与并····················6·D：轮子上的度度熊···················6·百度之星Astar2012程序设计大赛初赛试题13/13A：度度熊就是要第一个出场题目描述Baidu年会安排了一场时装秀节目。N名员工将依次身穿盛装上台表演。表演的顺序是通过一种“画线”抽签的方式决定的。首先，员工们在一张白纸上画下N条平行的竖线。在竖线的上方从左到右依次写下1至N代表员工的编号；在竖线的下方也从左到右依次写下1至N代表出场表演的次序。接着，员工们随意在两条相邻的竖线间添加垂直于竖线的横线段。百度之星A

4、star2012程序设计大赛初赛试题13/13最后，每位员工的出场顺序是按如下规则决定的：每位员工从自己的编号开始用手指沿竖线向下划，每当遇到横线就沿横线移动到相邻的竖线上去，直到手指到达竖线下方的出场次序编号。这时手指指向的编号就是该员工的出场次序。例如在下图的例子中，度度熊将第二名出场，第一名出场的是员工4。员工在画横线时，会避免在同一位置重复画线，并且避免两条相邻的横线连在一起。即下图所示的情况是不会出现的：百度之星Astar2012程序设计大赛初赛试题13/13给定一种画线的方案，员工编号为K的度度熊想知道自己是不是第一位出场表演的。

5、如果不是，度度熊想知道自己能不能通过增加一条横线段来使得自己变成第一位出场表演。输入为了描述方便，我们规定写有员工编号的方向是y轴正方向（即上文中的竖线上方），写有出场次序的方向是y轴负方向（即上文中的竖线下方）。竖线沿x轴方向（即上文中从左到右）依次编号1至N。于是，每条横线的位置都可以由一个三元组确定，其中xl,xr是横线左右两个端点所在竖线的编号，y是横线的高度。输入第一行是一个整数T(T<=50)，代表测试数据的组数。每组数据的第一行包含三个整数N,M,K(1<=N<=100,0<=M<=1000,1<=K<=N)，

6、分别代表参与表演的员工人数、画下的横线数目以及度度熊的员工编号。每组数据的第2~M+1行每行包含3个整数,xl,xr,y,(1<=xl

7、tar2012程序设计大赛初赛试题13/13样例输入2463121124126232235344403样例输出YesNo#include#include#include#includeusingnamespacestd;structnode{intl,r,y;}line[1010];structnode1{intt,b,pos;}a[1010],b[1010];boolcmp(nodea,nodeb){returna.y>b.y;}boolcmp1(nodea,n

8、odeb){returna.y