Codeforces FST 记录

暑假里 VP 了 $O(1)$ 场 CF。现记录如下（大致就是 2014 年底到 2015 年初的）

Codeforces Round #282

A, B 略

C 首先将区间转树，然后 DP。
第二维状态应该是 (现在的最大值 - 初始的最大值)

D 直接从下到上，从上到下分别 DP 出二次和，然后将链和子树合并。（细节咕咕咕）

E 根据题解上的证明（比较复杂，先咕着TODO），每个格子 $(i, j)$ 的 SG 值为 $\min(\text{lowbit}(i), \text{lowbit}(j), \text{highbit}(k))$ （ $\text{highbit}$ 的定义类似 $\text{lowbit}$ ）。所以总的 SG 值为所有 1 的格子的 SG 值的异或。

考虑有几个格子的 SG 值 $\geq x$ （显然 $x \le \text{highbit}(k)$ ）最后差分一下。

那么可以转化成二维区间覆盖 + 数点，用扫描线 + 线段树。

在线段树实现上，用类似标记持久化的思想，不下传标记，根据是否有标记决定是否 update。

另外，因为只需要知道数量的奇偶性，所以可以压位放在一个线段树上搞。

Codeforces Round #283

VP 的时候没什么差错，只是计算几何写翔了。

A 略

B 复杂度分析（O(调和级数)）

C 将区间包含转为二维数点之后贪心。

D 计算几何。利用相对运动来简化判定的形式（不仅要固定一个点，而且要让其中一条边不转）。考虑边界情况，旋转的线段相交可以变成旋转的点（圆）和线段相交。

E 用数位 DP 的思想，逐位递推。矩阵快速幂优化。

Codeforces Round #284

(著名的 dreamoon & sorry_dreamoon 场)

这一场 VP 的时候被榜带错了，直接开 C，结果因为没拆点，直接跑（魔改）匈牙利，WA 了无数发（这样写细节会出事），然后赛后 1 分钟过 B。（其实 D，E 也不难，就是两小时可能写不出来）

A 略

B 概率 DP 卡常题

C 按质因数拆点跑二分图匹配。

D 暴力建线段树，维护 $T \bmod 60$ 下的 DP 值

E 矩阵优化状压 DP。

Goodbye 2014

这场 FST 了一题。因为边界判错了。

A, B, C, D略（居然 A FST 了一发）

E 数据结构优化模拟。（细节 WA 了很多，最后写了 2 个 $\log$ 的）

最后我写的是 range_tree，每次合并的时候要二分出第一个不被撞到的点。

F O(调和级数) + 关键点 / 扫描线 + 双栈队列

前一种很常见，后一种的意思是用两个栈来模拟队列，同时维护 DP 值，这样插入删除都是在可接受范围内的。

G 数论 + 树论神题（详细讲一下最后几步细节的推导, TODO）

Codeforces Round #285

这一场手速不够，而且 C 题因为一个式子打错 FST 了（居然过了 39 个点），D 题算错转二进制的复杂度然后在死命卡 bitset。。。

A, B略

C 大分讨

题解上好像没有分讨，我大致分成了端点跨过中线，端点都在一侧，另外为了防止算重加上了端点在中线上和端点关于中线对称的情况。好像也可以直接 two pointer

D 线性基裸题，高精度转二进制（实际是 $O(\frac{n^2}{w}) 的$ ，必须压位才能过）

E 轻重链剖分 + SA + 在 $\log$ 条链上扫 / 整体二分（主要是为了 $O(n)$ 求出长度为 $\text{mid}$ 的位置）+ hash + 卡常

Codeforces Round #286

这场没有 VP 记录，因为爆零了（A题多了个 $\log$ 然后就死活过不去。。。）

A 缩减状态数（ $n\sqrt{2n}$ 个状态）

B 缩点 + 分析（挺好的题目）

对于一个弱连通分量：

存在SCC：建成环（一开始以为是每个SCC建一个环，实际不需要）
不存在SCC：建成链

只要并查集 + tarjan 判一下。

C 贪心 + 推式子 / 逆向思维（也是挺好的题目）

假设二分答案 $x$

