TH911 Blog

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

题解:[TJOI2015] 概率论

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

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

题解:[RMI 2020] 秘鲁 / Peru

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

题目传送门 双栈模拟队列 本篇题解主要介绍本题线性做法所利用的数据结构。 时间限制 $\text{300ms}$,又是交互题(无需 IO),显然是为了卡时间。 那么这道题大概率是一个 $\mathcal O(n)$ 的线性做法。 其实这道题目需要用到一个黑科技:双栈模拟队列。(具体见下文) 这道题目 DP 之后便是要维护一个数据结构,实现: 双端插入、删除。 ...

题解:[HNOI2004] 树的计数

洛谷P2290 | Prüfer 序列

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

题解:齿轮

洛谷P6298 | 最大公因数转换

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

题解:可持久化线段树 2

静态区间第 $k$ 小问题

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

题解:可持久化线段树 1(可持久化数组)

主席树 | 动态开点可持久化线段树

例题链接 可持久化线段树/主席树 可持久化线段树与主席树 “主席树”其实只是一个称呼,“主席树”的提出者也没有进行一个严谨的定义,一般主席树就是指可持久化权值线段树。 算法简介 可持久化线段树,可以维护多个历史版本下的线段树,支持单点修改,因此可以用来实现可持久化数组。 但是如果给每一个版本都开一个线段树,若有 $n$ 个节点,$m$ 个版本,空间复杂度就是 $\math...

题解:[国家集训队] Crash的数字表格 / JZPTAB

洛谷P1829

题目传送门 莫比乌斯反演 对于这种题目,显然是一个数学题,因此可以转换。 不妨钦定 $n\leq m$,否则交换 $n,m$。 记答案为 $\textit{ans}$: \[\begin{aligned} \textit{ans}&=\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)\\ &=\sum_{i=1}^...

题解:[NOI2018] 屠龙勇士

洛谷P4774

题目传送门 exexCRT 一条龙对应的剑可以通过平衡树等数据结构快速确定第 $i$ 条龙单次收到攻击为 $f_i$。 $x$ 次攻击后,龙的血量为 $a_i-f_ix$。 若干次回血后,血量为 $0$,即: \[\begin{aligned} a_i-f_ix&\equiv0&\pmod{p_i}\\ f_ix&\equiv a_i&\pm...

题解:[NOI2002] 荒岛野人

洛谷P2421

题目传送门 题意分析 观察数据范围,$1\leq n\leq15,1\leq m\leq10^6$,数据范围不大,因此可以考虑枚举 $m$。 两个野人 $i,j$ 在第 $x$ 年相遇即: \[c_i+x\cdot p_i\equiv c_j+x\cdot p_j\pmod m\] 同时,$x$ 需要满足 $x\leq\min(l_i,l_j)$。 若没有野人相遇,则 $...

题解:Short Task

CF1512G

题目传送门 题意分析 一个显然的性质,$d(n)\geq n$。因为 $n$ 自己一定是自己的因数。因此,若 $d(n)=c$ 存在,则 $n\leq c$。 又发现 $c\leq10^7$,且多次询问基本相同,因此可以考虑预处理出答案后离线处理。 自己写一下就可以发现,从 $n$ 找其因数求和并不好做,我太菜了,因此可以考虑从 $n$ 找其倍数 $kn$,更新 $kn$ 的...