TH911 Blog

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

题解：[NOIP2023] 天天爱打卡

洛谷P9871

题目传送门 记 $[l,r,w]$ 表示 $l\sim r$ 每天都跑步，小 T 请用户吃饭造成的提高为 $w$。 测试点 $1\sim9$ 一个非常显然的 $\mathcal O(nk)$ 的 DP。 设 $\textit{dp}_{i,j}$ 为在第 $i$ 天结束时连续打卡了 $j$ 天的最大能量值。 则有： \[\begin{aligned} \textit{dp...

Posted by TH911 on August 5, 2025

题解：[NOIP2024] 树的遍历

洛谷P11363 | DP 思维题

题目传送门 一道很好的 DP 思维题。 本文中「生成树」指代按照题目中方式生成的新树。 特殊性质 $k=1$ $k=1$ 是简单的。 任意一个点，其临边都是树上的一条新链。 设 $d_x$ 为 $x$ 的度数，则答案为： \[\prod_{i=1}^n(d_i-1)!\] 期望得分：$\text{24pts}$。 特殊性质 A 发现原图为一条链，可能的生...

Posted by TH911 on August 5, 2025

C++神奇错误之 bool 与垃圾值

inline 的玄学妙用

参见此处。 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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 6...

Posted by TH911 on August 4, 2025

C++ 中 inline 与内联优化

inline 的玄学妙用

本文部分内容转载于此处。原文是一篇非常好的文章，值得推荐。 受我的贴子和原文作者的帖子启发。 「inline 关键字是否可以促进编译器的内联优化」是一个争议较大的话题。经过查询、讨论和实验，得出以下结论。 大多数情况下，inline 关键字对性能优化没有帮助，但是也不会降低性能。 但是在部分编译环境下，inline 关键字可以明显促进编译器的内联优化，但是也有其他...

Posted by TH911 on August 3, 2025

全局平衡二叉树维护链上信息

例题：洛谷 P4211 [LNOI2014] LCA

本文中的「重子节点」、「轻边」等术语定义同重链剖分。 全局平衡二叉树，即在重链剖分的基础之上，使用静态二叉树来维护重链，从而得到的常数优秀、复杂度 $\mathcal O(\log n)$ 的数据结构。 全局平衡二叉树可以用于在 $\mathcal O(\log n)$ 的时间内处理树上链修改/查询，可以代替树剖维护链上信息。（其实也可以维护子树信息，但是我不会。）...

Posted by TH911 on July 29, 2025

动态 DP 详解

DDP | 例题：洛谷P4719,P4513 SPOJ GSS3

例题链接。 本文参考了部分资料，参见文末。 如果没有特殊声明，本文中所有的矩阵乘法均为广义矩阵乘法，请不要混淆。 DDP（动态 DP）可用于解决一类带修改操作的 DP 问题。一般用来解决树上带有点（边）权修改的 DP 问题。 引入 以较为简单的最大子段和问题来引入。 例题：SPOJ GSS3 - Can you answer these quer...

Posted by TH911 on July 26, 2025

树状数组优化 DP

前/后缀最值

树状数组优化 DP 常规的区间和就不讨论了，本文主要讨论树状数组维护前后缀最值。 Acwing3662 最大上升子序列和 [NOIP 2013 提高组] 花匠 树状数组可以用于维护前后缀最值。 维护前缀最大值： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 struct bitPre{ int t[N+1...

Posted by TH911 on July 25, 2025

NOIP 二十年 DP 训练总结

2005 至 2024 NOIP 动态规划真题

持续更新中，对于较为简单的题目，会直接给出题解。对于较为复杂的题目，会给出核心摘要及详细题解的链接。 题目主要来源于[此处](https://www.luogu.com.cn/problem/list?type=luogu&page=1&tag=3,129,139,141,144,152,323,435,443,444,4...

Posted by TH911 on July 25, 2025

题解：[ARC170C] Prefix Mex Sequence

AtCoder ARC170C

题目传送门 题意分析 对于 $s_i=1$ 的 $a_i$，显然 $a_i$ 时由 $a_1,a_2,\cdots,a_{i-1}$ 确定的唯一的数。 当 $n\leq m$ 时，最大的 $\operatorname{mex}$ 的值一定不会超过 $m$。故此时所有 $s_i=0$ 的 $a_i$ 都可以在 $\set{0,1,\cdots,m}\setminus\set{\o...

Posted by TH911 on July 24, 2025

题解：[ROIR 2025] 寻找宝藏

洛谷P11700 | DP

题目传送门 题意分析 本文中记 $x_i$ 为第 $i$ 列的扫描结果，即 $x_i$ 为原题中 $b_i$。同时，以下推导均不考虑取模。 DP 状态设计 注意到 $k\leq7$，且是计数类问题，因此考虑与 $k$ 有关的涉及状压的 DP。 如图，扫描仪的扫描区域其实就可以视作一个类似于三角形的区域在图上向右滑动。而第 $i$ 列的扫描结果与第 $i-1$ 列的扫描结...

Posted by TH911 on July 23, 2025

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

要做一个优秀的 OIER

FRIENDS