星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

平常改的题里面那些还算有意思的题

posted on 2018-09-20 18:49:58 | under Diary |

记录一些印象还不错的题。
[dy0607]revive
[ShichengXiao]Xor
[Simu]test
[Wearry]strange

$[Simu]babystep$

题意:给定一个 $n\times n$ 的网格图,一开始断掉一条边并查询两点是否在一个连通块内,之后给定 $m-1$ 个询问 $(x,y,z,o,x',y',z',o')$ ,上次询问的答案为是,那么断掉前四个所代表的一条边(给的是横纵坐标),否则断掉后四个所代表的边,并继续询问。 $n\le 500,m\le 2n^2-2n$
这题很妙。
你可以把一个点变成一个正方形格子,于是断边变成了连接两个方格边上的点。就像这样: $\begin{matrix}1\ 2\ 3\\ 4\ 5\ 6\end{matrix}$$ 1号点拆成 $1,2,4,5$ ,2号点拆成 $2,3,5,6$ 。然后断边就把 $2,5$ 这两个点连接起来。
一开始这个转化后的大格子的边缘是连起来的,然后我们每次可以用 $dsu$ 实现这个操作。但当我们合并前就发现原来两个点就连通的时候,实际上原图上的两点就断开了。就这样在 $merge$ 的时候判断一下就行了。这个可以在原图上画一画。

$2019.3.23[dy0607]lemon$

这里写的是 $zhou888$ 的解法。
我们考虑一个比较显然的贪心,就是记录一下每个点的到根的前缀 $\min$ ,然后排序之后把 $a$ 也排序贪心选。
但是当我们遇到不能选的时候,显然我们就要加坚固度了。但实际上我们对于所有没选的点都要枚举一下,然后再继续贪心验证,否则正确性显然是错的,因为每个点的限制会受到影响(因为是前缀 $\min$ )。这样时间复杂度是 $O(n^2\log n)$ 的。
我们考虑把它直接放到序列上,然后