TH911 Blog

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

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

题解：[NOI2024] 分数

洛谷P10788

题目传送门 第一道黑题居然是 NOI 的题。 题意分析 显然，$f(i,j)=f(j,i)$，因此可以假定 $n\leq m$。（否则交换 $n,m$）。 生成方式唯一 假设 $x\in S$，则从 $2$ 开始生成，$x$ 的最短生成方式是唯一的。 证明 由 $S$ 性质可得： $\dfrac1x\in S$。 $x+2k\in S$。 这可以等价于：...

Posted by TH911 on July 7, 2025

拉格朗日插值

例题：洛谷P4781

例题传送门 拉格朗日插值法 在数值分析中，拉格朗日插值法是以法国 $18$ 世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。如果对实践中的某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。上面这样的多项式就称为拉格朗日（插值）多项式。 设 $n-1$ 次多项式 $f(x)$ 的函数图像过 $...

Posted by TH911 on July 6, 2025

题解：「CROI · R2」01-string

洛谷P10766

题目传送门 题意分析 给定长度为 $n$ 的 $01$ 串 $s,t$，可以对 $s$ 执行三个操作： 将 $s_l,s_{l+1},s_{l+2},\cdots,s_r$ 均改为 $0$，记为 OFF 操作。 将 $s_l,s_{l+1},s_{l+2},\cdots,s_r$ 均改为 $1$，记为 ON 操作。 翻转 $s_l,s_{l+1},s_{l+2},...

Posted by TH911 on July 5, 2025

题解：[Violet] 蒲公英

洛谷P4168 | 分块维护众数

题目传送门 题意分析 给定序列 $a$，求 $a_l\sim a_r$ 的众数（出现次数最多的数）。 首先注意到 $1\leq a_i\leq10^9$，而 $n\leq4\times10^4$，显然可以离散化。 暴力会超时，那就优化暴力：对 $a$ 以 $\sqrt n$ 为块长进行分块，第 $i$ 块为 $a_{(i-1)\sqrt n+1}\sim a_{i\sqr...

Posted by TH911 on June 28, 2025

题解：[JOIST 2023] 比太郎之旅 / Bitaro's Travel

洛谷P9342

题目传送门 题意分析 首先发现，$n,q\leq2\times 10^5$，$\mathcal O(q)$ 肯定是不能省略的。 每一个询问其实都差不多，因此考虑如何高效的求出总旅行距离。 性质 记 $(p,q)$ 表示节点 $p\sim q$ 的距离，即 $\vert x_p-x_q\vert$。 令当前起始坐标为 $s$。首先可以通过一次二分求出离 $s$ 最近的节点 ...

Posted by TH911 on June 28, 2025

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

要做一个优秀的 OIER

FRIENDS