SanSiroWaltz's Blog

发现还是不适应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] 真·码农题。