TH911 Blog

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

题解:可持久化线段树 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$ 的...

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

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

洛谷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 ...

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

洛谷P7077

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

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

洛谷P5049

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

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