TH911 Blog

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

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

[NOIP 2017 提高组] 列队

洛谷P3960

题目传送门 题意分析 显然，第 $x$ 行的操作仅影响第 $x$ 行和第 $m$ 列。 因此考虑用 $i$ 个数据结构维护第 $i$ 行的前 $m-1$ 个学生，再用单独的一个维护最后一列。 那么这就是一个序列维护问题，考虑平衡树或权值线段树。 但是直接做空间会炸掉，因此可以优化。 对于平衡树，可以用一个节点存储一段区间，使用时分裂。 对于权值线段树，可以动态开...

Posted by TH911 on June 2, 2025

[NOIP 2017 提高组] 宝藏

洛谷P3959

题目传送门 状压 DP 看到数据范围，因为 $1\leq n\leq12$，因此可以设计指数级算法（一般是搜索或状压 DP），考虑状压 DP。 状态设计 设 \(\textit{dp}_s\) 表示打通的宝藏屋的集合（宝藏屋的状态，且 $0\sim n-1$ 编号）为 $s$ 时的最小代价，$w_{i,j}$ 表示 $(i,j)$ 的长度。 那么转移就可以枚举 $s$ 中的...

Posted by TH911 on June 1, 2025

题解：成绩排名

题目见正文

数据包 洛谷自建题目 题目 题目描述 小 Z 毕业后去了 H 中学教书，他带的班级有 $n$ 个学生，对于每个学生 $i$ 可以用一个正整数 $A_i$ 来衡量其学习能力（$i=1,2,3,\cdots,n$）。有一天，小 Z 捡到了 $k$ 本神奇教材，如果给一个学生学习了这本教材，他的学习能力就会变成原来的 $t$ 倍。小 Z 决定将这本书随机且等概率地发放给班上的 $n$...

Posted by TH911 on May 24, 2025

题解：括号匹配

题目见正文

数据包 洛谷自建题目 题目 题目描述 给定一字符串，只由 (、) 和 * 三种字符组成，你需要替换掉所有的 * 使得整个字符串变为一个 平衡的括号串。你可以选择将一个 * 替换为一个 ( 或 )，也可以直接删掉这个 *（也就是替换为一个 空串）。 一个平衡的括号串定义如下： 空串是平衡的括号串。 如果 $A,B$ 均为平衡的括号串，那么 $AB$ 也是一个平衡的括...

Posted by TH911 on May 24, 2025

扩展 KMP/exKMP/Z 函数 详解

洛谷P5410

例题链接 约定： 本文中所有字符串下标均从 $0$ 开始。 记 $\vert s\vert$ 表示字符串 $s$ 的长度。 记 $s[l,r]$ 表示字符串 $s_ls_{l+1}s_{l+2}\cdots s_r$。 $s=t$ 表示字符串 $s,t$ 相同。 Z 函数 定义 对于一个长为 $n$ 的字符串 $s$，定义函数 $z_i$ 表示 $s$ ...

Posted by TH911 on May 23, 2025

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

要做一个优秀的 OIER

FRIENDS