TH911 Blog

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

[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

[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

题解：[NOIP 2015 提高组] 斗地主

洛谷P2668

题目传送门 题意分析 爆搜即可。 优先出顺子、带牌，剩下的散排无论几张，一类牌都可以一次出完。 一个坑点：一定不要使用 else if，我因为这个导致某些操作不会被判断。 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...

Posted by TH911 on May 18, 2025

题解：[NOIP 2018 普及组] 摆渡车

洛谷P5017

题目传送门 DP 很明显能想到 DP。 状态设计 不妨令 $t$ 从小到大有序，设 $dp_{i,j}$ 表示前 $i$ 个人在第 $i$ 个人等待了 $j$ 时刻时全部上车的最短时间。 状态转移 从其他状态转移到 $dp_{i,j}$ 不是很好做，因此可以从 $dp_{i,j}$ 转移到其他状态。 枚举一个 $k$，表示前 $i+k$ 个人都上车，且第 $i+1\si...

Posted by TH911 on May 18, 2025

题解：[NOIP2021] 数列

洛谷P7961

题目传送门 DP 状态设计 为了便于处理，称二进制最低位为第 $0$ 位（权值位 $2^0$）。 考虑从小到大填入 $a_i$。 设 $dp_{i,j,k,l}$ 表示处理了 $a_1\sim a_i$，$S$ 能进位到的最高位为 $2^j$（实际上最高位也可以不是 $2^j$，之前的 $a_i$ 最大值为 $j-1$），最高位 $2^j$ 有 $k$ 个，已知 $l$ 位...

Posted by TH911 on May 18, 2025

题解：[NOIP 2017 普及组] 跳房子

洛谷P3957 | 单调队列优化 DP

题目传送门 题意分析 首先，花费的金币越多，灵活性越高，能够获得的分数也就越高。 因此，能够获得的分数是具有单调性的，考虑二分答案。 判断花费 $g$ 金币时能够获得的最高分数，考虑 DP。 设 $dp_i$ 为跳到第 $i$ 个格子时的最高分数。 则有： \[dp_i=s_i+\max_{x_i-d-g\leq x_j\leq x_i+\max(1,d-g)} dp_...

Posted by TH911 on May 17, 2025

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

要做一个优秀的 OIER

FRIENDS