百度之星初赛题目.docx
- 文档编号:15374900
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:16
- 大小:41.24KB
百度之星初赛题目.docx
《百度之星初赛题目.docx》由会员分享,可在线阅读,更多相关《百度之星初赛题目.docx(16页珍藏版)》请在冰点文库上搜索。
XX之星初赛题目
初赛第一场
A:
度度熊就是要第一个出场
∙查看
∙提交
∙提交记录
时间限制:
1000ms
内存限制:
65536kB
描述
Baidu年会安排了一场时装秀节目。
N名员工将依次身穿盛装上台表演。
表演的顺序是通过一种“画线”抽签的方式决定的。
首先,员工们在一张白纸上画下N条平行的竖线。
在竖线的上方从左到右依次写下1至N代表员工的编号;在竖线的下方也从左到右依次写下1至N代表出场表演的次序。
接着,员工们随意在两条相邻的竖线间添加垂直于竖线的横线段。
最后,每位员工的出场顺序是按如下规则决定的:
每位员工从自己的编号开始用手指沿竖线向下划,每当遇到横线就沿横线移动到相邻的竖线上去,直到手指到达竖线下方的出场次序编号。
这时手指指向的编号就是该员工的出场次序。
例如在下图的例子中,度度熊将第二名出场,第一名出场的是员工4。
员工在画横线时,会避免在同一位置重复画线,并且避免两条相邻的横线连在一起。
即下图所示的情况是不会出现的:
给定一种画线的方案,员工编号为K的度度熊想知道自己是不是第一位出场表演的。
如果不是,度度熊想知道自己能不能通过增加一条横线段来使得自己变成第一位出场表演。
输入
为了描述方便,我们规定写有员工编号的方向是y轴正方向(即上文中的竖线上方),写有出场次序的方向是y轴负方向(即上文中的竖线下方)。
竖线沿x轴方向(即上文中从左到右)依次编号1至N。
于是,每条横线的位置都可以由一个三元组确定,其中xl,xr是横线左右两个端点所在竖线的编号,y是横线的高度。
输入第一行是一个整数T(T<=50),代表测试数据的组数。
每组数据的第一行包含三个整数N,M,K(1<=N<=100,0<=M<=1000,1<=K<=N),分别代表参与表演的员工人数、画下的横线数目以及度度熊的员工编号。
每组数据的第2-M+1行每行包含3个整数,xl,xr,y,(1<=xl 输出 对于每组数据输出一行Yes或者No,表示度度熊能否通过增加一条横线段来使得自己变成第一位出场表演。 如果度度熊已经是第一位出场表演,也输出Yes。 注意,尽管输入数据中员工画的横线高度都是整数,但是度度熊可以在任意实数高度画横线。 此外,度度熊和员工一样,在画横线时需要避免在同一位置重复画线,也要避免两条相邻的横线连在一起。 样例输入 2 463 121 124 126 232 235 344 403 样例输出 Yes No B: 小小度刷礼品 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 65536kB 描述 一年一度的XX之星又开始了,这次参赛人数创下了吉尼斯世界纪录,于是XX之星决定奖励一部分人: 所有资格赛提交ID以x结尾的参赛选手将得到精美礼品一份。 小小度同学非常想得到这份礼品,于是他就连续狂交了很多次,提交ID从a连续到b,他想问问你他能得到多少份礼品,你能帮帮他吗? 输入 第一行一个正整数T表示数据组数; 接下来T行,每行三个不含多余前置零的整数x,a,b(0<=x<=10^18,1<=a,b<=10^18,a<=b) 输出 T行,每行为对应的数据情况下,小小度得到的礼品数 样例输入 1 888888888888888 样例输出 1 C: 集合的交与并 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 65536kB 描述 对于一个闭区间集合{A1,A2……AK}(K>1,Ai<>Aj{i<>j}),我们定义其权值 W=|A1∪A2∪……∪AK|*|A1∩A2∩……AK| 其中|X|表示X区间的长度;如果X为空集|X|=0。 当然,如果这些闭区间没有交集则权值为0。 给定N个各不相同的闭区间,请你从中找出若干个(至少2个)区间使其权值最大。 输入 第一行一个整数N(2<=N<=10^5) 接下来N行每行两个整数lr(1<=l<=r<=10^6),表示闭区间的两个端点。 输出 最大权值 样例输入 4 16 48 27 35 样例输出 24 D: 轮子上的度度熊 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 65536kB 描述 XX楼下有一块很大很大的广场。 广场上有很多轮滑爱好者,每天轮滑爱好者们都会在广场上做一种叫做平地花式轮滑的表演。 度度熊也想像他们一样在轮上飞舞,所以也天天和他们练习。 因为度度熊的天赋,一下就学会了好多动作。 但他觉得只是单独的做动作很没意思,动作的组合才更有欣赏性。 平地花式轮滑(简称平花),是穿轮滑鞋在固定数量的标准桩距间做无跳起动作的各式连续滑行。 度度熊表演的舞台上总共有N个桩,而他也从自己会的动作中挑出M最好看的。 但事情并没有这么简单。 首先每个动作因为复杂度不同,所以经过的桩的个数也不尽相同。 然后,为了保持连贯性,有些动作是接不起来的,所以每个动作都有他前面能接的一个动作的列表。 更有甚者,有的动作要考虑前两个动作才能确定是否能做出来。 因此动作被分为三类: 0型动作,无论前面是什么动作都能做出来,所以这种动作也能作为起始动作;1型动作,要考虑前面那个动作才能确定是否能接上;2型动作,要考虑前面两个动作才能确定是否能接上。 最后,评分也很复杂。 每个动作有个单独得分,只要在表演过程中做了这个动作就能获得这个分数。 有些动作的组合也非常好看,也会有相应的得分。 不过要获得某个组合的得分就要在过程中完成这组组合中所有的动作,但是,这些动作既不要求按顺序完成也不要求连续完成。 当然,大家不喜欢重复的动作,所以同一个动作和同一个组合不会获得两次得分。 举个例子,总共有10个桩,有以下几个动作: 动作1: 0型,需要3个桩,得分5。 动作2: 0型,需要4个桩,得分4。 动作3: 1型,能接在动作1或者动作2后面,需要6个桩,得分10。 动作4: 2型,要接在动作2+动作1后面,需要4个桩,得分30。 组合1: (动作1,动作2,动作4),得分15。 组合2: (动作1,动作3),得分10。 组合3: (动作2,动作3),得分5。 能配成的方案不少,但有这么几种方案是不行的: 1.动作2+动作1+动作4,虽然,动作4分数很多,而且1,2,4的组合还能额外获得15分。 但是,这个方案总共要用4+3+4=11个桩,超过了总桩数,所以不行。 2.动作1+动作3,同样也完成了一个组合,也满足各个动作要求的限定条件。 但是做完后,只过了9个桩,没有完成整个表演。 这样度度熊会很尴尬的。 所以这样的方案也不行。 最优方案应该是动作2+动作3,满足桩数要求,也满足各个动作前置限定条件。 最后得分: 单项动作14分+组合加分5分=19分。 虽然,度度熊一下就算出来自己应该怎么表演了。 但是他还是想考考精通编程的你。 输入 一开始一个整数T(1<=T<=5),表示有T组数据,每个数据如下格式: 第一行有三个整数,N,M,P。 分别表示桩数、动作数和组合数。 第二行M个0~2的整数,表示每个动作的类型。 第三行M个整数,表示每个动作需要使用的桩数。 第四行M个整数,表示每个动作单项的分数。 接下来P行,每行描述一个组合。 每行的前两个数X,Y,X表示组合中总共有X个动作,Y表示组合能获得的分数。 后面接X个数,表示组合中包含的X个动作的编号。 再接下来分为M块,第i块描述第i个动作的前置条件。 若第i个动作是0型的,那么它没有前置条件。 所以对应的块是一个空行。 若第i个动作是1型的,对应的块是一个M的01序列。 若这个序列是Aj的话,Aj=1表示动作i可以接在动作j后面。 若第i个动作是2型的,对应的块是一个MxM的01矩阵。 若这个序列是Aj,k的话,Aj,k=1表示动作i可以接在动作j+动作k后面。 输出 对于每个数据,输出包含一个整数,表示度度熊能获得的最高分数。 样例输入 1 1043 0012 3464 541030 315124 21013 2523 1100 0000 1000 0000 0000 样例输出 19 提示 保证至少有一个方案满足要求。 对于100%的数据,1≤N≤100,1≤M≤10,所有分数之和在32位有符号整数范围之内。 每个动作至少需要过1个桩。 初赛第二场 A: 度度熊就是要刷排名第一 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 65536kB 描述 一天度度熊在Baidu游戏大厅中发现了一个隐藏的神奇游戏,叫做”度度熊的逆袭”。 度度熊很好奇到底是什么情况,于是就进入了游戏。 这个游戏很神奇,游戏会给出n个数Ai,度度熊可以任意从中选取一些数,一个数可以选任意多次。 选好之后度度熊得到的分数为度度熊选出的数的Xor(异或)值。 度度熊顿时产生了兴趣,决心要刷至Ranklist的第一名。 但是度度熊犯难了,度度熊不知道自己给出的方案是不是最好的,于是度度熊找到了你,希望你告诉他对于某个回合,度度熊能得到的最高分和第二高分是多少? 输入 第1行1个数n,接下来1行n个整数表示Ai,(0<=Ai<2^31,并且 ) 1<=n<=10^5 输出 输出一行两个数,表示度度熊能够得到的最高分和第二高分为多少 样例输入 2 53 样例输出 65 B: 网页聚类 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 65536kB 描述 有N(N<=1000)个网页, 我们想按照它们的相似度或差异度,把它们聚成K(2<=K<=N)个类。 每个网页都具有一些属性,简单起见我们认为每个网页只有三个属性: x、y、z。 归一化之后,这三个属性的取值范围都是[0,1]。 两个网页i、j的差异度如下定义: s(i,j)=(x_j-x_i)^2+(y_j-y_i)^2+(z_j-z_i)^2。 请求出最大的t,每个类至少包含一个网页,并且其中任意两个位于不同类中的网页的差异度都至少为t。 输入 第一行包含两个整数N和K,后面N行每行三个实数,分别为x、y、z 输出 最大的t的值,使用四舍五入在小数点后保留六位小数。 样例输入 53 0.10.20.4 0.20.80.7 0.30.40.5 0.00.50.0 0.30.30.2 样例输出 0.170000 C: 度度熊的礼物 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 65536kB 描述 度度熊拥有一个自己的Baidu空间,度度熊时不时会给空间朋友赠送礼物,以增加度度熊与朋友之间的友谊值。 度度熊在偶然的机会下得到了两种超级礼物,于是决定给每位朋友赠送一件超级礼物。 不同类型的朋友在收到不同的礼物所能达到的开心值是不一样的。 开心值衡量标准是这样的: 每种超级礼物都拥有两个属性(A,B),每个朋友也有两种属性(X,Y),如果该朋友收到这个超级礼物,则这个朋友得到的开心值为A*X+B*Y。 由于拥有超级礼物的个数限制,度度熊很好奇如何分配这些超级礼物,才能使好友的开心值总和最大呢? 输入 第一行n表示度度熊的好友个数。 接下来n行每行两个整数表示度度熊好朋友的两种属性值Xi,Yi。 接下来2行,每行三个整数ki,Ai,Bi,表示度度熊拥有第i种超级礼物的个数以及两个属性值。 1<=n<=1000,0<=Xi,Yi,Ai,Bi<=1000,0<=ki<=n,保证k1+k2>=n 输出 输出一行一个值表示好友开心值总和的最大值 样例输入 4 36 74 15 24 334 343 样例输出 118 提示 送给第一种礼物的人有1,3,4,送给第二种礼物的人有2 D: 小王子的表演 ∙查看 ∙提交 ∙提交记录 时间限制: 1000ms 内存限制: 262144kB 描述 为了庆祝女王的生日,王宫前的广场上正举行着一场神枪手的表演赛。 这些神枪手中包括军队里的射击天才,山中的顶级猎人,异国的神奇牛仔……来自五湖四海的高手汇聚一堂。 在比赛中技压群雄的人,不仅仅能给女王的生日添上华丽的祝福,还能够获得无上的荣誉。 比赛的规则很简单。 场中存在着N个靶子,每个枪手允许在场内任何一点向任意方向射击一次,穿透最多靶子数目的枪手就是胜利者。 从广场的平面图来看,每个靶子都可以被认为是一个点,并且第i个靶子的运动轨迹是以点(xi,yi)为起点,点(xi+ai,yi+bi)为终点的线段。 发令枪响的那一刻,每个靶子同时从起点到终点开始匀速运动。 虽然靶子各自的速度不尽相同,但是所有的靶子将会在10秒后同时到达终点,选手必须在这10秒之内(包含开始和结束的瞬间)进行射击。 子弹的速度可以认为是无穷大并且射击场没有边界。 小王子偷偷地也报名参加的这次比赛,希望能在母亲的生日上表现出自己的成长。 聪明的小王子早就通过观察把所有靶子的运动情况强记在心,那么,小王子最完美的射击究竟能够穿透多少靶子呢? 输入 第一行只有一个整数,N,(1<=N<=50) 之后每一行包含4个整数,xi,yi,ai,bi,分别表示第i的靶子运动轨迹的起点(xi,yi),以及方向(ai,bi),假设这些整数的绝对值都不大于1000。 输出 只需要输出一个整数,表示最优情况下小王子一发子弹能够击穿的靶子数目 样例输入 9 -14-1460 -12-1402 -10-120-2 -12-1220 -14-1406 -8-1406 -8-8-60 -13-1112 -9-11-12 样例输出 4 提示 两个靶子可能会在某些时刻重叠在一起,此时它们不会发生碰撞而是沿着各自的轨迹继续运动下去。 数据中没有两个运动完全相同的靶子。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 百度 初赛 题目