百度之星2015初赛#1

正文索引 [隐藏]

超级赛亚ACMer

Problem Description

百小度是一个ACMer,也是一个超级赛亚人,每个ACMer都有一个战斗力,包括百小度。
所谓超级赛亚人的定义,是说如果在对抗中刚好接近极限状态,那就会激发斗志,实力提升。
具体来说,就是百小度现在要接受一些ACMer的挑战了,这些ACMer有n个人,第i个人的战斗力是a[i]。
百小度接下来可以自主安排与这n个ACMer的PK顺序,他要想在PK赛中赢过另外一个ACMer,就必须使得自己的战斗力不小于对方(平局情况他会按照百小度字典上的规则把自己排在第一)。
如果百小度的战斗力大于对方,那么百小度就会轻易获胜,得不到锻炼并且骄傲起来,他以后的战斗力将保持在这个值,再也不会发生改变。
如果百小度的战斗力等于对方,那么百小度在获胜的同时也会感到很吃力,但是这会激发百小度的斗志,使得他刻苦刷题,在下场PK赛之前,战斗力最多提升k点(即可以提升0~k点任意值)。
k是百小度的潜力提升上限,会被给定一个初始值,这个潜力提升上限k在后面的比赛中会下降。
每战胜一个ACMer,这个潜力上限k将减少1(因为超级赛亚人百小度也会感到累),但k最低只会减少到0,即不会出现战斗力下降的情况
。也就是第一次比赛如果激发了百小度的斗志,他能把战斗力提升0~k的任一值,如果第二次比赛继续被激发斗志,他能在第一次提升后的基础上,把战斗力再提升0 max(0,k1),依次类推……
m是百小度的初始战斗力上限,也就是百小度第一次进行PK赛的时候,可以选择0~m的任意一个值作为他的战斗力。
现在希望你编写程序,判断一下百小度是否战胜所有的ACMer。

Input

输入包含多组数据(数据不超过500组)
第一行一个整数T,表示T组数据
对于每组数据,第一行包括三个整数n,m,k(1n104,1m,k108)
第二行包括n个正整数,表示彪形大汉的战斗力(战斗力为不超过1012的正整数)

Output

对于每组数据,先输出一行Case #i: (1iT)
如果百小度能打败所有的ACMer,再输出”why am I so diao?”
否则再输出”madan!”

Sample Input

Sample Output

Hint

第一组样例解释 5个ACMer,初始战斗力选择范围是[0,11],接下来每场战斗力提升上限是3,2,1,0,0,…,0 百小度首先使得自己的初始战斗力为10,打败战斗力为10的第一个ACMer, 然后选择战斗力提升3,变成13,打败战斗力为13的第二个ACMer, 然后选择战斗力提升2,变成15,打败战斗力为15的第三个ACMer, 之后再以任意顺序打败剩下的ACMer

题解

玛雅!Orz 看错题目了、、一开始、我就说怎么觉得看似贪心但是仔细一想有不对、
把所有人拍个序,我们每次贪心的取能取到的最大的能激发潜力的人。

找连续数

Problem Description

小度熊拿到了一个无序的数组,对于这个数组,小度熊想知道是否能找到一个k 的区间,里面的 k 个数字排完序后是连续的。
现在小度熊增加题目难度,他不想知道是否有这样的 k 的区间,而是想知道有几个这样的 k 的区间。

Input

输入包含一组测试数据。
第一行包含两个整数n,m,n代表数组中有多少个数字,m 代表针对于此数组的询问次数,n不会超过10的4次方,m 不会超过1000。第二行包含n个正整数,第 I 个数字代表无序数组的第 I 位上的数字,数字大小不会超过2的31次方。接下来 m 行,每行一个正整数 k,含义详见题目描述,k 的大小不会超过1000。

Output

第一行输”Case #i:”。(由于只有一组样例,只输出”Case #1:”即可)
然后对于每个询问的 k,输出一行包含一个整数,代表数组中满足条件的 k 的大小的区间的数量。

Sample Input

Sample Output

题解

这到题目每个询问暴力枚举区间,前缀和维护区间和,ST表维护区间最小值,然后暴力处理某一区间是否有重复的数,这样每个询问加起来是O(n)的。于是O(NM)就行了!「如果吧ST表当作O(1)。。。」然后区间内无重复的数,且区间和和用最小值计算出来的一样那么就是一个合法的答案。

序列变换

Problem Description

给定序列A={A1,A2,...,An}, 要求改变序列A中的某些元素,形成一个严格单调的序列B(严格单调的定义为:Bi<Bi+1,1i<N)。
我们定义从序列A到序列B变换的代价为cost(A,B)=max(|AiBi|)(1iN)
请求出满足条件的最小代价。
注意,每个元素在变换前后都是整数。

Input

第一行为测试的组数T(1T10).
对于每一组: 第一行为序列A的长度N(1N105),第二行包含N个数,A1,A2,...,An. 序列A中的每个元素的值是正整数且不超过106

Output

对于每一个测试样例,输出两行:
第一行输出:”Case #i:”。i代表第 i 组测试数据。
第二行输出一个正整数,代表满足条件的最小代价。

Sample Input

Sample Output

题解

二分答案,然后我们贪心验证就好、、

KPI

Problem Description

你工作以后, KPI 就是你的全部了. 我开发了一个服务,取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的KPI是由当前管道内请求的重要值的中间值来计算。现在给你服务记录,有时我想知道当前管道内请求的重要值得中间值。

Input

有大约100组数据。
每组数据第一行有一个n(1n10000),代表服务记录数。
接下来有n行,每一行有3种形式 “in x”: 代表重要值为x(0x109)的请求被推进管道。 “out”: 代表服务拉取了管道头部的请求。 “query: 代表我想知道当前管道内请求重要值的中间值. 那就是说,如果当前管道内有m条请求, 我想知道,升序排序后第floor(m/2)+1th 条请求的重要值.
为了让题目简单,所有的x都不同,并且如果管道内没有值,就不会有”out”和”query”操作。

Output

对于每组数据,先输出一行
Case #i: 然后每一次”query”,输出当前管道内重要值的中间值。

Sample Input

Sample Output

题解

评测机一定是开O2了、、、直接Vector就水过去了、、

矩形面积

Problem Description

小度熊有一个桌面,小度熊剪了很多矩形放在桌面上,小度熊想知道能把这些矩形包围起来的面积最小的矩形的面积是多少。

Input

第一行一个正整数 T,代表测试数据组数(1T20),接下来 T 组测试数据。
每组测试数据占若干行,第一行一个正整数 N(1N<≤1000),代表矩形的数量。接下来 N 行,每行 8 个整数x1,y1,x2,y2,x3,y3,x4,y4,代表矩形的四个点坐标,坐标绝对值不会超过10000。

Output

对于每组测试数据,输出两行:
第一行输出”Case #i:”,i 代表第 i 组测试数据。 第二行包含1 个数字,代表面积最小的矩形的面积,结果保留到整数位。

Sample Input

Sample Output

题解

旋转卡壳+凸包!(其实我并不会做 见BZOJ1185