TH911 Blog

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

题解：可持久化线段树 1（可持久化数组）

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

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

Posted by TH911 on July 13, 2025

题解：[国家集训队] 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}^...

Posted by TH911 on July 11, 2025

题解：[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...

Posted by TH911 on July 10, 2025

题解：[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)$。 若没有野人相遇，则 $...

Posted by TH911 on July 10, 2025

题解：Short Task

CF1512G

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

Posted by TH911 on July 10, 2025

题解：[TJOI2009] 猜数字

洛谷P3868

题目传送门 题意分析 显然，$n\equiv a_i\pmod{b_i}$。 因此可以使用 CRT 求解。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46...

Posted by TH911 on July 9, 2025

题解：通往奥格瑞玛的道路

洛谷P1462

题目传送门 题意分析 求经过的城市收费最大值的最小值，显然需要二分答案。 那么二分这个值，之后只需要跑一遍最短路即可。 注意不要混淆“血量”与城市“收费”即可。 AC 代码 时间复杂度：$\mathcal O((n+m)\log m\log n)$。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ...

Posted by TH911 on July 8, 2025

题解：[CSP-S2020] 函数调用

洛谷P7077

题目传送门 题意分析 显然，每个数据最终的值都可以表示为 $ka_i+b_i$。 $k$ 就是所有的 $2$ 操作的 $v$ 之积,而重点就在于如何计算 $b_i$。 可以将操作 $3$ 的关系建成图，因为没有递归，因此是无环图，则原图是一个 DAG，那么就容易想到拓扑排序后 DP。 只需要从后往前合并，将乘法操作转化为若干次加法操作计算即可。 AC 代码 时间复杂度：...

Posted by TH911 on July 8, 2025

题解：[NOIP 2018 提高组] 旅行 加强版

洛谷P5049

题目传送门 题意分析 旅行原题中是 $\mathcal O\left(n^2\right)$ 的，但是加强版中 $n\leq500000$，因此需要优化。 对于 $m=n-1$ 的情况，可以直接 DFS 一遍求得答案。 但是对于 $m=n$ 的情况，原题是 $\mathcal O(m)$ 枚举断边，因此效率低下。 考虑如何快速确定环上的边应不应该断。 令断边为 $(u,v...

Posted by TH911 on July 8, 2025

题解：[CSP-S 2022] 假期计划

洛谷P8817 | BFS 最短路

题目传送门 题意分析 $n\leq2500$，直接 $\mathcal O\left(n^4\right)$ 肯定不行，但是也代表着 $\mathcal O\left(n^2\right)$ 量级的时间或空间复杂度是可以接受的。 因此，可以在 $\mathcal O\left(n^2\right)$ 的时间内通过 $n$ 次 BFS 求出 $\textit{can}_{i,j}...

Posted by TH911 on July 8, 2025

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

要做一个优秀的 OIER

FRIENDS