A
source : CF1415D
考虑只有 \(30\) 个位,所有 \(n\) 足够大时一定存在三个元素相邻的两两最高位相等,除此以外直接 \(O(n^3)\) 暴力
B
source : CF1415E
归零 \(k\) 次相当于将原序列分成 \(k-1\) 个集合,每个集合显然相互独立,将 \(a_i\) 按降序排列,每一个贪心找到当前能加分最多的集合扔进去,可以优先队列维护
C
source : Gym104420C
考虑\(\begin{cases}|y|\le C_0+C_1\le|y|+2\\|k|\le C_0-C_1 \le |k|+2\end{cases}\)在 \(6\) 种长度中考虑分类构造合法的串,打擂台,注意细节
D
source : AT_arc159_d
显然选区间的一段后缀不会更劣,那么可以设计状态 \(dp_i\) 为包含 \(r_i\) 的 \(LIS\) 的最长长度
考虑从 \(j\) 转移过来,有两种转移:
- 区间 \(j\) 和区间 \(i\) 无交, \(dp_i = max_{r_j<l_i}\{dp_j+len_i\}\)
- 区间 \(j\) 和区间 \(i\) 有交, \(dp_i=max_{l_i\le r_j \le r_i} \{dp_j+r_i-r_j\}=max_{l_i\le r_j \le r_i} \{dp_j-r_j\}+r_i\)
线段树维护 \(dp_i,dp_i+r_i\) 的区间最大值即可
E
source : POJ2482 / P1502
典题,转化为以每个点为左下角的矩形交的 \(max\),然后就是简单扫描线
F
source : CF1864D
翻转操作的影响范围显然是以 \((i,j)\) 为顶点向下的等腰直角三角形,因此从上往下不会有操作顺序交叉的影响,考虑懒标记和标记下放
一个巧妙的标记方法是,对 \((i,j)\) 操作/下放标记时翻转 \((i,j),(i+1,j)\),给 \((i+1,j-1),(i+1,j+1),(i+2,j)\) 打标记,利用了类似二维前缀和的容斥方法
特判边界的操作方式
G
source : CF1184C2
曼哈顿距离小于 \(R\) 的点形成一个对角线平行坐标轴的正方形,不好维护怎么办
于是经典套路,旋转 \(45\) 度将曼哈顿距离转为切比雪夫距离,就可以做成 E 了
关于曼哈顿转切比雪夫的证明:
曼哈顿距离: \(|x_1-x_2|+|y_1-y_2|\)
切比雪夫距离: \(max\{|x_1-x_2|,|y_1-y_2|\}\)
考虑 \(|x| = max\{x, -x\}\),就有了一个绝对值到 \(max\) 的转化
(以下为 \(dis(x,y)\) 原点到 \((x, y)\) 的距离转化,容易推广到任意两点)
对于这两个 \(max\) 分类讨论,可以得到:
显然这个最终形式像极了切比雪夫距离的形式,于是就有了曼哈顿距离转切比雪夫距离的坐标系转换公式: \((x, y) \rightarrow (x+y,x-y)\)
这东西就是原坐标系旋转 \(45\) 度的 \((x,y) \rightarrow (\frac{(x+y)}{\sqrt2},\frac{(x-y)}{\sqrt2})\) 再放缩 \(\sqrt2\) 倍的公式