CF243E Matrix PQTree
题目链接题解对于维护「某些元素之间必须贴贴相邻」这样的问题，可以考虑使用一种叫做 PQTree 的结构来维护。PQTree 上的点有三种类型：叶子结点，表示一个元素P 类节点，表示这个节点的儿子的顺序是可以任意排布的Q 类节点，表示这个节点的儿子的顺序必须是当前给出的顺序或者逆序现在我们考虑如何加入一个限制。设这一次限制是要求 $S$ 内的元素贴贴，那么我们把 $S$ 内对应的叶子都标记成黑...
题目链接题解对于维护「某些元素之间必须贴贴相邻」这样的问题，可以考虑使用一种叫做 PQTree 的结构来维护。PQTree 上的点有三种类型：叶子结点，表示一个元素P 类节点，表示这个节点的儿子的顺序是可以任意排布的Q 类节点，表示这个节点的儿子的顺序必须是当前给出的顺序或者逆序现在我们考虑如何加入一个限制。设这一次限制是要求 $S$ 内的元素贴贴，那么我们把 $S$ 内对应的叶子都标记成黑...
题意问有多少个 $n$ 个点的完全图，满足所有边权在 $[1,K]$ 内，并且最小生成树只有一个。答案对质数 $p$ 取模。$n \leq 50,K \leq 10^9,\max(n,K)+1 \leq p \leq 10^9$。题解先考虑如何求最小生成树：将所有边从小到大排序，按照顺序选择两个端点不在一个联通块的边，并合并这两个联通块。所以我们可以考虑按照权值去考虑这些边：设 $f_{n,...
题意平面上有 $m$ 个特殊点，每个点有一个颜色。还有 $n$ 个点均匀分布在半径为 $r$ 的圆上，认为有一个点在 $(r,0)$。现在问有多少种方式，可以在这些点之间连线，满足：每个点度数是 $0$ 或 $2$这些线段与点构成了若干个封闭的简单多边形，并且互不相交，互不包含所有相同颜色的特殊点必须在同一个多边形内每一个多边形内部至少要有一个特殊点每一个特殊点至少要在一个多边形内部问这样分...
题意你要和一堆骰子玩剪刀石头布。有 $n$ 个骰子，每个骰子有三种结果：R，S，P。概率分别是 $pR_i,pS_i,pP_i$。每次你会随机选择一个没有用过的骰子，然后你决定好出什么，然后扔这个骰子。如果获胜得 $3$ 分，平局得 $1$ 分，失败得 $0$ 分。你无法分辨出每一次拿出的骰子是什么，但你可以通过每一局的结果来决策之后的操作。求期望最多可以获得多少得分。$1 \leq n \...
D1T2 逛街题意给定一个长度为 $n$ 的序列，有 $m$ 次操作，每次操作为如下两种形式之一：1 l r 从左到右遍历 $i \in [l,r-1]$，令 $a_i \gets \max(a_i,a_{i+1})$输出区间 $[l,r]$ 中所有前缀最大值的和保证初始时 $a_i$ 两两不同。$n,m \leq 3 \times 10^5$。题解有一档部分分是，保证操作 1 中 $l=1...