TH911 Blog

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

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

题解：[NOIP 2016 提高组] 愤怒的小鸟

洛谷P2831

题目传送门 题意分析 注意到 $n\leq18$，因此可以考虑状压 DP。 设 $\textit{dp}_s$ 表示射死的猪的集合为 $s$ 时的方案数。（$s$ 放到状压的代码里面就是一个整数，二进制的第 $i$ 位表示猪 $i$ 是否被射死。） 那么考虑抛物线如何射死猪。 对于一条抛物线，如果射死一只猪，则有无穷多条；如果射死两只猪，则可以确定（因为抛物线形如 $y=a...

Posted by TH911 on May 17, 2025

题解：GKK 的游戏

题目见正文 | 最小生成树

洛谷自建题目链接 数据包 题目 题目描述 GKK 是一个喜欢环上游戏的男孩。 现在有一张 $n$ 个点组成的图，每个点的编号为 $0\sim n-1$。你有 $m$ 次操作，每一次操作有三个参数 $a,b,c$。操作的意义如下： 在编号为 $a+0,b+0$ 的点之间连一条边权为 $c+0$ 的边。 在编号为 $b+0,a+1$ 的点之间连一条边权为 $c+...

Posted by TH911 on May 17, 2025

题解：[NOIP 2015 提高组] 运输计划

洛谷P2680

题目传送门 题意分析 令最短时间为 $mid$。 那么我们显然可以二分枚举 $mid$，因为其具有单调性——$mid$ 越大，则可供选择的虫洞方案就越多。 那么考虑如何较为高效地判断 $mid$ 是否可行。 考虑到权值小于等于 $mid$ 的计划不需要考虑，那么虫洞所在边一定是其余计划的公共边。 则可以用树上差分求出这些公共边是哪些，然后枚举删除即可。 判断删去之后能否...

Posted by TH911 on May 16, 2025

树上差分

树上差分 记 $f_x$ 表示节点 $x$ 的父节点。 点差分 记 $a_x$ 表示节点 $x$ 的点权。 那么当我们想要在树上的某一段路径上的点都加上 $1$ 的时候，一个一个暴力做效率就太过于低下，因此可以考虑差分。 记 $d$ 表示 $a$ 的差分数组，即： \[d_x=a_x-\sum_{i\in son_x}a_i\] 这样，如果将 $p\sim q$ 路径上的所有点...

Posted by TH911 on May 16, 2025

题解：[NOIP 2018 提高组] 赛道修建

洛谷P5021

题目传送门 题意分析 对于这类求“最值的最值”的问题，很容易想到二分答案。 因此我们套路地想二分答案是否可行，即能否高效的判断最小赛道长度为 $\textit{mid}$ 时是否可行。 一个显然的贪心：赛道的长度如果大于等于 $\textit{mid}$，则应尽可能接近于 $\textit{mid}$。因为修建的太长了对于答案的贡献不变，反而会挤占其他赛道。 修建赛道，对于...

Posted by TH911 on May 11, 2025

题解：[NOIP 2018 提高组] 旅行

洛谷P5022

题目传送门 题意分析 $m=n-1$ 或 $m=n$，即这是一棵树或基环树。 显然，题意描述的小 Y 的路径会呈现为一棵树。 那么对于 $m=n-1$ 时的前 $60\%$ 的数据点，只需要 DFS 一遍记录序列即可，时间复杂度 $\mathcal O(n\log n)$，需要给边排序以保证字典序最小。 对于 $m=n$ 时，则会有一条边走不到，删去该边，剩余的部分构成一棵...

Posted by TH911 on May 9, 2025

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

要做一个优秀的 OIER

FRIENDS