TH911 Blog

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

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

题解：[NOIP2022] 种花

洛谷P8865

题目传送门 题意分析 首先，观察样例解释，显然可以发现所谓的 F 就是 C 下面带了一段。 样例解释 四个 C- 形种花方案为： 1 2 3 4 **1 **1 **1 **1 *10 *10 *10 *10 **0 *** *00 *00 000 000 **0 *** 其中 * 表示在这个位置种花。注意 C 的两横可以不一样长。 类似的，...

Posted by TH911 on April 18, 2025

题解：[NOIP2020] 排水系统

洛谷P7113

题目传送门 题意分析 “不会发生污水形成环流的情况”，即无环，则整张图为一张有向无环图。 那么很容易想到拓扑排序，拓扑排序后统计贡献即可。 这道题目的难度可能就在于分数运算，但是也不难，写个结构体用 __int128 实现即可。 AC 代码 时间复杂度：$\mathcal O(n\log V)$。其中 $\mathcal O(\log V)$ 是求解最大公因数带来的。 ...

Posted by TH911 on April 18, 2025

题解：[NOIP 2017 提高组] 时间复杂度

洛谷P3952

题目传送门 大模拟 对于这种模拟题，其实题解也几乎没什么好说的——依据题意模拟即可。 注意事项 某些循环体不会被执行，其内部的循环体也不会被执行，不应当计入时间复杂度。 注意变量的上下界 $x,y$ 当 $x>y$ 时不会执行，$x=y$ 时为常数复杂度（包括 $x=y=n$）。 AC 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 1...

Posted by TH911 on April 12, 2025

题解：[NOIP 2017 普及组] 棋盘

洛谷P3956

题目传送门 DFS 暴力搜索 这是可以写的，从 $(1,1)$ 开始搜索，当搜索到 $(m,m)$ 的时候结束，记录答案。 设 $dfs(i,j,step,0/1)$ 表示搜索到 $(i,j)$，已经花费了 $step$ 金币，能否使用魔法。 从节点 $(i,j)$ 到达的节点 $(i’,j’)$ 的分支有三种： $(i,j),(i’,j’)$ 颜色相同，下...

Posted by TH911 on April 12, 2025

题解：The Number Games

CF980E

题意分析 给定一棵 $n$ 个节点的树，第 $i$ 个节点的权值为 $2^i$。从中删除 $k$ 个节点，使得剩下 $n-k$ 个节点联通且权值和最大。 求删除哪 $k$ 个节点。 贪心性质 权值为 $2^i$ 毫无疑问是极其特殊的，因此我们可以考虑有没有一些性质。 显然，$2^x>2^{x-1}+2^{x-2}+2^{x-3}+\cdots+2^{0}$，因此我们可以考虑贪...

Posted by TH911 on April 12, 2025

题解：[NOIP 2015 提高组] 子串

洛谷P2679

题目传送门 DP 状态设计 因为需要满足无后效性原则，因此 DP 考虑的肯定是两段前缀。 设 $f_{i,j,p,0/1}$ 表示从 $A$ 中取前 $i$ 个字符（第 $i$ 个字符选或不选）取 $p$ 段，匹配 $B$ 中前 $j$ 个字符的方案数。 DP 状态转移 $A_i=B_j$ 时。 显然，有 $f_{i,j,p,0}=f_{i-1,j...

Posted by TH911 on April 11, 2025

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

要做一个优秀的 OIER

FRIENDS