2A
题意（gym105158C）：
给定正整数序列 \(\{a\}\)，构造一个 \(\mathbb Z \to \mathbb Z\) 的映射 \(f\)，满足 \(\forall i < n,\ f(a_{i}) \le f(a_{i + 1})\)。最小化 \(f(x) \ne x\) 的 \(x\) 数量。
数据范围：\(1 \le n \le 10^6,\ 1 \le a_i \le n\)。
对于 \(i \notin \{a\}\)，显然是可以构造 \(f(i) = i\)，对结果没有影响。
对于 \(i \in \{a\}\)，设其第一次和最后一次出现的位置为 \(l_i, r_i\)。由于 \(f(a_{l_i}) = f(a_{r_i})\)，因此 \(\forall j \in [l_i, r_i], f(a_j) = f(i)\)。
把若干相交 \(l, r\) 缩成一段，使得两两连续段所包含颜色不同，一个连续段只能包含一个元素。
最大化不动点个数，转化为求最长不降子序列长度，时间复杂度 \(O(n \log n)\)。submission
A
题意（gym105158D）：
给定平面上若干整点，从中任选两点，求他们的曼哈顿距离比上欧几里得距离的最大/最小值。
数据范围：\(n \le 1\times 10^6\)，保证没有点重合。
\[\dfrac{a + b}{\sqrt{a^2 + b^2}} = \sin\theta + \cos \theta = \sqrt2\sin(\theta + \dfrac{\pi}{4}) \]\(PQ\) 与 \(x\) 轴夹角越接近 \(45^{\circ}\) 或 \(135^{\circ}\)，答案越大。
越水平或垂直答案越小。
如何使两点夹角最接近水平？其他角度可以通过旋转坐标系化归为水平的情况。
按纵坐标排序，只有相邻点对可能产生贡献，其他情况不优。
再考虑如何旋转坐标系。
由于只需要考虑纵坐标的相对大小，我们可以把 \(\begin{bmatrix}x\\y\end{bmatrix}\) 左乘 \(\begin{bmatrix}1&1\\-1& 1\end{bmatrix}\) 得到新坐标 \(\begin{bmatrix}x + y\\x - y\end{bmatrix}\)，等价于顺时针旋转 \(45^{\circ}\)。
同理顺时针旋转 \(135^{\circ}\)，\(\begin{bmatrix}x - y\\ x + y\end{bmatrix}\)。
因此只要按照 \(x - y\) 和 \(x + y\) 排序即可，时间复杂度 \(O(n\log n)\)。
B
题意：给出一棵树，对于每个 \(k \in \left[0, \lfloor\frac{n- 1}{2}\rfloor\right]\) 求解以下问题：
在所有 \(2^{n} - 1\) 种非空点集中，有多少大小为 \(m\) 的点集满足 \(\max_{i, j\in S} \text{dist}(i, j) \le 2k\)。
数据范围：\(1 \le m \le n \le 5000\)。
结论：若树上所有边边权均为正，则树的所有直径中点（边）重合。
若直径长为偶数：
假设存在两条不同中点的直径 \((s_1, m_1, t_1),\ (s_2, m_2, t_2)\)，显然满足 \(d(s_1, m_1) = d(m_1, t_1) = d(s_2, m_2) = d(m_2, t_2)\)。
其中 \(d(s_1, t_2) = d(s_1, m_1) + d(m_1, m_2) + d(m_2 , t_2) > d(s_2, t_2)\)，矛盾。
奇数的情况类似。
也就是一个点集所构成的（虚）树直径交于一点。
枚举这个中点 \(u\)，统计：\(\forall_{v \in S} \text{dist}(u, v) \le k\)，且至少有两个等于 \(k\) 的点分布在不同子树的 \(S\) 个数。
做一下简单容斥即可。
对于直径为奇数的情况，可以枚举中边，类似方法统计。时间复杂度 \(O(n^2)\)。
C
D
题意（CF1466H）：
标签：25,begin,le,end,题意,CSP2024,circ,bmatrix From： https://www.cnblogs.com/Luxinze/p/18459736