ipsc2017

剧透预警

这次的题目好像都是中规中矩的题。。具有ipsc特色的题只有几道。。

抱住了周总和zrt的大腿。。

A 使用简单的构造即可

x.x.x.x
.......
x......
.......
x......(odd*odd)

xx.x.x.x
........
x.......
........
x.......(even*odd)

.x.x.x.x
x.......
........
x.......(even*even)

第一次flood之后第一行和第一列都占满，之后可以慢慢吞噬整个网格。

用初中数竞可以证明其最优性。具体证明就是方格块的总周长不会变大，所以初始周长至少是$2(r+c)$。

B 开始的时候就想到了B1的构造，但是边界情况太多就没写了。。最后10min rush了一波但是失败了。。

C 周总做的。周总C2被卡精度了。

D 周总做的。周总太强啦

E 简单数据结构。由于卡空间最好用平衡树。

所谓土的面积其实就是有多少个点的高度被改变了。

一个点高度改变只会引起一段区间的高度改变。如何求这段区间呢，以增高点$p$的高度，求$p$左端连续多少个点需要增高为例。如果增高前有$h_{p-l}+l=h_p$，那么显然$p-l$这个点也要增高。这样我们维护一个“区间加法单点求和”的结构，每次二分这个最小的$p-l$即可。

“区间加法单点求和”如果用动态开节点的线段树做，空间复杂度是$O(n\log n)$的，不太好。于是我们把问题变成“单点修改求前缀和”并且用平衡树存下所有修改过的点即可做到$O(n)$的空间复杂度。

复杂度$O(\log^2 n)$一次询问。我知道可以做的更好但是懒得写→_→

F easy：暴力模拟，轮数是$O(c^2)$的但是我不会证。

G 问题是：一个有向图每个点的出度不超过$1$，支持加删边并维护可达性。

显然每个弱连通分量都是一个环套树，所以显然可以用LCT做。呃话说我真的一年没有写过LCT和平衡树了。。

数据结构长这样：一个LCT维护一堆有根树(不能xjb换根但是不影响)，每个有根树的根维护其出边(如果有)，树根的出边称作环边(因为加入这条边$s\to t$的时候$s$已经是$t$的祖先了)。

删除一个点$a$的出边的时候，如果这条边是环边那么直接删即可；否则(是树边)需要寻找删边之前$a$的根的环边，并判断$a$是否在环上。如果在环上，删边之后需要把环边加入树中并确定这棵树的新根；否则$a$所在的树会断裂成两棵。

加入一条边$a\to b$的时候，如果$a$有出边(在LCT中可以判)，那么需要删掉$a$的出边，方法如上。然后需要判断$b$能否到达$a$(或判断$a$是不是所在树的根)，如果能的话这条边就是环边；否则就是树边。环边直接加，树边在LCT中操作一下就好。

(其实也不是很难写但是需要代码手想清楚。

H 队友做的。。看上去是不难的构造

I 将图缩点(强连通分量)，剩下的图中找出所有$1$到$n$的必经点，这些必经点中大小为$1$(即，强连通分量的大小为$1$)且无自环的点就是答案。

J 我只会做easy(滑稽

K 好像是zrt做的?听说是100b水题?

L 没看。。

M zrt大佬把图的邻接矩阵都读出来了，剩下的就很傻逼了

至于读图呢我嘴巴一下。。图都长得中规中矩(没有各种混淆啥的)，所以对每条边，读一个像素就可以知道这条边是否存在。