TH911 Blog

「光阴不可测，岁月亦无歌。」

题解：[集训队互测 2011] Crash 的文明世界

洛谷P4827 | 斯特林数展开下降幂 | 换根 DP

题目传送门 题意分析 树上问题 首先，$n$ 个点 $n-1$ 条边，显然是一个树。 因此，$\operatorname{dist}(i,j)$ 其实可以 $\mathcal O(1)$ 计算出来。只需要 $\mathcal O(n\log n)$ 预处理一个 DFS 序 LCA 即可。（详见此处） 斯特林数 对于整数 $x$ 的 $k$ 次方，其实可以通过第二类斯特林数...

Posted by TH911 on July 15, 2025

题解：重返现世

洛谷P4707 | kth Min-max 容斥 | DP

题目传送门 题意分析 kth Min-max 容斥 首先可以去除掉 $p$ 中的 $0$，因为 $p_i=0$ 的 $i$ 不会生成，对答案没有任何影响。 求收集到 $k$ 种原料的期望时间，即求收集所有原料的期望时间的第 $k$ 大时间。 那么就可以考虑 kth Min-max 容斥。 定义 \(\operatorname*{kthmin}\) 表示求第 $k$ 小，\...

Posted by TH911 on July 15, 2025

题解：[PKUWC2018] 随机游走

洛谷P5643 | Min-max 容斥 | 树形 DP | 高维前缀和

题目传送门 题意分析 Min-max 容斥 记走到点 $i$ 的期望步数为 $t_i$，$S=\set{1,2,3,\cdots,n}$，题目所求即： \[E\left(\max_{i\in S}t_i\right)\] 根据 Min-max 容斥，等价于求： \[\sum_{T\subseteq S}(-1)^{\vert T\vert-1}E\left(\min_{i...

Posted by TH911 on July 15, 2025

题解：已经没有什么好害怕的了

洛谷P4859 | 二项式反演

题意分析 设“糖果”能量为 $a_1,a_2,a_3,\cdots,a_n$，“药片”能量为 $b_1,b_2,b_3,\cdots,b_n$；不妨令 $a,b$ 均单调递增。 因为 $a_i,b_j$ 互不相同，因此每一种组合都是独一无二的。 设“糖果”比“药片”能量大的组数为 $k’$，则有 $k’+(k’-k)=n,k’=\dfrac{n+k}{2}$。 观察题面和样例解释...

Posted by TH911 on July 15, 2025

题解：[HAOI2015] 按位或

洛谷P3175 | Min-max 容斥

题目传送门 题意分析 设 $t_i$ 表示第 $i$ 位变为 $1$ 的时间，设 $S=\lbrace1,2,3,\cdots,n\rbrace$。 则题目所求为： \[E\left(\max_{i\in S} t_i\right)\] 期望套 $\max$，看起来就很像 Min-max 容斥。 由 Min-max 容斥，有： \[E\left(\max_{i\in S...

Posted by TH911 on July 14, 2025

题解：[TJOI2015] 概率论

洛谷P3978 | “数学题” | 卡特兰数

题目传送门 题意分析 首先，对于这种输入只有一个数，从这一个数就能推出答案的题目，大概率是个毒瘤数学题。如此考虑求解。 求期望，期望即总叶节点数除以不同构的二叉树个数。 令 $n$ 个节点的不同构二叉树个数为 $f_n$，其叶节点总数为 $g_n$，则答案即 $\dfrac{g_n}{f_n}$。 考虑如何求解 $f_n,g_n$。 先考虑求解 $f_n$。其实 $f_n...

Posted by TH911 on July 14, 2025

题解：[RMI 2020] 秘鲁 / Peru

洛谷P11405 | 双栈模拟双端队列

题目传送门 Upd 2026/2/26：修了代码，放了一份封装完善的；加入了 DP 推导部分。 本篇题解主要介绍本题线性做法所利用的数据结构。当时第一次见到这种东西，没想到不那么冷门…… 题意分析 DP 是显然的： \[f_i=\min_{j=i-k}^{i-1}\left(f_j+\max_{l=j+1}^is_l\right)\] 维护不难做到 $\mathcal...

Posted by TH911 on July 14, 2025

题解：[HNOI2004] 树的计数

洛谷P2290 | Prüfer 序列

题目传送门 题意分析 对于这种关于树上度数的计数问题，一般会考虑使用 Prüfer 序列求解（Prüfer 序列参见此处）。 Prüfer 序列（Prufer 序列）的主要作用就是将无根树与序列相互转换，每一个确定的无根树都对应一个确定的 Prüfer 序列。 那么对于这道题目，假如树确定了，那么对应的 Prüfer 序列。因此满足条件的树的棵数即 Prüfer 序列的数量。...

Posted by TH911 on July 14, 2025

题解：齿轮

洛谷P6298 | 最大公因数转换

题目传送门 题意分析 将从 $n$ 个 $a_i$ 中选出 $k$ 个数，使得这 $k$ 个数的最大公因数为 $t$ 记为 $f_t$。题目即求解 $f_1,f_2,\cdots,f_m$。 但是可以发现这并不好求，因为无法确定最大公因数为 $t$ 对应哪 $k$ 个数。 可以思考一个常用的技巧：将最大公因数转化为普通因数。 那么我们求 $k$ 个数的因数均包含 $t$ 的...

Posted by TH911 on July 14, 2025

题解：可持久化线段树 2

静态区间第 $k$ 小问题

例题链接 静态区间第 $k$ 小 可以使用可持久化权值线段树解决。 求 $a[l,r]$ 第 $k$ 小不好求，因此可以考虑先简化一下，求 $a[1,r]$ 的 $k$ 小值。 这就可以使用可持久化权值线段树，对于每一个 $i$，给 $a_1\sim a_i$ 建一棵权值线段树统计数量。 查询时，使用前缀和与差分获取真实的 $[l,r]$ 中的数的个数即可。 AC 代码 ...

Posted by TH911 on July 13, 2025

FEATURED TAGS
树状数组 题解 省选/NOI− 提高+/省选− DP 基础算法 普及+/提高 数学 线段树 贪心 普及/提高− 组合数学 字符串 未完 二分 图论 平衡树 数论 树形 DP Tarjan 位运算 搜索 Trie 二分答案 状态压缩 无聊时候的一点思考 最短路 FHQ Treap NOI/NOI+/CTSC 前端 前缀和 树链剖分
ABOUT ME

要做一个优秀的 OIER

FRIENDS