8
18
2015
2

codeforces补全计划

发现还是不适应tc的画风,还是做点cf题补智商吧。


CF Round 315

[A] 答案不会超过[tex]2000000[/tex],直接暴力即可。

[B] 算出组合数和第二类斯特林数就行。

[C] 很裸的2-SAT,从大到小枚举k,表示前k位和s相同,第k+1位要取大一些,剩下随便取。贪心尽量选最小的,正确性显然。

[D] 考虑任意k+1条直线,肯定要取其中一个交点,直接暴力会超时。注意到如果超过k+1条直线交于一点时,这个点必然要取。当[tex]n>k^2[/tex],假如有解,根据抽屉原理,必然有一个点被超过k+1条直线经过,反复随机化便可找到这一点。

[E] 单调队列[tex]O(NK)[/tex]dp显然,但空间不够把每个状态的前驱都保存下来。注意到如果一个状态的前驱是gap,直接找到上一个gap并取尽量大的值即可。对于不是gap的位置,我们保存它在单调队列的存在时刻,这样我们在求一个状态的前驱时,可以通过二分查找判断当前时刻的单调队列的所求位置是不是gap。空间复杂度[tex]O(N+M)[/tex]。


VK Cup 2015 Finals

[A] 建出trie树后贪心匹配。

[B] 暴力,正确性不会证但一副很靠谱的样子。

[C] 容易证明以某一点为中心至多只会劣于周围的一个点。考虑树分治,每次对重心求出答案,通过求导选择找到那个更优的子树。

[D] 维护两个并查集即可。

[E] 加入两个集合的交集有2个共同元素,那么这两个元素有一条边相连。还剩一些叶子结点,找到包括它的最小的集合,就是它所代表的集合,然后就随便搞了。

[F] sb题。

[G] 就是一个凸包啦。


CF Round 313

[A] 列个方程就出来了。

[B] 判断最小表示法是否相同。

[C] sb容斥。

[D] 用皮克定理算,暴力是[tex]O(N^2)[/tex]的,但因为有些边取到的概率太小,可以忽略不计,所以可以做到[tex]O(KN)[/tex],K取60左右即可。

[E] 一个比较复杂的dp。首先离散化,设f[i][j][k]表示用区间[i,j]的灯,要覆盖完整的一段,左端点小于等于k,右端点最多能取到哪。先枚举k,然后设g[i][j][k]表示区间[i,j]的灯,最左边没覆盖到的是k,最右边能取到哪,这可以用dp得到。有了g数组,f数组也可以很简单的得到。再来一次dp,就可以求出答案了。时间复杂度[tex]O(N^4)[/tex]。


CF Round 310

闻(chou)名(ming)遐(zhao)迩(zhu)的毛子场

[A] 语文题。

[B] sb题。由于我从来都手写堆,所以变成码农题。

[C] 码农题。

[D] 暴力。

[E] 真·码农题。

Category: 未分类 | Tags: | Read Count: 805
Avatar_small
Recursion 说:
2015年8月18日 20:00

我觉得tc除了我什么题都不会做以外画风还是很正常的...


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com