题解
线性动态规划（线性 DP）概率
[ICPC2018 WF] Gem Island
题面
有 $n$ 个人，最开始每个人手中有 $1$ 颗绿宝石，每天晚上，会随机选一个绿宝石分裂为两个。
求 $d$ 个晚上后绿宝石数量最多的 $r$ 个人的绿宝石数和的期望值。
$1 \le n,d \le 500$ ， $1 \le r\le n$ 。
题解
设最终第 $i$ 个人有 $a_i$ 个宝石，可知其概率
$$ …
Jayun 发布于 2024-02-22 11:56:42
00
Hash费用流深度优先搜索（DFS）
题目大意
给定一棵树和两组 01 权值，求对这棵树重标号后，第一组权值和第二组权值最小不同数。
$n\leq700$ 。
题解
真是一场酣畅淋漓的写题啊！
处理无根树的方式与 P4895 独钓寒江雪 一样，重心作根，两个重心就新开个点向两中心连边；哈希也与之相同。
有根后设 $f_{x,y}$ 表示在子树 $x,y$ 同构的条件下，二者权值最小不同数。考虑转移， $x,y$ 同构而它们 …
Jayun 发布于 2024-02-21 21:06:56
00
基础线段树
[BalkanOI2018] Election
题目描述
有一个长度为 $N$ 的字符串 $S[1\dots N]$ ，它仅由 C 和 T 两种字母组成。
现在有 $Q$ 个查询，每个查询包含两个整数 $L$ 和 $R$ ，表示：设新字符串 $S'=S[L\dots R]$ ，至少在 $S'$ 中要删除多少个字符，才能保证：对于 $S'$ 的每一个前缀和后缀，其 C 的数 …
Jayun 发布于 2024-02-21 15:04:24
00
基础线段树
题面
定义一个好的 $01$ 串 $\mathcal{S}$ 满足以下条件：
$\mathcal{S}$ 非空。
$\mathcal{S}$ 的任意一个前缀 $\mathcal {S}[1\dots p](p\in [1,|$ $\mathcal S$ $|])$ 中， $0$ 的数量都不多于 $1$ 的数量。
$\mathcal{S}$ 的任意一个后 …
Jayun 发布于 2024-02-21 14:59:30
00
Hash树形动态规划（树形 DP）计数
独钓寒江雪
题目描述
给定一棵无根树，求其中本质不同的独立集的个数对 $10^9+7$ 取模的结果。
$n \leq 5\times 10^5$ 。
题解
若有根，明显 DP， $f_{u,0/1}$ 表点 $u$ 选否个数。无根，寻重心以为根，有二则添点向之连边。以哈希判同构，是以组合。
得 beginend 哈希法：
for (int i = 1; i <= tot; i++ …
Jayun 发布于 2024-02-20 21:59:20
00
线性动态规划（线性 DP）
题目
给定两个整数序列 $A$ 和 $B$ ，长度分别为 $n$ 和 $m$ ，且满足 $1\leq A_i,B_i\leq k$ 。现在你希望求出一个满足 $1\leq C_i\leq k$ 的整数序列 $C$ ，它既不是 $A$ 的子序列，也不是 $B$ 的子序列。求 $C$ 的最小长度。
题解
设 $f_{i,j}$ 表示扫完 $A_i,B_j$ 时 …
Jayun 发布于 2024-02-20 14:44:49
00
树状数组
Pairwise Modulo
题面
给定一个由不同数组成的序列 $a$ ，定义 $p_k$ 为：
$$p_k = \sum_{i=1}^k \sum_{j=1}^k a_i \bmod a_j
$$
其中 $a_i \bmod a_j$ 表示 $a_i$ 除以 $a_j$ 的余数。对于每个 $i \in [1,n]$ ，求出 $p_i$ 。
$2\le n \le 2 \ …
Jayun 发布于 2024-02-20 09:25:03
00
最大流基础栈
Projectors
题面
$n$ 个讲课， $m$ 个研讨会， $x$ 个高清投影仪和 $y$ 个普通投影仪。
每堂讲课必须使用一个高清投影仪，而研讨会可以使用普通或高清投影仪。
给定讲课和研讨会的时间区间，构造一个投影仪的分配方案。
$n,m,x,y \leq 300, a_i,b_i,p_i,q_i \leq 10^6$ 。
题解
厉害的建模题。
分配普通投影仪的分配时不需要考 …
Jayun 发布于 2024-02-19 20:59:03
00
基础线段树
题目
你有一个由大写字母 $A$ 和 $B$ 构成的长度为 $n$ 的基因序列 $s$ 。每一次操作把所有子串 $BA$ 替换为 $AB$ ，若干次后基因序列可以有序，即如同 $AAA\dots BBB$ 的形式，你想要知道这个最小次数。
但是这个问题太简单了，你决定加入修改。你现在有 $q$ 次修改，每一次（永久地）把基因序列 $s$ 的一个区间 $[l,r …
Jayun 发布于 2024-02-17 07:54:27
00
高斯消元
题目大意
给定一个二分图，已知这个二分图的完备匹配个数是奇数，询问删除每条边后完备匹配个数的奇偶。
$n\leq2000,m\leq5\times10^5$ 。
题解
线性代数苦手者。
令二分图的邻接矩阵为 $A$ ，二分图的完备匹配个数可以列式 $\sum_p\prod_{i=1}^nA_{i,p_i}$ 。由于题目只考虑奇偶，所以可以看作是在模 2 的背景下，此时邻接矩阵的行列式 $| …
Jayun 发布于 2024-02-15 21:20:02
00