CF1991E Coloring Game 题解
Description 有一个由 nnn 个顶点和 mmm 条边组成的无向图。每个顶点可以用三种颜色之一着色： 111 、 222 或 333 。初始时，所有顶点都未着色。 Alice 和 Bob 正在玩一个包含 nnn 轮的游戏。在每一轮中，都会发生以下两个步骤： Alice 选择两种不同的颜色。 Bob 选择一个未着色的结点，并用 Alice 选择的两种颜色之一为其着色。 如果存在连接两
LOJ #6089. 小 Y 的背包计数问题 题解
Description 小 Y 有一个大小为 nnn 的背包，并且小 Y 有 nnn 种物品。 对于第 iii 种物品，共有 iii 个可以使用，并且对于每一个 iii 物品，体积均为 iii。 求小 Y 把该背包装满的方案数为多少，答案对于 233333332333333323333333 取模。 定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。 1≤n≤1051\leq n\l
P6192 【模板】最小斯坦纳树 题解
Description 给定一个包含 nnn 个结点和 mmm 条带权边的无向连通图 G=(V,E)G=(V,E)G=(V,E)。 再给定包含 kkk 个结点的点集 SSS，选出 GGG 的子图 G′=(V′,E′)G'=(V',E')G′=(V′,E′)，使得： S⊆V′S\subseteq V'S⊆V′； G′G'G′ 为连通图；
P10013 [集训队互测 2023] Tree Topological Order Counting
Description 给定一颗 nnn 个点的有根树，111 是根，记 uuu 的父亲是 faufa_ufau。另给出一长度为 nnn 的权值序列 bbb。 称一个长度为 nnn 的排列 aaa 为这颗树的合法拓扑序，当且仅当 ∀2≤u≤n,au>afau\forall 2 \le u \le n,a_u > a_{fa_u}∀2≤u≤n,au>afau。 对每个点
P5469 [NOI2019] 机器人 题解
Description 小 R 喜欢研究机器人。 最近，小 R 新研制出了两种机器人，分别是 P 型机器人和 Q 型机器人。现在他要测试这两种机器人的移动能力，测试在从左到右排成一排的 nnn 个柱子上进行，柱子用 1−n1 - n1−n 依次编号，iii 号柱子的高度为一个正整数 hih_ihi。机器人只能在相邻柱子间移动，即：若机器人当前在 iii 号柱子上，它只能尝试移动到 i−1i -
LOJ #160. 树形背包 题解
Description 有 NNN 个物品，编号分别为 1…N1\ldots N1…N。物品 iii 的重量为 wiw_iwi，价值为 viv_ivi。 给出每个物品依赖于哪个物品。我们用 di=j (i>j>0)d_i = j\ (i>j>0)di=j (i>j>0) 表示：如果要选取物品 iii，就必须先选取物品 jjj。另外，我们用 di=0(i&
CF1810G The Maximum Prefix 题解
Description 构造一个长度最多为 nnn 的数组 aaa，其每个元素均为 111 或 −1-1−1。生成方式如下： 选择任意整数 k∈[1,n]k\in[1,n]k∈[1,n] 作为 aaa 的长度。 对于 ∀i∈[1,k]\forall i\in[1,k]∀i∈[1,k]，有 pip_ipi 的概率设 ai=1a_i=1ai=1，有 1−pi1-p_i1−pi 的概率设 ai
P4126 [AHOI2009] 最小割 题解
Description A,B 两个国家正在交战，其中A国的物资运输网中有 NNN 个中转站，MMM 条单向道路。设其中第 i (1≤i≤M)i\ (1\leq i\leq M)i (1≤i≤M) 条道路连接了 ui,viu_i,v_iui,vi 两个中转站，那么中转站 uiu_iui 可以通过该道路到达 viv_ivi 中转站，如果切断这条道路，需要代价 cic_ici。 现在B国想