TH911 Blog

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

题解：[CSP-S 2024] 染色

P11233

题目传送门 题意分析

Posted by TH911 on August 12, 2025

线段树优化建图

例题：CF786B

例题链接 给定一张 $n$ 个点的图，完成 $q$ 次建边操作，每次建边有权值： 建有向边 $v\rightarrow u$。 对于 $i\in[l,r]$，建边 $v\rightarrow i$。 对于 $i\in[l,r]$，建边 $i\rightarrow v$。 求最终图的最短路。 满足 $1\leq n\leq10^5$...

Posted by TH911 on August 12, 2025

题解：[JOISC 2022] 监狱

洛谷P9520

题目传送门 朴素图论建模 记 $s_x,t_x$ 分别表示囚犯 $x$ 的起点、终点，$\set{s_x\rightarrow t_x}$ 表示囚犯 $x$ 走过的点集。 对于囚犯 $u,v$： 若 $s_u\in\set{s_v\rightarrow t_v}$，则 $u$ 比 $v$ 先走，否则会被挡住。 若 $t_u\in\set{s_v\rightarrow...

Posted by TH911 on August 12, 2025

题解：[GDCPC 2024] 图

洛谷P13356

题目传送门 充分发扬人类智慧。 题意分析 首先考虑到 $k=\left\lceil\dfrac m{n-1}\right\rceil$，这应当有一些性质，因为 $k$ 并不是一个输入的给定值。 考虑到 $n-1$ 应当有什么用，注意到 $n-1$ 条边会构成一棵 $n$ 个节点的树。 因此启发我们可以考虑将边分组，维护 $k$ 组。理想情况是前 $k-1$ 组均有 $n...

Posted by TH911 on August 12, 2025

题解：[Vani有约会] 雨天的尾巴 /【模板】线段树合并

洛谷P4556

题目传送门 树链剖分做法 显然可以树链剖分维护链上信息，操作离线，按 $z$ 从小到大操作即可。 时间复杂度 $\mathcal O\left(m\log^2n\right)$。 线段树合并做法 对于每一个点都开一个动态开点权值线段树记录收到的救济粮数量。 操作路径可以进行树上差分转化为 $4$ 次操作。 即修改 $x\sim y$ 的路径时，修改四个点： $x...

Posted by TH911 on August 11, 2025

题解：[JOISC 2022] 京都观光

洛谷P9521

题目传送门 题意分析 考虑从左上角 $(i_1,j_1)$ 走到右下角 $(i_2,j_2)$，只拐一次弯。 有两种走法： 先向右，再向下，距离为： \[a_{i_1}(j_2-j_1)+b_{j_2}(i_2-i_1)\] 先向下，再向右，距离为： \[a_{i_2}(j_2-j_1)+b_{j_1}(i_2-i_1)\] ...

Posted by TH911 on August 11, 2025

题解：[集训队互测 2024] 长野原龙势流星群

洛谷P12479

题目传送门 题意分析 发现平均值不好维护，因此可以维护连通块的大小与权值和。 假设得到了以 $x$ 为根的连通块的答案，那么如果存在一个连通块包含了这个连通块，一定要包含 $x$ 的父节点。因此在得出 $x$ 的答案后，$x$ 连通块的作用等价于其父节点 $\textit{father}_x$ 与 $x$ 的连通块构成的大连通块。 因此考虑一种数据结构，能够维护这种操作，考虑...

Posted by TH911 on August 11, 2025

题解：[北大集训 2021] 基因编辑

洛谷P8986

题目传送门 本题解主要用于翻译题面。 难度在于读题 题面说了一大堆 HD1048576d 外星人、外星生命的基因序列、基因编辑技术等内容，以至于读题非常不容易。考虑如何去有条理地、清晰地正确理解题目。 输入给出了正整数序列 $s_1,s_2,\cdots,s_n$，和一个数对 $(l,r)$。 先找与之相关的信息。 对于一段长度为 $n$ 的外星生命的基因序列（...

Posted by TH911 on August 11, 2025

题解：[Ynoi2011] ODT

洛谷P5314

题目传送门 题意分析 维护链上信息，显然可以树链剖分做到 $\mathcal O\left(\log n^2\right)$ 修改。 但是需要查询 $x$ 的子节点、自己、父节点点权第 $k$ 小。 延续树剖的思路，将重子节点单独处理，数据结构维护轻子节点点权。 这样修改的时候只需要修改链顶 $\textit{top}_x$ 的父节点 \(\textit{father}_{...

Posted by TH911 on August 10, 2025

题解：[HNOI2010] 弹飞绵羊

洛谷P3203

题目传送门 题意分析 其实用 LCT 可以很好维护，但是我们并不会 LCT。 因此考虑一些其他的数据结构来维护。发现并没有什么特别适合的数据结构，考虑分块。 记 $\textit{step}_i$ 表示 $i$ 跳出块的步数，$\textit{to}_i$ 表示跳出到了哪里。 按照 $\sqrt n$ 为块长分块。记 \(\operatorname{pos}(i),\ope...

Posted by TH911 on August 10, 2025

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

要做一个优秀的 OIER

FRIENDS