TH911 Blog

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

题解：[NOIP 2017 提高组] 逛公园

洛谷P3953

题目传送门题意分析记忆化搜索需要最短路，先可以通过 Dijkstra $\mathcal O\left((n+m)\log m\right)$ 求出 $1\sim i$ 的最短路长度 $dis_i$。分析题目条件，“方案数无穷多”，即存在 $0$ 环，如何判断 $0$ 环下文会讲。合法路线显然非常大，因此暴力枚举是行不通的，考虑 DP 递推求解。设 $dp_{...

Posted by TH911 on May 5, 2025

题解：Memory and Scores

CF712D

题目传送门题意分析 $A,B$ 两个人的分数是独立的，也就是说，这两个人的分数不会相互影响。那么我们就可以求出两个人的分数的方案数，然后把 $A$ 的分数大于 $B$ 的分数的方案数通过乘法原理计数即可。记 $A_{i,j}$ 表示 $A$ 在第 $i$ 轮分数为 $j$ 的方案数。（$B$ 同理可得。）则有 $A_{0,a}=1$，这也是边界。考虑到每次的增量...

Posted by TH911 on May 4, 2025

题解：[NOIP 2016 提高组] 换教室

洛谷P1850

题目传送门 DP $n,m\leq2000$，可以考虑 DP。状态设计 DP 需要满足最优子结构与无后效性原则，因此 DP 方程里的参数需要能够转移。设 $dp_{i,j,k\in\lbrace0,1\rbrace }$ 表示处理到第 $i$ 个时间段，申请换了（不是实际换了几个） $j$ 个教室，第 $i$ 个教室是否更换的答案。状态转移期望，即每种情况的贡献...

Posted by TH911 on April 25, 2025

题解：[NOIP2024] 遗失的赋值

洛谷P11362

题目传送门题意分析首先，$n$ 个变量显然会被 $m$ 条一元限制切割为若干段。不考虑每一段的边界情况，段内一个变量的方案数显然为 $v^2$。段内总方案数显然仅仅与段的长度有关，设长度为 $x$ 的段的方案数为 $f_x$。考虑求出 $f_x$：如果第一个变量与左端点相同，段内方案数显然为： \[v\cdot f_{x-1}\] ...

Posted by TH911 on April 19, 2025