一些有趣的小工程

说实话我觉得竞赛题目挺坑爹的……木有啥意思。人类为何要出题刁难人类。

我更喜欢做的事情是写点工程啥的 >_<… 做做小游戏挺好玩的。

—— vfk 《四色的 NOI》

这算哪门子引用啊

CF603E Pastoral Oddities(结论,LCT/分治+并查集)

题目链接

题意简述

给你一张边带权且边从 $1$ 到 $m$ 编号的无向图 $G$,称一张图 $H$ 是“好的”,当且仅当存在一个 $H$ 的生成子图 $F$ 使得 $F$ 中每个点的度数都是奇数。现在,你需要回答 $m$ 个问题,第 $i$ 个问题是:求最小的 $x$,使得仅保留 $G$ 中编号不超过 $i$ 且边权不超过 $x$ 的边时,得到的生成子图是“好的”,或者指出不存在这样的 $x$。

$2\le n\le 10^5$, $1\le m\le 3\cdot 10^5$, TL 4s。

整体二分学习笔记

整体二分是一种离线算法,可以将一个修改同时作用于多个询问,从而减少不必要的开销,将二分答案从单次询问扩展到多次询问。

在一些题目中,相比与其它解法,整体二分可以避免复杂的数据结构,降低代码难度与空间复杂度。