分类[ 题解 ]下的文章


题目链接:[HNOI2019] JOJO题意:维护一个字符串 $s$,支持以下两种操作:在 $s$ 末尾插入连续 $x$ 个字符 $c$。将 $s$ 撤回到第 $x$ 次操作之后的状态。在每次操作后,计算 $s$ 的每一个前缀的最长 $\text{border}$ 的长度和。$1\le n\le 10^5$。

阅读全文

题目链接:CF1466H Finding satisfactory solutions题意:由于洛谷目前的中文题面过于简洁,导致看完中文题面之后本题就已经解决了一半,所以我来简单翻译一下英文题面。有 $n$ 个人,第 $i$ 个人初始的时候手上有物品 $i$。他们之间可以交换物品,每个人恰好拿到一个物品。而每个人有对物品的偏好,第 $i$ 个人的偏好用排列 $\{s_{i,n}\}$ 来表示。第 $i$ 个人相较物品 $y$ 更喜欢物品 $x$,当且仅当在排列 $\{s_{i,n}\}$ 中 $x$ 在 $y$ 之前。对于一个物品交换的排列 $p$,表示第 $i$ 个物品最后到了 $p_i$ 的手上。对于一个非空的,人的子集 $S$,如果子集内部的人,使用子集内所有人初始手上的物品进行交换,可以达到以下结果:不存在一个人 $x\in S$,在子集内交换后得到物品 $y\in S$,且第 $x$ 个人比起 $y$ 更喜欢 $p_x$。至少存在一个人 $x\in S$,在子集内交换后得到物品 $y\in S$,且第 $x$ 个人比起 $p_x$ 更喜欢 $y$。则称这样一个子集 $S$ 是“不稳定”的。一个物品交换的排列 $p$ 是“稳定”的,当且仅当不存在一个“不稳定”的子集。现给出一个物品交换的排列 $p$,求有多少种 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$ 使得 $p$ 是“稳定”的。(可以证明,对于一组 $\{\{s_{1,n}\},\{s_{2,n}\}\cdots,\{s_{n,n}\}\}$,恰好存在一个 $p$ 是“稳定”的)$1\le n\le 40$。

阅读全文

题目链接:[Ynoi2008] stcm题意:给定一棵树,可以维护一个集合,支持以下操作:当前集合中插入一个节点 $x$。撤回上一次插入操作。将当前点集标为第 $i$ 个点的子树补信息。一个点 $x$ 的子树补信息定义为:树的点集除去 $x$ 的子树(包括 $x$)内的点得到的集合。要求在 $4.5\times 10^6$ 次操作以内,标记所有点的子树补。$1\le T\le 3,1\le n\le 10^5$。

阅读全文

题目链接:重返现世题意:有 $n$ 个元素,每次抽取到第 $i$ 个的概率是 $\dfrac{p_i}{m}$,求抽到任意不同 $k$ 个的期望次数。$1\le n\le 1000,1\le m\le 10^4,0\le n-k\le 10,\sum p_i=m$。

阅读全文

题目链接:[MtOI2018]情侣?给我烧了!题意:有 $n$ 对情侣,电影院有 $n$ 排共 $2n$ 个座位,每排 $2$ 个座位,求恰好 $k$ 对情侣坐在同一排的方案数。$1\le T\le 2\times 10^5,1\le n\le 5\times 10^6,0\le k\le n$。情侣?给我烧了!

阅读全文

回到顶部