TH911 Blog

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

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

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

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

要做一个优秀的 OIER

FRIENDS