反向推（从高度为 $x$ 出发，每次贪心选择最早会爆负的 $k$ 个加上去，最后的高度要高于初始高度），容易证明正确性。
而如果直接计算出第 $i$ 个操作的最早发生时间 $t_i$ 的时候（即求最小的 $t$ 满足 $\max(0, at - ip) + a(m - t) - (n - i)p \le x$ ），就需要稍微推一下，如果将某些操作提前（但不小于 $t_j$ ）不会影响正确性（因为计算时假设前 $i$ 次操作都在 $t$ 进行，后 $n - i$ 次操作都在最后进行），也就是证明只要在合法时间段内操作，所有操作独立。

D 复杂度分析（按照 $\sqrt{n}$ 分类） + 减少不必要枚举（枚举较少的出边）

E 自动机 DP 上套矩阵（好像可以推式子）

听完毕姥爷讲课，发现可以直接线性递推用 BM(Berlekamp Massey Algorithm) （或者高消）来做。。。A brandly new introduction

再来看最近的一场

Codeforces Round #503

两（3？）题手速场（话说 C 题 pp 比 D 多，把我带去做 C 了。。。最后只剩 7 个没 FST，中间好像还有乱搞）

A，B 略（话说前两天我还看到了 B 的连续版本）

C 递归构造，每次考虑删除一个点和它的出边所到达的点，求出子问题答案后分这个点是否一步可达讨论。（似乎大家都在缩点后乱搞）

D 将 $O(n^2)$ 条线段极角排序，扫描时维护每个点到扫描线的距离关系（带符号），利用两个点的距离大小关系只在扫描线角度和两点连线极角相同是改变维护。 ~~$O(n^3)$ 卡常：CF 机子是 32 位机，所以先求模 $2^{32}$ 意义的值。或者预处理叉积~~

E 边分 + 凸包合并（写点分容易变成 3 个 $\log$ 或者在 $m$ 上多一个 $\log$ ）标算 $O(n \log^2 n + m)$

Let’s continue.

Codeforces Round #290

真好玩，居然最大的数据范围 $n \le 1000$ 。

A 略（写得好长）

B 略（用 std::map 的总状态数上界？表示只会证到 $O(n^2 \sqrt{\max a_i})$ , ~~虽然这肯定是 $O(玄学)$ 的~~）

C 既然 $a_i \ge 2$ ，那就可以奇偶分层建二分图，把容量设成 $2$ 即可。复杂度应该是 $O(n^2 \sqrt{n})$ 的吧。

D ~~挺好玩的计数题~~（还有 $30$ 分钟开始码，最后 $2$ 分钟过前两个样例，来不及测后面的样例就交了，然后第三个样例就爆了，结果漏了个 case）（flag广告: 当时 Hightail 爆了，本来可以 quickly 测样例的）
首先可以把 $\text{size} > 2$ 的点双扔了（但是之后得捡回来，我一开始就漏了这里）
然后对于每一棵树分别求解，最后背包合并。
对于每一棵子树，没有被访问过的结点都连通。假如我们知道了这个集合，剩下结点的排列方案可以 DP 出来。（考虑那个奇怪的操作过程，假如反过来考虑就变成了每次沿着某条边扩展一个结点，可以发现根节点一定是扩展序列的第一个（即原序列的最后一个），且它的子树是独立的，可以直接乘组合数合并。）
这一部分可以计算前面的没访问的集合一起 DP （ $f_{i, j}$ 表示子树 $i$ 内有 $j$ 个点没有访问，其中 $j = 0$ 就是前面讨论的情况， $j > 0$ 时也是个背包）。
为了防止对外侧子树的讨论，可以让枚举每个点为根跑一次 DP，DP 时保证 $j > 0$ 时根结点必须不被访问。那么每个方案被统计 $j$ 次，最后加起来的时候除掉即可。
注意背包的时候要乘上 ${\text{size}_{u} \atop \text{size}_{v_1} \text{size}_{v_2} \ldots \text{size}_{v_n} }$ 。
最后我们要把点双捡回来。对于 $j = 0$ 的情况，若子树 $i$ 内结点与点双结点相连（但是如果 $i$ 是这次枚举的根，则它和点双结点相连不需要统计），则是非法状态， $f_{i, 0} = 0$ 。

