Throne

最近的一些比赛中经常用到树上 $LCA$ 的常见模型，这里整理一下几种做法和应用场景。

Problem I - Step

Problem B - Countless Me

分析

假设最优情况下，目标序列的每个值分别为：

$$x_1,x_2,\cdots,x_n$$

把原序列变成任意目标序列时，每个位置最多只需要一次操作，因此整体可以看作“构造一个更优的目标序列”。

D2. Reverse Card (Hard Version)

题意

给定两个正整数 $n,m$，计算满足条件的有序数对 $(a,b)$ 的数量：

思路简记

建图后，可以枚举每个点作为起点跑 Dijkstra。如果最短路过程中再次回到起点，就得到经过该点的一个最小环候选值；再结合题目给定的阈值判断答案。

Problem 1946D - Birthday Gift

分析

对于区间位运算，比较自然的做法是按位拆分，并从高位到低位分析 $x$ 的每一位。

记录一下 $blog 创建、换主题、部署和加速的大体流程。

扩展欧几里得用于求解形如 $ax+by=m$ 的不定方程，也常用于求逆元。

2021 CCPC 桂林 E - Buy and Delete

题目描述

Alice 和 Bob 在有向图 $G$ 上玩游戏。最初图中没有边，Alice 可以先购买一些边加入图中，购买总价不能超过 $c$。之后 Bob 每轮可以删除一个边集 $S$，要求只保留 $S$ 中的边时图是无环的。Bob 不断删除直到图中没有边。

Problem B - Martian Sunrise

题目描述

给定 $m$ 行音调，每行有 $7$ 个元素；再给定一行长度为 $n$ 的目标音调。每次可以从 $m$ 行中任选两行，作为当前可用的元素集合去匹配目标音调，求完成匹配所需的最少次数。

约束为 $1 \le m \le 16$，$1 \le n \le 10^4$。