做题记录 25.5.14

· · 个人记录

UOJ #670. 【UNR #5】获奖名单

令 l 为总长度，用 | 表示回文串的中心位置，用一组括号表示一个字符串，相同字母表示相同字符

考虑从中心向外构造

先考虑 l 为偶数且不存在跨越 \frac l2 和 \frac l2+1 的字符串的一般情况

则需要找到以下两种形式之一：

取出这一部分后回文串左右剩余部分拼起来仍然为一般情况

若每个字符建立一个点，再额外建立一个虚点，对于长为 2 的字符串 (ab) 在 a 和 b 之间连无向边，对于长度为 1 的字符串 (a) 在 a 和虚点之间连边，则第一种相当于找一对重边（可退化为双自环，若重边一端为虚点则包括在第二种中），第二种相当于找到一个包含虚点的环（可以不是简单环，若包含虚点多次则可断为多个环）

然后考虑一般情况

若总长为偶数，则要么为上述一般情况，要么在上述基础上增加一个自环

求出虚点所在连通块的欧拉回路（题目保证有解，因此一定存在欧拉回路），这个回路覆盖了一般情况的第二种形式，沿着回路移动一遍，把字符串交错放置到中点左右

剩余部分一定只含长为 2 的字符串（否则无解），分为两类，重边和自环，每种类型分别两两抵消，每组两个一左一右放在中点两侧，最终重边一定恰好完全消去，自环至多剩下一个，若剩下一个则放在中间

若总长为奇数，则在一般情况的基础上需要增加一条虚点开始非虚点结束的路径（设路径为 a-b-c-d-\cdots-e-f-g-\text v，其中 \text v 为虚点，则中间部分为 (gf)(e\ast)\cdots (\ast d)(cb)(\overline ab)(cd)\cdots(ef)(g)，其中 \overline a 为中点），此时虚点所在连通块为半欧拉子图，其中起点为中间部分对应路径的终点，其他连通块都是欧拉子图

找出起点，求出欧拉路，欧拉路第一条边放置在中心，之后左右交替放置（先左后右），最终同样剩余重边和自环，处理方式和偶数长度类似，但没有剩余

时间复杂度 O(n+m)（若统计重边时用 unordered_map）

代码

参考

\purple\odot CF547D Mike and Fish

每个 x 坐标和每个 y 坐标建立一个点，若 (x,y) 为 \text r 则 x\to y，若 (x,y) 为 \text b 则 x\gets y

问题转化为给一张无向图定向，使之每个点的出度入度只差不超过 1

度数为奇数的点数量为偶数，两两配对，一对中两个之间连额外边，则转化为定向使出度入度相同，求欧拉回路即可

时间复杂度 O(n+V)

代码