TH911 Blog

题解：叶子的染色

洛谷P3155

题目传送门题意分析注意无色节点不是白色节点。给定一棵 $m$ 个节点的无根树并指定 $n$ 个叶子节点。规定根节点到叶子节点 $i$ 的路径上深度最大的有色节点的颜色为 $c_i$，保证根节点的度数大于 $1$。求最少染色节点数。树形 DP 状态设计暂不考虑因为根节点不同而产生的影响，后文会证明根节点的不...

Posted by TH911 on January 22, 2025

题解：消息传递

洛谷P2018

题目传送门加强版数据包加强版数据包满足 $2\leq n\leq 200000$，需要使用 $\mathcal O\left(n\log n\right)$ 做法。题意分析给定一棵无根树，最开始花费 $1$ 时刻可以选择一个节点告知一条消息，每一个时刻每一个已知消息的节点都可以告知其他一个节点，求消息传遍整棵树的最短时间和最开始能选择的节点有哪些。 $\ma...

Posted by TH911 on January 22, 2025

题解：没有上司的舞会

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

TH911 Blog

题解：叶子的染色

洛谷P3155

题解：消息传递

洛谷P2018

题解：没有上司的舞会

洛谷P1352

题解：最大子树和

洛谷P1122

Splay树详解

例题：洛谷P3369

浅谈平衡树

各类平衡树概述

题解：[USACO15FEB] Censoring S

洛谷P4824

题解：[USACO15FEB] Censoring G

洛谷P3121

一点写 Markdown 时常用的 html 代码

题解：[Codechef REBXOR] Nikitosh and xor

01Trie求异或 | 前缀与后缀

FEATURED TAGS

ABOUT ME

FRIENDS