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

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

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

题解:[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$。 这可以等价于:...

拉格朗日插值

例题:洛谷P4781

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

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

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

题解:[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$ 最近的节点 ...