复杂度 $O(n^4)$ , 如果把前面的枚举每个点为根变成直接指定根 DP, 应该就是 $O(n^3)$ 的。

E 构造题。~~（题解的转对偶图变成二叉树真神）~~
第一个 comment 道真相。从一个状态变成另一个状态的构造题可以将两个状态都变成一个方便构造的中间状态，然后将后面一个反向。

~~（前面的坑要不不填了）~~

Rockethon 2015

ACM 赛制 + 部分分。再次最后半小时开始 rush 最后没有调完。。。

A 略（想了半天为什么会这么简单。。。）

B 观察合法序列的性质后逐位确定。

C 枚举第二大的值，对应的数，以及第一大的数，剩下推式子。注意处理相等的情况。

D 构造题。首先确定左右子树分界线的取值范围。然后限制就在于整个子树的右边界限制。这个我是用个 DP 来实现的：
记 $f_i$ 为 $i$ 子树的最小右边界， $last_i$ 为由读入给出的 i j 对中 $j$ 的最大值（即边界的一个松的下界），从后向前转移： $f_i = \max_{j = i + 1} ^ {last_i} f_j$ 。
(好像题解说这个也可以在 DFS 的时候顺便求出来，少个 $\log$ )
最后 DFS 一遍最后确定左右子树的分界线。

E 关键性质 $|x| \ge x$ ，所以我们可以暴力枚举绝对值如何打开，而不会丢失最优解。
记 $f_{i, j, \{0, 1\}}$ 表示考虑前 $i$ 位，分了 $j$ 段，第 $j$ 段中 $S_{j - 1}$ 和 $S_j$ 的大小关系。
转移的时候考虑这一位是否作为右端点，并枚举左端点即可。
发现可以前缀 $\max$ 优化。
转移的时候 $j = 1, j = k$ 的情况要特判（我就这里挂了）

F 题意看错好多次。二分答案后建网络流。
直接跑需要常数较为优越。可以利用上次跑的结果（如果上次是 l = mid + 1 的话），在此基础上加边再跑，会快很多 (2300ms $\rightarrow$ 680ms)。

G 可以列出 $O(n^4k)$ 的 DP：
$f_{t, i, j}(i < j)$ 表示在 $t$ 时刻， $a_i > a_j$ 的概率。转移枚举 reverse 的 $l, r$ 。容易把它优化到 $O(n^3k)$ （如只枚举 $l + r$ , 计算贡献次数）。
因为输出小数，可以猜想 $\text{ans}_k$ 是收敛的（不会证）。所以 $k$ 可以与一个常数 $\text{MAXT}$ 取 $\min$ 。（ $O(n^3\min(k, \text{MAXT}))$ ）
也可以优化到 $O(n^2 \min(k, \text{MAXT}))$ （代码中看到有维护二维前缀和的，但是不会。写了个更复杂的），同样分 $4$ 种情况讨论：

对于 $l, r$ 不影响 $(i, j)$ 位置的情况（ $i < l \le r < j$ , $r < i$ 或 $l > j$ ）：直接求出转移次数，乘上去即可。
对于只影响 $i$ 的位置的情况（ $l \le i \le r < j$ ）:
令 $i'$ 为 $i$ 对称后的位置，则 $i + i' = l + r \Rightarrow r = i + i' - l$ , 带入上式得： $0 < l \le i \le i + i’ - l < j $，最后解得：$ \max(i’ + i - j, 0) < l \le \min(k, i)$。然后对两边的 $\min, \max$ 分类讨论：
$\begin{cases} i + i' - j < l \le i, & \max(j - i, i) \le i' < j \\ i + i' - j < l \le i', & j - i < i' \le i \\ 0 < l \le i, & i < i' \le j - i \\ 0 < l \le i'. & 0 < i' \le \min(j - i, i) \end{cases}$
维护 $f_{i,j}$ 以及 $i \times f_{i,j}$ 的前缀和， $O(1)$ 分 4 段转移。
对于只影响 $j$ 的位置的情况（ $i < l \le j \le r \le n$ ）:
同第 2 种计算。
$\max(j, j') \le l < \min(j' + j - i, n + 1) \Rightarrow$
$\begin{cases} j' \le l < n + 1, & \max(j, n + 1 + i - j) \le j' < n + 1 \\ j' \le l < j + j' - i, & j \le j' < n + 1 + i - j \\ j \le l < n + 1, & n + 1 + i - j \le j' < j \\ j \le l < j + j' - i. & i < j' < \min(j, n + 1 + i - j) \\ \end{cases}$
对于 $i, j$ 位置都影响的情况 ( $1 \le l \le i < j \le r \le n$ )：
同样将 $r$ 表示出来，解不等式。注意需要外层按照 $j - i = \Delta$ 枚举, $j' < i'$ 。
$\max(k + j - n) \le l \le \min(k, i) \Rightarrow$
$\begin{cases} j' + j - n \le l \le i, & \max(n - j + 1, i) < j' \le n - \Delta \\ j' + j - n \le l \le k, & n - j + 1 < j' \le i \\ 0 < l \le i, & i < j' \le n - j + 1 \\ 0 < l \le j'. & 0 < k \le \min(n - j + 1, i) \end{cases}$

