2023.10.18 信息学日志
1. CF1689D Lena and Matrix
题目描述
-
- 数据范围：
\sum n \cdot m \leq 10^6 题目概况
来源：Codeforces
洛谷难度：蓝题
CF难度：
标签：枚举 最短距离
思路点拨
考虑每个点，只需要关注它到其他点曼哈顿距离的最大值，而实际上全局只会有
-
dis = x_1-x_2+y_2-y_1 -
dis = x_2-x_1+y_1-y_2 -
dis = x_2-x_1+y_2-y_1
设定
-
\min(x_2+y_2) -
\min(x_2-y_2) -
\max(x_2-y_2) -
\max(x_2+y_2)
先预处理出四至点，再暴力每个点到四至点的曼哈顿距离最大值的最小值（打擂台）.
预处理时间复杂度：
打擂台时间复杂度:
标签：双指针 ST表 贪心
思路点拨
-
毋庸置疑的是因为每个人的战力不同，所以通过双指针直接判定
a、b 数组是否一一对应.不对应直接-1 . -
此时
a 数组已经被b 数组元素切成了[l,r] 的区间，只需要考虑这样的区间该如何处理. -
设
p=r-l+1 以下分为2 种情况：-
-
k \leq p - 火球术代价比狂暴术代价优
\lfloor \frac{p}{k}\rfloor \cdot x + p \mod k \cdot y - 反之
x+(p-k)\cdot y
- 火球术代价比狂暴术代价优
-
-
完善，
a 数组区间最值用ST 表预处理维护
时间复杂度：
- ①：
\sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)==1] - ②：
\sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot \sum_{j=1}^{i}[\gcd(i.j)==1])-1) - ③：
\sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot\varphi(i) -1) - ④：
\sum _{p∈prime}2 \cdot(\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i))-1
所以可以使用线性筛预处理