Codeforces Round #253 (Div. 1)

扯点别的。。
终于过山了。。
"以前我爬山都tm不叫爬山啊。。叫走楼梯!"——小学死党。
最近带小学死党游杭州。。
把他带去爬山。。尝试了一下野路。。。
一开始是小路。。后面路都没了。。都是荆棘。。
各种攀岩。。
加上下雨。。泥土湿滑。。
两人四脚着地地往上攀。。。
感觉手脚并用才tm叫爬山啊!
爬到山腰还没有看到正常的石板路。。有种迷路在深山的感觉。。
幸好最后爬到正道上了。。
不然就是荒野求生了
这种经历真是一生难忘啊。。再也不想要第二次的那种一生难忘


situation

没正式参加。。就不说了

sol

A

没看

B

没看

C

看了没写。。。
我看懂的题意是,一次可以删连续的一段数。。然后调整出一次只删一个数一定比删多个优,所以就变成一次只删一个数的问题了。。
(啥,你说原题意就是一次只删一个?)
然后稍微yy一下,就能在直觉上感受到。。如果有一个凹陷:a[i]<=a[i+1],a[i]<=a[i-1],那么a[i]先于a[i+1],a[i-1]被删一定不会更差。。
这样就能做了。。
把凹陷都消去。。就变成单调的。就一眼了。
反正都是一眼猜想流

D

少见的我会做的D。
首先这是一道语文题。。
题目里面给的染色要求:
如果点u相邻边有边染色成了c,v也有。。那么(u,v)路径上一定要有一条边是颜色c。
这一点其实就是说如果把这棵树所有非颜色c的边删掉,得到的森林,除了点数为1的联通块之外,就只能有1个大小大于1的连通块。。(自己感受一下吧)。。
然后还有一个要求就是一个点相邻的边,最多只有两条染成同一颜色。。
那么就说明同一颜色的边组成了一条链。。

然后这题就转化成了。。
给这棵树弄一个链剖分。。
最小化 一个点到根经过的链数的最大值
显然答案是logn以内的。。
考虑静态版本,显然可以直接树形dp做到O(n)。

然后动态加叶子的话。。直接暴力改这个叶子的祖先dp值。。
因为dp值每次被改肯定是改到更大。而每个子树的dp值的上界是O(lgn)(树链剖分可以做到O(lgn))
所以最终这棵树所有dp值的和不超过O(nlgn),所以修改祖先dp值最多发生O(nlgn)次。。
所以暴力上就是O(nlgn)了。。

E

其实不算比较难的E了。。
(好像卡了暴力不random_shuffle的?)

这个不难看出答案可以二分。。
二分ans之后,转化为判断是否存在一个半径为ans的圆,里面最多包含一个给定的点,并且圆心在矩形内。
假设存在这样一个圆,边界上没有给定的点的话,那么我们可以通过平移来让它边界上有给定的点。
所以二分ans之后,我们枚举哪个点会在边界上。
以每个给定的点,作一个半径为ans的圆。。
假设我们枚举i号点会在边界上。
那么其它圆与它相交,会交出一些圆弧。。将圆弧离散化之后,如果一段圆弧被覆盖不超过一次,那么圆心放在这段圆弧上就是可行的,那么就存在这样的圆了。。
否则就答案小于这个ans了。。

这样我们每次判定的时间是O(n^2lgn)。。而且要乘以二分次数O(lgMaxAns)

反正这些都是很好想的。。。

我没有想到的就是。。通过random_shuffle可以优化一下期望的复杂度来过掉这题。。

大概就是说我们先枚举哪个点会在边界上,然后二分答案,
枚举到第i个点的时候,下界是前i-1个点在边界上时候的答案。。
这样子就能优化期望复杂度了。。
因为random_shuffle之后,第i个点成为前i个中产生最大答案的点的概率是1/i。。算算期望就行了。。
这样就好了。。

Comments

comments powered by Disqus