edu112

Links

A

憨憨题,6,8,10的性价比都一样,奇数铁不行,只能用偶数。

偶数就直接除2。随便组合就行。特判 2,4即可。


B

憨憨题,发现直接沿着 x 轴,y 轴平移即可。

新的矩形只能放在四角,判一判平移会不会出界即可。


C

憨憨题,Alice只能选择一个 \((1,y)\) 向下走到 \((2,y)\)

所以 Bob 能走的是 \(\max(suf_{y+1},pre_{y-1})\)

模拟即可。


D

憨憨题,发现因为字符集大小为 3,合法串只可能长成 \(\texttt{abcabcabc}\cdots\texttt{abc}\) 的样子,所以直接就枚举字符集全排列,判一判就好了。

前缀和模拟即可,复杂度 \(\mathcal{O(6n)}\)


E

发现这个1与n联通等价于把选出的 segment +1,看是不是全大于0.

然后最大减最小尽可能小?

我会 binary search 发现 \(m\leq 10^6\) 好像不大行。

那我会 two pointers!​

先按 \(w\) 排序,显然,枚举右端点,看此时合法到哪里,移动左端点。

正确性显然。

复杂度:\(\mathcal{O(n\log m)}\)

憨憨题考试都做不对,呜呜呜


F

憨憨DS,睡了一觉就会了。(其实考试时都没看到,充分说明自己菜)

如何快速看一个边合不合法?

如果存在套环的情况,考虑对于对于环 \(c_1,c_2\)

一个最大的边的子集 \(s\)​​ ,如果\(s\subset c_1,s\subset c_2\)​。那么 \(c_1,c_2\)​​ 的异或都为一,并且\(c_1\)​​ 并 \(c_2\)​​ 去除 \(s\)​​ 的简单回路异或就为 \(0\) 不合法。

所以不可能存在套环的情况。

这就提示我们这玩意是个边仙人掌。

直接考虑树。

如果是一条连接一颗树上的两个节点的边,那么首先判断是否路径上的边都不在任意一个连通块内。

然后再看新形成的一个环的 \(\texttt{xor}\) 是否为1。

如果是一条连接两个连通块的边,一定行。

LCT (le ci te) 不好写,嘤嘤嘤。

离线把最终的树建出,考虑对树的形态产生影响的边只有连接连通块的边,用并查集维护即可。

然后随便剖一剖就好了。

复杂度 \(\mathcal{O(q\log^2n)}\) 大概率比 LCT 快吧((((。


edu112
https://proton-z.github.io/2021/07/31/cf-round-edu112/
作者
Imitators
发布于
2021年7月31日
许可协议