TH911 Blog

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

题解：[NOI2004] 郁闷的出纳员

洛谷P1486

题目传送门 题意分析 给定 $a_1,a_2,a_3,\cdots,a_n$，对于每一个 $a_i$（$1<i\leq n$），在 $a_1,a_2,\cdots,a_{i-1}$ 中找一个 $a_j$，使得 $\sum\vert a_i-a_j\vert$ 最小。 即找 $a_i$ 的前驱与后继。 很容易想到平衡树维护。 AC 代码 1 2 3 4 5 6 7 8...

Posted by TH911 on January 21, 2025

题解：[HNOI2002] 营业额统计

洛谷P2234

题目传送门 题意分析 给定 $a_1,a_2,a_3,\cdots,a_n$，对于每一个 $a_i$（$1<i\leq n$），在 $a_1,a_2,\cdots,a_{i-1}$ 中找一个 $a_j$，使得 $\sum\vert a_i-a_j\vert$ 最小。 即找 $a_i$ 的前驱与后继。 很容易想到平衡树维护。 $\text{Updated ...

Posted by TH911 on January 21, 2025

题解：平均数

洛谷P1404

题目传送门 $\mathcal O\left(n^2\right)\ \text{70pts}$ 做法 暴力枚举左右边界。 参考代码 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 //#include<bits/s...

Posted by TH911 on January 21, 2025

题解：[NOI2005] 维护数列

题解：数列 | 洛谷P2402,P2710

考虑到P2710 数列和P2042 [NOI2005]维护数列的区别仅仅是一个可以被转换为其他操作的操作和数组大小，放到一篇。 题意分析 需要维护的操作有： 区间插入 区间删除 区间翻转 区间覆盖 区间求和 单点查询 求区间最大子段和 我们可以通过平衡树 FHQ Treap 来维护区间信息。 FHQ Treap 维护区间信息见 FHQ ...

Posted by TH911 on January 21, 2025

浅谈01Trie

例题：洛谷P10471,P4551

前置知识：Trie树 例题：最大异或对 给定 $a_1,a_2,a_3,\cdots,a_n$，求 $a_i\oplus a_j$ 的最大值，其中“$\oplus$”表示异或。 我们先分析一下：当什么时候，$a_i \oplus a_j$ 会尽可能大？ 显然，$a_i,a_j$ 在二进制下高位不同时会尽可能大，因为 $2^k>2^{k-1}+2^{k-2}+2^{k-3...

Posted by TH911 on January 19, 2025

AC 自动机详解

例题：洛谷P5357,P3808,P3796,P3966 | Trie树 & Trie图

例题链接：【模板】AC 自动机 AC 自动机（简单版） AC 自动机（简单版 II） [TJOI2013]单词 前置知识：KMP、Trie树。 什么是 AC 自动机 这不是一个能让你自动 AC 的机器 这不是一个能让你自动 AC 的机器。 给定文本串 $T$ 和多个模式串 $S_1,S_2,S_3,\cdots,S_n$，...

Posted by TH911 on January 19, 2025

题解：浏览器

洛谷P4932

题目传送门 题意分析 给定 $n$ 个点，每个点有权值 $x_i$。 对于整数 $u,v\in[1,n]$，若 $u\oplus v$ 在二进制下有奇数个 $1$，在 $u,v$ 间建边。 求最终边的数量。 $\mathcal O(n^2)$ 暴力做法 首先这个图明显就是个障眼法。 定义 $count(x)$ 表示 $x$ 的二进制上 $1$ 的个数，时间复杂度 $\m...

Posted by TH911 on January 18, 2025

题解：XOR Pairs

洛谷P11016

题目传送门 题意分析 我们先思考：什么样的两个 $x,y$，会满足 $x \oplus y>\max(x,y)$。 为了便于表述，令 $x>y$。 举个例子： 数值 $x$ 的最高位     $y$ 的最高位   $x$ ...

Posted by TH911 on January 18, 2025

题解：序列合并

洛谷P10512

题目传送门 题意分析 给定 $a_1,a_2,a_3,\cdots,a_n$，要求将相邻两项 $a_i,a_{i+1}$ 合并为 $a_i\ \vert \ a_{i+1}$，合并 $k$ 次。 求最后 $a_1\ \&\ a_2\ \&\ a_3\ \&\ \cdots\ \&\ a_{n-k}$ 的最大值。 显然，最后的每一个 $a_i$ ...

Posted by TH911 on January 18, 2025

题解：最大上升子序列和

AcWing 3662

题目传送门 题意分析 给定一个序列，求最大上升子序列和。注意不是最长上升子序列。 我们可以很容易得出一个 $\mathcal O(n^2)$ 的做法：枚举 $i\in [1,n]$ 和 $j \in [1,i-1]$，以 $a_i$ 为末尾的最大上升子序列和 $\textit{dp}_i$ 即满足 $a_j<a_i$ 的最大的 $\textit{dp}_j+a_i$。 ...

Posted by TH911 on January 18, 2025

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

要做一个优秀的 OIER

FRIENDS