CodeForces Round#349 Div.2

A.Pouring Rain

设第x秒会喝完,每秒会增加e\;cm,减少\frac{v}{r^{2}\pi}\;cm,原来相差h\;cm,这就是个追击问题,容易得到方程

(\frac{v}{r^{2}\pi}-e)\times\;x=h

解之即可

B.Coat of Anticubism

考虑题目给出的性质:“初始数据保证一定不能组成凸多边形”

结论:先对原数组排序,然后答案为

a[n]-\sum_{i=1}^{n-1}a[i]\;+1

证明:

显然答案满足对原数据进行分组以后,最大<最小+次小+x

而根据题目的初始性质,最大的数大于其他所有数之和

也就意味着分组一定会把除了最大的数以外的其他数分为两组,不妨把这两组合并

那么也就等价于除了最大数的所有数之和\leq最大

而为了凑成三角形,最优做法就是取最大的数-其余数之和+1

故得证

C.Reberland Linguistics

实质上问题是转化为suffix_{i}是否可以被完美切除

那么考虑动态规划,设f(i) 表示第i个点往后切2个是否符合题意

g(i)则表示切三个

\left\{\begin{matrix}f(i)\;=\;f(i+2)|g(i+2)\;\;\;\;(str[i->i+1]\neq str[i+2->i+3]) & \\g(i)\;=\;g(i+3)|f(i+3)\;\;\;\;(str[i->i+2]\neq str[i+3->i+5])&\end{matrix}\right.

时间复杂度O(3n)

D.World Tour

由于题目给的是边长为1的有向图,那么求任意点对之间的最短路d(x,y)可以用bfs,时间复杂度O(n(n+m))

考虑到枚举四个点会超时,但是我们实际上只需要枚举中间两个点即可

O(n^{2})的时间预处理出某个点到其他点中距离最远的3个点,记为f(x)

再用同样的方法,预处理出其他点到某个点距离最远的3个点,记为g(x)

假设枚举的中间点为x,y,那么答案就是f(x)+d(x,y)+g(y)

时间复杂度O(9*n^{2})

E.Chain Reaction

大枚举,这个坑以后再填。。

反思

(1)不要在一题上吊死

(2)理清逻辑线再写

(3)英语很重要

(4)草稿纸很重要

(5)想出来的算法不要立刻写,要先对样例模拟,思考有没有没考虑的情况,三思而后码

彻底掉绿了wori...21

CodeForces Round#349 Div.2》上有1条评论

  1. Pingback引用通告: CF红名计划 | MedalPluS

发表评论