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}...

题解:[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}^...

扫描线思想与算法实现

例题:洛谷P5490

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

题解: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$ 都包含...

题解:[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...

题解:[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...

题解:[NOIP2024] 树的遍历

洛谷P11363 | DP 思维题

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

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...

C++ 中 inline 与内联优化

inline 的玄学妙用

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

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

例题:洛谷 P4211 [LNOI2014] LCA

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