Topcoder UniqueMST
题意问有多少个 $n$ 个点的完全图，满足所有边权在 $[1,K]$ 内，并且最小生成树只有一个。答案对质数 $p$ 取模。$n \leq 50,K \leq 10^9,\max(n,K)+1 \leq p \leq 10^9$。题解先考虑如何求最小生成树：将所有边从小到大排序，按照顺序选择两个端点不在一个联通块的边，并合并这两个联通块。所以我们可以考虑按照权值去考虑这些边：设 $f_{n,...
题意问有多少个 $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...
题意有一个 $n$ 个点的 DAG，现在有 $k$ 波进攻，第 $i$ 波有 $i$ 个人，它们每个人会选择一条 DAG 上的路径，并占领这个路径上的所有点，路径之间是不能相交的。第 $i$ 波进攻前可以做一些准备，可以花 $1$ 秒关闭某个点的所有入边，或关闭某个点的所有出边。第 $i$ 波进攻有个参数 $a_i,b_i$，如果花费了 $t_i$ 时间准备，如果不会所有点都被占领，就会获得...