百度之星初赛题目.doc

6月2日第一场
A:度度熊就是要第一个出场
时间限制:
1000ms
内存限制:
65536kB
描述
“画线”抽签的方式决定的.
首先,;在竖线的下方也从左到右依次写下1至N代表出场表演的次序.
接着,员工们随意在两条相邻的竖线间添加垂直于竖线的横线段.
最后,每位员工的出场顺序是按如下规则决定的:每位员工从自己的编号开始用手指沿竖线向下划,每当遇到横线就沿横线移动到相邻的竖线上去,直到手指到达竖线下方的出场次序编号
.,度度熊将第二名出场,第一名出场的是员工4.
员工在画横线时,会避免在同一位置重复画线,:
给定一种画线的方案,,度度熊想知道自己能不能通过增加一条横线段来使得自己变成第一位出场表演.
输入
为了描述方便,我们规定写有员工编号的方向是y轴正方向(即上文中的竖线上方),写有出场次序的方向是y轴负方向(即上文中的竖线下方).竖线沿x轴方向(即上文中从左到右),每条横线的位置都可以由一个三元组确定,其中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 < N, xr = xl + 1, 0 <= y <= 1,000,000),描述了一条横线的位置
.
输出
对于每组数据输出一行Yes或者No,,,尽管输入数据中员工画的横线高度都是整数,,度度熊和员工一样,在画横线时需要避免在同一位置重复画线,也要避免两条相邻的横线连在一起.
样例输入
2
4 6 3
1 2 1
1 2 4
1 2 6
2 3 2
2 3 5
3 4 4
4 0 3
样例输出
Yes
No
B:小小度刷礼品
时间限制:
1000ms
内存限制:
65536kB
描述
一年一度的百度之星又开始了,这次参赛人数创下了吉尼斯世界纪录,于是百度之星决定奖励一部分人:所有资格赛提交ID以x结尾的参赛选手将得到精美礼品一份.
小小度同学非常想得到这份礼品,于是他就连续狂交了很多次,提交ID从a连续到b,他想问问你他能得到多少份礼品,你能帮帮他吗?
输入
第一行一个正整数T表示数据组数;
接下来T行,每行三个不含多余前置零的整数x,a,b (0 <=x <= 10^18, 1 <= a,b <= 10^18,a <= b)
输出
T行,每行为对应的数据情况下,小小度得到的礼品数
样例输入
1
88888 88888 88888
样例输出
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行每行两个整数 l r(1 <= l <= r <= 10^6),表示闭区间的两个端点.
输出
最大权值
样例输入
4
1 6
4 8
2 7
3 5
样例输出
24
D:轮子上的度度熊
时间限制:
1000ms
内存限制:
65536kB
描述
,,所以也天天和他们练****br/>因为度度熊的天赋,,动作的组合