TH911 Blog

题解：没有上司的舞会

洛谷P1352

题目传送门树形 DP 令 $dp_{x,i}$（$i\in{0,1}$）表示编号为 $x$ 的职员来或不来参加舞会的情况下，其子树内的最大快乐指数。那么，初始时就有 $dp_{x,0}=0,dp_{x,1}=r_x$，即只算其本身的贡献。对于节点 $x$ 的子节点 $y_1,y_2,y_3,\cdots,y_k$，该如何转移呢？先考虑 $dp_{x,1}$，因为上司...

Posted by TH911 on January 22, 2025

题解：最大子树和

洛谷P1122

题目传送门题意分析给定一棵无根树，你可以从中去掉一些子树（但不能使原树为空），求最后剩下的树的最大权值和。最大子段和问题我们先回顾一下最大子段和。其解法是令 $dp_i$ 表示以 $a_i$ 结尾的最大子段和，那么就有： \[dp_i=\max(dp_{i-1}+a_i,a_i)\] 即接到前面一项和不接到前面一项之后两种情况。最大子树和树——半线性结...

Posted by TH911 on January 22, 2025

Splay树详解

例题：洛谷P3369

前置知识：平衡树。例题链接。例题加强版链接。您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：插入一个数 $x$。删除一个数 $x$（若有多个相同的数，应只删除一个）。定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。查询数据结构中排名为 $x$ 的数。求 $x$ ...

Posted by TH911 on January 22, 2025

浅谈平衡树

各类平衡树概述

平衡树是什么二叉搜索树 BST BST，二叉搜索树，又名二叉查找树、二叉排序树，是一种特殊的二叉树。能够保证中序遍历是有序的。最理想的情况下，BST 的树高为 $\mathcal O(\log n)$，但是可能会变成 $\mathcal O(n)$。维持树高一棵较为理想的 BST：但是可能会因为输入顺序等原因变为：这样就很不好。因此，我们可以通过各种平衡...

Posted by TH911 on January 21, 2025

题解：[USACO15FEB] Censoring S

洛谷P4824

题目传送门前置知识：KMP 又水一道提高+/省选−。强化版：[USACO15FEB] Censoring G。弱化版很明显，可以使用 [USACO15FEB] Censoring G 的代码，将数组大小从 $10^5$ 改为 $10^6$ 即可。参考代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

Posted by TH911 on January 21, 2025

题解：[USACO15FEB] Censoring G

洛谷P3121

题目传送门前置知识：AC 自动机又水一道提高+/省选−。弱化版：[USACO15FEB] Censoring S。题意分析在文本串 $t$ 中查找模式串 $s_1,s_2,s_3,\cdots,s_n$，从 $t$ 中删除所有可能查找到的 $s_i$ 并输出删除之后的 $t$。多字符串匹配问题，一眼 AC 自动机。但是这道题目唯一可能有困惑的...

Posted by TH911 on January 21, 2025

一点写 Markdown 时常用的 html 代码

洛谷难度评级入门 1 入门 普及− 1 普及− 普及/提高− 1 &l...

Posted by TH911 on January 21, 2025

题解：[Codechef REBXOR] Nikitosh and xor

01Trie求异或 | 前缀与后缀

原题传送门然而原题打不开…… 所以：洛谷镜像 $1$ 洛谷镜像 $2$ 水一道提高+/省选− 和一道省选/NOI−。附：原题 pdf 文件题意分析如果是只求一个区间，那么问题就会十分简单。因为异或满足结合律，因此可以构造序列 $a$ 的前缀异或和，然后和最大异或对一样 $\mathcal O\left(n\log n\right)$ 使用0...

Posted by TH911 on January 21, 2025

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

TH911 Blog

题解：没有上司的舞会

洛谷P1352

题解：最大子树和

洛谷P1122

Splay树详解

例题：洛谷P3369

浅谈平衡树

各类平衡树概述

题解：[USACO15FEB] Censoring S

洛谷P4824

题解：[USACO15FEB] Censoring G

洛谷P3121

一点写 Markdown 时常用的 html 代码

题解：[Codechef REBXOR] Nikitosh and xor

01Trie求异或 | 前缀与后缀

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

洛谷P1486

题解：[HNOI2002] 营业额统计

洛谷P2234

FEATURED TAGS

ABOUT ME

FRIENDS