集合统计类期望题目。 题目描述 在一片大海上有 $ n$ 个岛屿，规划建设 $ m$ 座桥，第i座桥的成本为 $ z_i$，但由于海怪的存在，第 $ i$ 座桥有 $ p_i$ 的概率不能建造。 求在让岛屿尽量联通的情况...

老了…稍微麻烦一点的树形 DP 都想不到了。 我也不知道什么时候养成的数字 汉字之间 加 空 格 的习惯。听说是好习惯？ 题目描述 给定一棵树，边权是整数 $ c_i$ ，找出两条不相交的链（没有公共点），使...

可能是一个 SAM 常用技巧？感觉 SAM 的基础题好多啊.. 题目描述 给定一个长度为 $ n$ 的字符串 $ S$ ，令 $ T_i$ 表示它从第 $ i$ 个字符开始的后缀，求： $$> \sum_{1\le i<j\le n}len(T_i)+le...

后缀自动机入门。 题目描述 为了提高智商，ZJY 开始学习弦论。 这一天，她在《String theory》中看到了这样一道问题：对于一个给定的长度为 $ n$ 的字符串,求出它的第 $ k$ 小子串是什么。你能帮帮...

有意思的网格图转化。CF Div.1 还是挺有难度的。 注：由于本题有较完美的中文题面，所以不贴英文题面。 英文题面 题目描述 Innopolis 大学的教授正努力研究元素周期表。他们知道，有 $ n \tim...

前言 最小圆覆盖和最小矩形覆盖其实是有一定区别的。在矩形中有两组平行直线，在圆中则没有。 随机增量法 因为复杂度是在期望意义下计算的，所以无论题目给出什么样的数据，我们都要随机一下，这就是“随机”的...

很有意思的题目。 题目背景 加特林轮盘赌是一个养生游戏. 题目描述 与俄罗斯轮盘赌等手枪的赌博不同的是，加特林轮盘赌的赌具是加特林。 加特林轮盘赌的规则很简单：在加特林的部分弹夹...

题目链接 A. Sushi for Two 题意 在一个 01 序列中找出长为偶数的连续的一段使得它前一半和后一半内部分别相同，而前一半和后一半不同。 $ 2\le n\le 100\ 000$ 题解 令共有 $ k$ 段连续的区间，第 $ i$ 段...

平衡树分裂钛好玩辣！ 题目描述 方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。 OJ 上注册了 $ n$ 个用户，编号为 $ 1\sim n$，一开始他们按照编号排名。方伯伯会按照心情对这些用户做...

动态点分治入 门 题？ 题目描述 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 $ N$ 个屋子和 $ N-1$ 条双向走...