TH911 Blog

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

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

题解：[NOIP2023] 双序列拓展

洛谷P9870

题目传送门 测试点 $1\sim7$ 考虑将问题转化。 对于 $\forall1\leq i,j\leq l_0$ 均有 $(f_i-g_i)(f_j-g_j)>0$，即对于 $\forall1\leq i\leq l_0$，有 $f_i>g_i$ 或 $f_i<g_i$。 不妨设 $f_i=x_a,g_i=y_b$。则对于 $f_{i+1},g_{i+1}...

Posted by TH911 on August 9, 2025

题解：[NOIP2021] 方差

洛谷P7962

题目传送门 测试点 $1\sim8$ 首先，题目的操作即交换差分。 将答案变式： \[\begin{aligned} n^2\cdot\dfrac1n\sum_{i=1}^n\left(a_i-\overline{a}\right)^2&=n\sum_{i=1}^n\left(a_i-\overline{a}\right)^2\\ &=n\sum_{i=1}^...

Posted by TH911 on August 9, 2025

扫描线思想与算法实现

例题：洛谷P5490

例题链接 给定平面直角坐标系内 $n$ 个四边平行于坐标轴的矩形，求其面积并。第 $i$ 个矩形的左下角和右上角分别为 $(x_{1,i},y_{1,i}),(x_{2,i},y_{2,i})$。 扫描线思想 扫描线，顾名思义，就是模拟一条线在平面上扫来扫去，从而得出答案。 这一般用于图特别大以致于无法存储的情况。 如图，图中描绘的就是扫描线从下至上扫过的情况。当坐...

Posted by TH911 on August 9, 2025

题解：AND Sorting

CF1682B

题目传送门 第一发橙题题解。 记位运算 & 为 $\&$。 $T$ 次询问，每次询问给出的序列都是 $0\sim n-1$ 的排列。记排列为 $a_1,a_2,a_3,\cdots,a_{n-1}$。 本题所具有核心性质便是：所有需要更改位置的数均进行了一次 $\&$ 操作。 也就是说，所有这些满足 $a_i\neq i-1$ 的 $a_i$ 都包含...

Posted by TH911 on August 8, 2025

题解：[NOIP 1998 提高组] 拼数

洛谷P1012

题目传送门 题意分析 容易发现，$n$ 个数 $a_1,a_2,a_3,\cdots,a_n$ 首尾相接，无论如何排列，最终得到的数 $x$ 的位数是一定的。 那么当 $x$ 的位数一定时，决定 $x$ 的大小的便是 $a_1,a_2,\cdots,a_n$ 的排列顺序。贪心的思路便是字典序尽可能地大。正确性是显然的。 注意不是越大的 $a_i$ 就越前。例如 $a=\lan...

Posted by TH911 on August 8, 2025

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

要做一个优秀的 OIER

FRIENDS