LuoguP3209 [HNOI2010] 平面图判定
Description 判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图是否是平面图,图中存在一个包含所有顶点的环,即存在哈密顿回路。 对于一个无向图 $G=(V,E)$,如果能够做到把它画在同一个平面上,使得 $\forall (a,b)(c,d)$,$a,b,c,d$ 两两不等的情况下,边 $(a,b)$ 和…
LuoguP3007 [USACO11JAN] The Continental Cowngress G
Description 给出 $n$ 个法案,$m$ 头牛的意见, 每头牛会表决两次。每次表决格式为 i Y 表示“支持 $i$ 号法案”或 i N 表示“反对 $i$ 号法案”。最终,每头牛至少要有一个表决被满足。不可能成立的话输出 IMPOSSIBLE,否则输出方案。 $1\leq N \leq 1,000,1\leq M \leq 4,000…
浅谈 Manacher
基本概念 回文子串:字符串中反转后与反转前相同的子串。 最长回文子串:字符串中长度最大的回文子串。 第 $i$ 位回文半径:以字符串第 $i$ 位为中心的回文子串的最大长度的一半。 在处理回文子串的问题时,一般需要求出字符串每一位的回文半径。 为了避免奇偶讨论和边界问题,我们可以在每一位字符两侧添加同一个特殊字符,在字符串的首尾各添加一个不同的特殊…
YbtOJ 维护集合 题解
Description 你需要维护一个可重集,初始集合为空,支持 $4$ 种操作: I k 向集合内插入元素 $k$。A k 将集合内所有元素加上 $k$。S k 将集合内所有元素减去 $k$。F k 查询集合内第 $k$ 大。 你需要进行 $n$ 次操作。 一开始给出一个下界 $Minv$,表示集合内的所有元素都必须大于等于 $Minv$,在任何…
CF724G Xor-matic Number of the Graph 题解
Description 题目链接 给你一个无向图,有 $n$ 个顶点和 $m$ 条边,每条边上都有一个非负权值。 我们称一个三元组 $(u,v,s)$ 是有趣的,当且仅当对于 $u,v\in [1,n]$,有一条从 $u$ 到 $v$ 的路径(可以经过相同的点和边多次),其路径上的权值异或和为 $s$。对于一条路径,如果一条边经过了多次,则计算异或…
浅谈线性基
简述 线性基是竞赛中常用来解决子集异或一类题目的算法。基:在线性代数中,基(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数。同样的,线性基是一种特殊的基,它…
UVA1104 芯片难题 Chips Challenge 题解
Description 题目链接 有一个 $N \times N$ 的棋盘,可以在上面放棋子。 有些格子不能放棋子,有些格子必须放棋子,剩下的格子随意。 要求放好棋子之后满足如下两条要求: 第 $i$ 行和第 $i$ 列的棋子数目必须一样多。$(1\leq i \leq N)$第 …
LuoguP2223 [HNOI2001]软件开发 题解
Description 某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),…