7
8
2017
0

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大佬把图的邻接矩阵都读出来了,剩下的就很傻逼了

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

Category: 未分类 | Tags: | Read Count: 110

登录 *


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