~~(码得好累，推得好累)~~
~~(我已经不会解不等式了，移项各种不变号，式子推了将近一天才推对)~~

Codeforces Round #292

(又是 dreamoon 和 sorry_dreamoon)

(再次手感极差，感觉在现场赛要 3 题全 FST)

A 略（论如何将 $3!=6$ 变成 $6!=6$ ）

B 从叶子开始删即可判断。（讲个笑话： std::vector <int> v 的清空操作是 v.empty()。。。）

C 拆环后线段树最大子段和。

D Key Observation: 求出来的 d 数组根据大小关系形成了树结构。DSU 解法。

E 类二分图转成两侧分开取 $\max$ 。

Codeforces Round #295

前 1h 一直在卡题

A 略

B 看清题意（不是拓扑排序！）

C 计算每个子段的贡献次数，长度相同的放一起计算，注意特殊处理两端的段。

D （这题被搬过）把赋值变成加，把加变成乘。注意细节。

E （个人感觉比 D 简单）对于每个连通块，建出 DFS 树，如果有一条树边被两条非树边覆盖，那么一定存在解，否则无解（此时图每个点双都是个环，显然无解）。

设两条非树边分别为 $(u_1, v_1), (u_2, v_2) (\text{dep}_{u_i} < \text{dep}_{v_i}, \text{dep}_{u_1} < \text{dep}_{u_2})$ ，设 $l = \text{lca}(v_1, v_2)$ 。则存在三条路径 $u_2 \rightarrow l$ ， $u_2 \rightarrow u_1 \rightarrow v_2 \rightarrow l$ ， $u_2 \rightarrow v_2 \rightarrow l$

~~（假装这是图）~~ (加粗的为树边)

Codeforces Round #296

A 略

B 关注到若 $A < B < C$ 且 AB, BC 连边，则 AC 连边。那么就可以 DP / 贪心做了。

C 又一道 DFS 树好题。先奇点变成偶点，按照树边和非树边（返祖边）讨论，顶点特判即可。

D 毛爷爷论文题。

E std 容斥 + 二维数点。然而被 comment 踩爆。
将三角形表示成 3 个叉积形式，然后叉积存在分配律，将和一条直线相关的点提出来， $O(n)$ 计算。注意要按照严格顺时针或逆时针方向计算。

新近一场，打得很菜。

Codeforces Round #513

A, B, C 略（B 题直接贪心边界各种判错，丢了好多分）

D 贪心，证明从略（居然 pretest 没开 long long 也能过，又丢了些分，然后就爆了）

E 答案为 $\sum \lceil \frac{dist_{u, v}}{2} \rceil$ , 分奇偶 DP。

F 难点在于模型转换。首先可以对每个点分别求解。然后可以搞出来一个 DP：设 $f_{i, j}$ 表示 $i \rightarrow \text{root}$ 的边已经全部删去（且保留了根节点），且 $i$ 子树内已有 $j$ 条边被删去的概率。转移分两步：首先添上连向父亲的边（枚举它被删的时间），然后子树合并（因为删边有序，所以要乘组合数）。

