Codeforces#995 题解

Codeforces Round #492 (Div. 1) [Thanks, uDebug!]

A. Tesla AC代码


显然,如果一开始所有车都动不了的话,一定无解。
否则,如果一辆车就在它的车位前面,我们就把它开进去。然后,中间的两排一定出现了至少一个空位。我们可以像这样让所有车一起绕圈,并且在一辆车经过它的车位的时候把它开进去:
→→→↓
↑←←←
$20000$次移动是绰绰有余的。

B. Suit and Tie AC代码


对于整数1 \leq i \leq n定义a_i为两个i中左边一个的位置,b_i为右边一个的位置。答案即为
\sum\limits_{i = 1}^n (b_i - a_i - 1) - \sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n [(a_j - a_i)(a_j - b_i)(b_j - a_i)(b_j - b_i) > 0]
其中,对于逻辑表达式x,当x为真时[x]为1,否则[x]为0。
不难证明这是答案的下界。并且从左往右依次考虑第1, 3, 5, 7 \dots个位置,把对应的人挪到第2, 4, 6, 8 \dots个位置上就能得到一个最优解。

C. Leaving the Bar AC代码


给定三个长度小于等于L向量\vec a, \vec b, \vec c,考虑\vec a, -\vec a, \vec b, -\vec b, \vec c, -\vec c,可以发现这些向量中一定有两个夹角小于等于\frac{\pi}{3}。因此,这两个向量的差的长度也小于等于L。也就是说,给定任意三个长度小于等于L的向量,他们中一定有两个的和或差小于等于L。我们可以把n个向量合并到只剩两个,然后贪心地决定这两个向量是加还是减。这样,最终向量的长度一定不超过\sqrt{2} \times 10^6。以二叉树的形式记录合并的过程,最后就能知道每个向量应该加还是减。

D. Game AC代码


这题是个假题……对剩下的没填的数的数量进行归纳法即可证明,当前状态的答案一定是最终可能取到的所有函数值的平均值。所以O(n)记录平均值就行了。

E. Number Clicker [AC代码]

(http://codeforces.com/contest/995/submission/39741504)


一个典型的双向BFS题。因为逆元的随机性很高,还有很多奇奇怪怪的随机算法能过。

F. Cowmpany Cowmpensation AC代码


显然,答案是一个不超过n次的多项式。所以可以通过DP求出D0 \dots n时的答案,然后插值。

发表评论

电子邮件地址不会被公开。 必填项已用*标注