AC. 梦想

frank_c1

Codeforces Round #357 (Div. 2)

发布于2016年06月15日 | 暂无评论 | 1,226阅读 | 比赛经历,生涯框架

本场题目不是很难,但我还是在有些地方发挥得不是很好。

B题暴力题结果想偏了23min才出(之前还有一次部分变量没开long long结果过pretest了QAQ)。C题贪心大模拟结果没有考虑到一个情况WA了一发……还好D题这次终于写出来了似乎拉回来一点。

吐槽一句,真不明白在CF上出大计算几何的意义……作为E题防AK十分有效果。

A. A Good Contest

Codeforces上rating\ge 2400是红名。某次比赛中某人比n个人分数高,给出这些人比赛前后的rating,求有多少人比赛前就是红名,而且比赛后比比赛前的rating高。

1 \le n \le 100

按照题意模拟。

B. Economy Game

求不定方程1234567a + 123456b + 1234c = n是否有非负整数解。

1 \le n \le 10 ^ 9

枚举a,b验证一下即可。

C. Heap Operations

给出有n个操作的操作序列。包括 insert x:将整数x加入堆,getMin x:询问堆中最小值,且答案为x,removeMin:将最小值弹出。

你需要构造一个操作次数最小的操作序列,使得输入序列是它的一个子序列,且需要满足询问答案正确,getMin和removeMin操作时堆中有元素。输入保证存在一个合法的方案使得操作数不超过10 ^ 6

1 \le n \le 10 ^ 5

在getMin和removeMin操作之前将序列调整到合法状态即可。注意考虑全面。

D. Gifts by the List

给定一棵n个点的森林。第i个点有一个喜爱点a_i,保证a_ii的祖先。

要求构造一个序列,对于任意i,满足序列中第一个是i祖先的点就是a_i

1 \le n \le 10 ^ 5

题面太长一开始没看懂题QAQ。

首先树与树之间彼此独立,在序列中的顺序不需要考虑。于是森林问题转化为一棵树的问题。

我们考虑如果有解,我们一定是将点按深度从大到小加入序列。

怎么判断无解呢?我们记录每个点的子树中的点所能达到的深度最小的祖先pre(x),如果存在pre(x)x的严格祖先,问题显然无解。如果对于所有x,都有pre(x)x子树中的点,问题有解。

所有对这棵树DFS一遍即可。

时间复杂度O(n)

E. Runaway to a Shadow

平面上有n个圆,可能相交重叠。初始在(x_0,y_0)点。可以等概率地选择一个方向以速度v作匀速直线运动。如果在T秒内与任意圆相交,我们称这个点逃跑成功了。

求这个点逃跑成功的概率。

1 \le n \le 10 ^ 5

这个概率好像没什么用呢。我们以(x_0,y_0)为圆心作一个半径为vT的圆。

我们可以求所有给定圆与这个圆的交点。将圆周看作线段,那么每个给定圆如果与该圆有交点,就一定覆盖了线段上的一段(可能退化成一点)。所以我们得到了若干条线段。对这些线段求一下并即可。最终的概率就是线段并的长度除以圆周长度。如果这个点本身在某个圆里面,概率就是1。

时间复杂度O(n \log n)

注:感觉这种计算几何的题目口胡起来是不难的,真正打出完整代码有难度啊。

[UPD] 通过ABCD四题,居然rank 39 ,rating增至1983,终于紫名啦,开心!