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

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

题解:平均数

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

题解:[NOI2005] 维护数列

题解:数列 | 洛谷P2402,P2710

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

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

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

题解:浏览器

洛谷P4932

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

题解:XOR Pairs

洛谷P11016

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

题解:序列合并

洛谷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$ ...

题解:最大上升子序列和

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