TH911 Blog

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

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

题解：[NOIP 2011 提高组] 聪明的质监员

洛谷P1314

题目传送门 题意分析 记 $W=x$ 时，答案为 $\textit{calc}(x)$。 则可以发现，答案为： \[\textit{calc}(W)=\sum_{i=1}^my_i=\sum_{i=1}^m\left(\sum_{j=l_i}^{r_i}[w_j\geq W]\times\sum_{j=l_i}^{r_i}[w_j\geq W]v_j\right)\] 显然...

Posted by TH911 on June 28, 2025

题解：[NOIP 2018 提高组] 填数游戏

洛谷P5023

题目传送门 打表 容易发现 $n,m$ 没有什么区别，即 $n$ 行 $m$ 列的棋盘等价于 $m$ 行 $n$ 列的棋盘。 观察数据范围，可以发现 $n\leq8$，而 $m\leq10^6$。 因此可以考虑打表，然后找一下规律。 打出来表得到： 1 2 3 4 5 6 7 8 9 10 11 int f[9][9]={ {0,0,0,0,0,0,0,0,0}, {...

Posted by TH911 on June 13, 2025

题解：[SDOI2017] 序列计数

洛谷P3702 | 分治 DP

题目传送门 题意分析 首先，“至少一个数是质数”就很不好判断，考虑容斥掉。答案即 不考虑是否为质数的答案 减去 没有质数的答案。 观察到 $1\leq p\leq100$，考虑复杂度与 $p$ 正相关的算法。 设 $f_{i,j}$ 表示第 $1\sim i$ 个数，和模 $p$ 为 $j$ 时的不考虑是否为质数答案。没有质数的答案为 $g_{i,j}$。答案即： \[(f...

Posted by TH911 on June 7, 2025

题解：[NOI2012] 随机数生成器

洛谷 P2044 | 矩阵快速幂优化递推

题目传送门 题意分析 显然，因为 $n\leq10^{18}$，不能直接计算。因此考虑优化。 考虑到： \[X_{n+1}\equiv aX_n+c\pmod m\] 考虑优化这个递推，想到矩阵快速幂。 构造矩阵： \[\begin{bmatrix} X_{n+1}\\1 \end{bmatrix} = \begin{bmatrix} a&c\\0&1 ...

Posted by TH911 on June 7, 2025

线性代数学习笔记

矩阵 行列式

参考资料 参考 Blog 参考资料 矩阵 简介 矩阵源于线性方程组，例如对于以下方程组： \[\begin{cases} x_1+2x_2-x_3&=2\\ 2x_1+x_2+x_3&=7\\ -x_1+3x_2&=5 \end{cases}\] 将未知数分开，可以写为矩阵： \[\begin{bmatrix} 1&2&-1\\ 2...

Posted by TH911 on June 7, 2025

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

要做一个优秀的 OIER

FRIENDS