Q779的博客

斯坦纳树学习笔记斯坦纳树问题是组合优化问题1 ，其中最常见的是最小斯坦纳树问题。我们一般使用状压dp来求解最小斯坦纳树的问题，当然也有不用状压dp的题啦（最小斯坦纳树题目链接：P6192 【模板】最小斯坦纳树题意：给定一个包含

2022-10-15 OI

算法图论 DP 数据结构

洛谷P5210 [ZJOI2017]线段树题解题目链接：P5210 [ZJOI2017]线段树题意：线段树是九条可怜很喜欢的一个数据结构，它拥有着简单的结构、优秀的复杂度与强大的功能，因此可怜曾经花了很长时间研究线段树的一些性质。

2022-10-14 OI

算法图论数据结构

UOJ49 【UR #3】铀仓库题解题目链接：#49. 【UR #3】铀仓库题意：顽皮的 cxy 潜入了著名核物理专家 Picks 的研究所，走进了存放浓缩铀的仓库。浓缩铀存放在一个个箱子里，一共有 $n$ 叠箱子排成一条直线，不

2022-10-14 OI

算法

洛谷P5299 [PKUWC2018]Slay the Spire 题解题目链接：P5299 [PKUWC2018]Slay the Spire 题意：九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组

2022-10-14 OI

算法数学 DP

容斥原理学习笔记容斥原理容斥原理(principle of inclusion-exclusion)：令 $X$ 为一个有限集合，$P_1, P_2,\dots , P_m$ 是一些性质的集合。对于任意 $S \subseteq [m

2022-10-14 OI

数学咕咕

洛谷P3349 [ZJOI2016]小星星题解题目链接：P3349 [ZJOI2016]小星星题意： cxy 是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有 $n$ 颗小星星，用 $m$ 条彩色的细线串了起来，每条细线连着两颗

2022-10-13 OI

算法数学 DP 咕咕

Splay rotate操作图解Splay 的旋转操作比较难理解，因此我在这里画了一张详细的图解。首先是旋转部分的代码，完整代码见 OI模板-数据结构 void rotate(int x) { int y=t[x].f

2022-10-13 OI

数据结构

洛谷P5369 [PKUSC2018]最大前缀和题解题目链接：P5369 [PKUSC2018]最大前缀和题意： cxy 是一个算法竞赛爱好者，有一天 cxy 遇到了一个非常难的问题：求一个序列的最大子段和。但是 cxy 并不会做这

2022-10-13 OI

算法数学 DP

洛谷P3830 [SHOI2012]随机树题解题目链接：P3830 [SHOI2012]随机树题意：给定一棵随机有根二叉树的叶节点数 $n$ ，求叶子结点深度的期望树深度的期望（根节点深度为 $0$ ）每组数据将给出 $\

2022-10-11 OI

算法数学图论 DP

竞赛图及其性质咕咕咕… 竞赛图的定义若有向简单图 $G=(V,E)$ 满足任意不同两点间都有恰好一条边（单向），则称 $G$ 为竞赛图。注意与有向完全图作区分，有向完全图是任意 $u,v \in V$ 均有边 $u \to v$ 和

2022-10-10 OI

算法图论

CF913F Strongly Connected Tournament 题解题目链接：CF913F Strongly Connected Tournament 题意：有 $n$ 个人，编号为 $1, 2, \cdots, n$ ，他们

2022-10-09 OI

算法数学图论 DP

洛谷P1809 过河问题题解题目链接：P1809 过河问题题意：有一个大晴天，cxy 与同学们一共 $n$ 人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸边有一条小船。船太小了，一次只能乘坐两人。每个人都有一个渡河时间

2022-10-09 OI

算法 DP