今天学习了LCA算法的两种做法，tarjan和树上倍增(本质上是暴力求解的优化)。 tarjan求解LCA 该算法利用并查集缩点，离线求每个询问的两点LCA。 首先将所有点对相互储存在树上(如果要求点 $x$ 和点 $y$ 的LCA，那么将 $y$ 存在 $x$ 中作为一次询问，将 $x$ 也存在 $y$ 中)，然后对树进行一次后序遍历。 在后序遍历过程中，每访问一个点，需要遍历该点的所...

vp Codeforces Round 881 (Div. 3) A 题目大意 给定一个数列，对这个数列上的每个数染色，对于每种颜色，染色的花费是 $该颜色的最大数-最小数$ ，求染色总花费的最大值。 思路 贪心，每种颜色只染两个数并使这两个数的差尽量大即可，可以排序后从左右两边同时进行染色。 代码 int n, a[55], l, r; void solve() { ...

这篇博客主要是讲述作者在 CodeForces 的一道题目 CF1819B The Butcher 的解题过程。在解题思路方面，文章提到了需要讨论两种情况切割出一个长最大的矩形或者切割出一个宽最大的矩形，并递归判断剩余小矩形是否满足构成大矩形的条件。在实现方面，作者给出了具体的代码实现，并使用了 STL 中的 vector 和 sort 等常用函数。最后，文章总结了这道题目的时间复杂度和解题...

这篇博客主要介绍了如何使用动态规划解决 Codeforces 题目 CF1842C “Tenzing and Balls”，并提供了优化思路和完整的代码实现。 题意 给定一个长度为 ${n}$ 的数列，可以选择两个相同的数，并将它们和它们之间的所有数删除。询问最多能删除多少个数。 思路 用 $dp[i]$ 表示数列前 $i$ 个元素最少能保留的个数。对于数列的前 $i$ 项构成的子列...