状压 DP 求解哈密顿路径 (Hamiltonian Path)

哈密顿路径是经过图中每个顶点恰好一次的路径。该问题为 NP-Hard,在竞赛中顶点数通常较小( ),标准解法为状态压缩动态规划。 - 状态表示: 表示当前经过的节点集合为二进制掩码 、当前停留在节点 的方案数或最短路径长度。 - 状态转移:枚举 的出边 ,若 不在集合中(即 ): - 时间复杂度: ,空间复杂度: 。

字符串哈希

给定一个仅含小写英文字母的字符串 ,将其划分为若干非空子串 ,满足 称该划分为 palindromic,当且仅当把每个 看作一个原子后,序列 本身是回文的,即 要求输出最大的可能 。 输入第一行为测试组数 ,随后 行每行一个字符串 。约束为 , 。 样例: | 输入 | 输出 | |------|------| | b

左偏树 可并堆

左偏树是一种具有左偏性质的堆有序的二叉树。注意,左偏树不是二叉堆。 左偏树的每一个节点存储的信息包括左右子节点 、权值 和 距离 。 左儿子或右儿子为空的节点,称为外节点。节点的距离的定义:即该节点到与其最近的外节点经过的边数。 我们规定,外节点的距离为 0,空节点的距离为 -1。 [图片缺失:Pasted image

平面最近点对

给定平面上任意n个点,求最近的一对点之间的距离 我们使用类似于归并排序的思想解决这道题目.归并排序的思想是,如果一个区间的答案能够由二分划出的左区间,右区间,同时能够通过常数复杂度得到跨越mid左右区间的元素组成的答案,那么我们就可以以 的复杂度解决这道题目. 容易想到,我们可以对x坐标进行排序,然后每次递归处理左右两

P5490 【模板】扫描线 & 矩形面积并

求 个四边平行于坐标轴的矩形的面积并。 第一行一个正整数 。 接下来 行每行四个非负整数 ,表示一个矩形的四个端点坐标为 。 一行一个正整数,表示 个矩形的并集覆盖的总面积。 对于 的数据, 。 对于 的数据, , , 。 Updated on 4.10 by Dengduck(口胡) \& yummy(实现):增加了

排列进制(Cantor展开)

CSES Permutation Order 这道题让我们求一个排列在全排列中的位次,以及给出n和位次求解这个排列,我们可以把一个排列映射到一个进制上进行处理. 形式化的,我们记一个数字的阶乘进制为 : ,阶乘进制的每一个数字 ,在排列中正好对应了在当前剩余数字中,选第几个小的数字.直接运用进制转换的知识进行转换即可,

斯特林数 (Stirling Numbers)

将 个不同元素,划分为 个非空圆排列的方案数,记作 或 。 递推式: 组合意义: 个人坐 张圆桌的方案数。考虑第 个人: 1. 若单独坐一桌,前面 人坐 张桌子,方案数为 ; 2. 若坐到已有人的桌子上,先让前 个人坐 张桌子,第 个人可以坐到这 个人中任意一个人的左边,方案数为 。 将 个不同元素,划分为 个非空子集

期望DP

Niuniu 喜欢玩 OSU!。将该游戏简化为如下问题: 给定两个整数 ,接下来有 次点击,每次点击可能成功也可能失败。若一段连续成功的长度(连击长度)为 ,则该段贡献 分。第 次点击成功的概率为 。求总得分的期望值,结果对 取模。 输入 - 第一行两个整数 。 - 第二行 个整数 。 数据范围 样例输入 样例输出 1