zzy 的模型转化：

H 我看到了两种构造。（首先利用慢速乘的原理构造乘法，注意每个格子初值为 1）

首先构造 $x^d, (x+1)^d, (x+2)^d, \ldots, (x+d)^d$ 。然后二项式定理展开后高消解出构造出 $x^2$ 时每项的系数。然后根据 $xy = \frac{(x+y)^2-x^2-y^2}{2}$ 解。
首先可以得到 $(\sum_{i=1}^n x_i)^k= \sum_{a_i} [\sum a_i=k] \left( { n \atop {a_1 \ a_2 \ a_3 \ \ldots \ a_n} } \right) \prod x_i^{a_i}$ 。令 $n = d$ , 则 $(\sum x_i)^d$ 中有一项为 $d! \prod x_i$ , 令 $x_1 = x, x_2 = y, x_3 = \ldots = x_n = 1$ ，就是答案。那么将其它项容斥掉，对于每个子集 $S \subset \{1, 2, \ldots, n\}$ 计算 $(\sum_{i \in S} x_i)^d$ ，并乘上容斥系数 $(-1)^{n - |S|}$ 即可。因为在每一个式子中对应项的系数相同，所以容斥是正确的。在实现的时候，因为后面全是 $1$ ，所以直接枚举 $x, y, 1$ 的数量，再多乘上一个组合数就行了。

Codeforces Round #516

手速不够，网炸 + 前面不知道在想些什么。

A sort 后就是答案上界

B 根据同一格子向右走减向左走为定值解不等式。最后发现只需要最小化向左走步数。0-1 BFS（听说直接 BFS 能 pp？）

C 在一条直线上倍增。直接搞容易需要 $2^{30}$ 的长度，要么分隔线画斜线，要么将直线转成 L 型。

D （比赛时式子推到一半弃疗）重标号，使得原来的 $[l, r]$ 对应 $[1, L]$ 。设 $[1, L]$ 间 sweet tooth 有 $a$ 个，整个区间有 $b$ 个，共传了完整的 $t$ 轮。分别对 $k, k + 1$ 求解。
列出方程： $(t + 1)(a + L) + t(b - a + n) = k$ ，得 $t(b + n) + a + L = k$ , 发现 $a + L \le b + n$ ，类似取模的形式，则 $t$ 有 $O(\sqrt{n})$ 种取值。
枚举 $t$ , 得 $tb + a = k - tn - L$ , 根据不等式 $0 < (\le) a \le L, a \le b \le n, b - a \le n - L$ 解出 $b$ 的范围，取 $\max$ 。
实现时注意细节。（因为前面不是严格取模，所以 $t = \lfloor \frac{k}{b + n} \rfloor$ 或 $\lfloor \frac{k}{b + n} \rfloor - 1$ ）

E 可以猜想，除了 $a_i = i$ 外，其余答案为 $n - 1$ 。直接构造，将废掉的那一列放在最左侧，稍微规划一下就可以做到 $n - 1$ 行。

F 来自 zzy 的题解

F： $n\sqrt{n}$ 卡常好题
【哈希膜数设小一点，多交几法就好了】

(翻译一下：枚举答案 $ans$ ，则对于一个串，找到它之后是否存在它的子串答案为 $ans - 1$ ，这一步开一个大小为 $MOD$ 的 bitset 来判)

更靠谱的 $O(n \sqrt n)$ 做法：首先枚举答案,
~~SA + LCP (没想过)或者~~维护当前答案下合法的起始位置以及它在 SAM 上对应结点，转移时 $O(1)$ 移动指针得到新串，判断之后有没有它的合法子串即可。

这个思路可以优化到 $O(n \log n)$ ：
记 $f_i$ 为最长串从 $i$ 开始的答案。可以发现 $f_i \le f_{i - 1} + 1$ （否则 $f_{i - 1}$ 会更优）。这样 $f_i$ 可以从 $f_{i - 1} + 1$ 枚举到 $1$ 。这样总枚举量 $O(n)$ 。判定时同样在 SAM 上维护指针，做 DFS 序上的 RMQ。