TH911 Blog

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

题解：[POI 2015] LAS

洛谷P3584 | DP

题目传送门 题意分析 发现， $c_i$ 的限制比较多，因此针对此进行 DP。 设 $\textit{dp}{i,j},j\in\set{1,2,3,4}$ 表示食物 $i$ 的状态为 $j$ 的合法状态是从 $\textit{dp}{i-1,\textit{dp}{i,j}}$ 转移得来。同时，规定 $\textit{dp}{i,j}$ 有值表示合法，没有值表示不合法。 那...

Posted by TH911 on July 23, 2025

题解：Sam 数

洛谷P2106 | 矩阵快速幂优化 DP

题目传送门 朴素数位 DP 一个显然的 DP：设 $\textit{dp}_{i,j},i\in[1,k],j\in[0,9]$ 为 $i$ 位且最高位为 $j$ 的 Sam 数的个数。 则有： \[\textit{dp}_{i,j}=\sum_{\max(j-2,0)}^{\min(j+2,9)}\textit{dp}_{i-1,j}\] 最终答案 $\textit{an...

Posted by TH911 on July 22, 2025

题解：[HAOI2011] Problem b

P2522 | 莫比乌斯反演

题目传送门 题意分析 首先写出答案： \[\textit{ans}=\sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]\] 这种涉及到 $\gcd$ 的题目，一般都考虑莫比乌斯反演。 不妨令 $b<d$，有： \[\begin{aligned} \textit{ans}&=\sum_{i=\lceil\frac ak\rceil}^{...

Posted by TH911 on July 19, 2025

题解：Square Subsets

CF895C | 状压DP

题目传送门 题意分析 发现一个神奇的东西：$a_i\leq70$。值域如此之小，一定可以利用。因此考虑与值域有关的做法。 寻找完全平方数，则其所有质因子的指数均为偶数。 可以发现，$[1,70]$ 中的质数有且仅有 $19$ 个，可以考虑从此方面入手。 考虑影响是否为完全平方数的仅仅是质因子的指数的奇偶性，因此可以考虑状压 DP。 记第 $i$ 个质数为 $p_i,p_1...

Posted by TH911 on July 19, 2025

题解：[COTS 2024] 双双决斗 Dvoboj

洛谷P10680 | 动态单点修改ST表 | 阈值分治

题目传送门 题意分析 首先注意到一个非常特殊的性质，区间查询形如 $\left[l,l+2^k-1\right]$，长度为 $2^k$。 其次，单点修改很简单，区间查询较为复杂。 所以，考虑使用相关数据结构和算法维护。 考虑 ST 表，这可以很好的维护长度为 $2^k$ 的区间信息。记 $\left[l,l+2^k-1\right]$ 的答案为 $\textit{st}_{...

Posted by TH911 on July 18, 2025

多项式学习笔记

FFT/NTT

多项式乘法 本部分主要介绍 傅里叶变换 及 快速傅里叶变换（FFT）等在 OI范围内 的应用。 参考 Blog 参考 Blog 参考 Blog 参考文章 本文会简要介绍 FFT 的原理、思想，涉及诸如 复平面、平面向量 等数学内容，文中会简要介绍。 FFT 快速傅里叶变换 傅里叶变换的本质就是将一个多项式在 系数表示法 和 点值表示法 之间转换。 FFT...

Posted by TH911 on July 17, 2025

C++神奇错误之vector扩容导致引用失效

变量更改

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 67 68 69...

Posted by TH911 on July 16, 2025

题解：[FJOI2016] 建筑师

洛谷P4609 | 第一类斯特林数

题目传送门 题意分析 首先，高度为 $n$ 的建筑是不会被挡住的。 剩下的建筑即 $n-1$ 个。将这 $n-1$ 个建筑划分为 $A+B-2$ 个圆排列即可，每个排列内最高的建筑为起始端。 只需要考虑在 $n$ 的左侧还是右侧，因此乘上一个组合数。 故，答案为： \[\begin{bmatrix}n-1\\A+B-2\end{bmatrix}\dbinom{A+B-2}...

Posted by TH911 on July 16, 2025

题解：SP7363 TREESUM - Tree Sum

洛谷SP7363 | 斯特林数展开下降幂 | 换根 DP

题目传送门 其实和[集训队互测 2011] Crash 的文明世界是差不多的。 题意分析 树上问题 首先，$n$ 个点 $n-1$ 条边，显然是一个树。 设 $\operatorname{dist}(i,j)$ 表示以 $i$ 为根节点时，$j$ 的深度。不难发现这其实就是任意节点为根节点时，$i,j$ 之间的树上距离加 $1$。因此令 $\operatorname{d...

Posted by TH911 on July 16, 2025

题解：[POI 1997] 跳

洛谷P5940 | 斐波那契数列

题目传送门 题意分析 观察棋子的跳法，不难想到斐波那契数列（本文中“斐波那契数列”均将下标视为无限延伸）。 设斐波那契数列第 $i$ 项为 $f_i$，满足 $f_i=f_{i-1}+f_{i-2}$。 因此可以想到每一个位置都对应斐波那契数列中的某一项。设位置 $i$ 的棋子数量为 $\textit{cnt}_i$。 则两种跳法对应： 向左跳： \[\...

Posted by TH911 on July 15, 2025

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

要做一个优秀的 OIER

FRIENDS