2023.10.18 信息学日志

信息学日志"/>

2023.10.18 信息学日志

1. CF1689D Lena and Matrix

题目描述

• n ⋅ m n \cdot m n⋅m 的矩阵，求矩阵上任意一点坐标使得到矩阵上的关键点曼哈顿距离最大值最小。
• 数据范围： ∑ n ⋅ m ≤ 1 0 6 \sum n \cdot m \leq 10^6 ∑n⋅m≤106

题目概况

来源：Codeforces

洛谷难度：蓝题

CF难度： 1900 1900 1900

标签：枚举 最短距离

思路点拨

考虑每个点，只需要关注它到其他点曼哈顿距离的最大值，而实际上全局只会有 4 4 4 个点真正会影响最大值。

d i s = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ dis = |x_1-x_2|+|y_1-y_2| dis=∣x1​−x2​∣+∣y1​−y2​∣ 将绝对值拆开分为4种情况,如下：

• d i s = x 1 − x 2 + y 1 − y 2 dis = x_1-x_2+y_1-y_2 dis=x1​−x2​+y1​−y2​

• d i s = x 1 − x 2 + y 2 − y 1 dis = x_1-x_2+y_2-y_1 dis=x1​−x2​+y2​−y1​

• d i s = x 2 − x 1 + y 1 − y 2 dis = x_2-x_1+y_1-y_2 dis=x2​−x1​+y1​−y2​

• d i s = x 2 − x 1 + y 2 − y 1 dis = x_2-x_1+y_2-y_1 dis=x2​−x1​+y2​−y1​

设定 ( x 1 , y 1 ) (x_1,y_1) (x1​,y1​) 为关键点，若使 d i s dis dis 最大，推广一下 ( x 2 , y 2 ) (x_2,y_2) (x2​,y2​) 作为四至点（地理）需要满足以下 4 4 4 点之一：

• min ⁡ ( x 2 + y 2 ) \min(x_2+y_2) min(x2​+y2​)

• min ⁡ ( x 2 − y 2 ) \min(x_2-y_2) min(x2​−y2​)

• max ⁡ ( x 2 − y 2 ) \max(x_2-y_2) max(x2​−y2​)

• max ⁡ ( x 2 + y 2 ) \max(x_2+y_2) max(x2​+y2​)

先预处理出四至点，再暴力每个点到四至点的曼哈顿距离最大值的最小值（打擂台）.

预处理时间复杂度： O ( 4 ⋅ n ) O(4 \cdot n) O(4⋅n)

打擂台时间复杂度: O ( 4 ⋅ n ) O(4 \cdot n) O(4⋅n)

A C AC AC.

题目收获

将关键式分解压缩解空间。

2. CF1380D Berserk And Fireball

题目描述

CF1380D 传送门

题目概况

来源：Codeforces

洛谷难度：蓝题

CF难度： 2000 2000 2000

标签：双指针 ST表 贪心

思路点拨

1. 毋庸置疑的是因为每个人的战力不同，所以通过双指针直接判定 a 、 b a、b a、b 数组是否一一对应.不对应直接 − 1 -1 −1.

2. 此时 a a a 数组已经被 b b b 数组元素切成了 [ l , r ] [l,r] [l,r] 的区间，只需要考虑这样的区间该如何处理.

3. 设 p = r − l + 1 p=r-l+1 p=r−l+1 以下分为 2 2 2 种情况：

   • p < k p<k p<k。处理区间内最大值，若最大值大于 2 2 2 端点 b b b 数组数值，则 − 1 -1 −1 ； 否则该区间代价为 p ⋅ y p \cdot y p⋅y (y为狂暴术代价，x为火球术代价)
   • k ≤ p k \leq p k≤p
     • 火球术代价比狂暴术代价优
       ⌊ p k ⌋ ⋅ x + p m o d k ⋅ y \lfloor \frac{p}{k}\rfloor \cdot x + p \mod k \cdot y ⌊kp​⌋⋅x+pmodk⋅y
     • 反之
       x + ( p − k ) ⋅ y x+(p-k)\cdot y x+(p−k)⋅y

4. 完善， a a a 数组区间最值用 S T ST ST 表预处理维护

时间复杂度： O ( n ⋅ l o g 2 ( n ) ) O(n \cdot log2(n)) O(n⋅log2(n))

A C AC AC.

题目收获

将题目分区间缩小范围。

3. P2568 GCD

题目描述

P2568 传送门

题目概况

来源：Codeforces

洛谷难度：蓝题

标签：数论 欧拉函数 gcd ⁡ \gcd gcd 前缀和

思路点拨

题目显而易见，先推一下式子。

• 原始： ∑ p ∈ p r i m e ∑ i = 1 n ∑ j = 1 n [ gcd ⁡ ( i , j ) = = p ] \sum _{p∈prime}\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)==p] ∑p∈prime​∑i=1n​∑j=1n​[gcd(i,j)==p]
• ①： ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ n p ⌋ [ gcd ⁡ ( i , j ) = = 1 ] \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)==1] ∑p∈prime​∑i=1⌊pn​⌋​∑j=1⌊pn​⌋​[gcd(i,j)==1]
• ②： ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ( ( 2 ⋅ ∑ j = 1 i [ gcd ⁡ ( i . j ) = = 1 ] ) − 1 ) \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot \sum_{j=1}^{i}[\gcd(i.j)==1])-1) ∑p∈prime​∑i=1⌊pn​⌋​((2⋅∑j=1i​[gcd(i.j)==1])−1)
• ③： ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ( ( 2 ⋅ φ ( i ) − 1 ) \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot\varphi(i) -1) ∑p∈prime​∑i=1⌊pn​⌋​((2⋅φ(i)−1)
• ④： ∑ p ∈ p r i m e 2 ⋅ ( ∑ i = 1 ⌊ n p ⌋ φ ( i ) ) − 1 \sum _{p∈prime}2 \cdot(\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i))-1 ∑p∈prime​2⋅(∑i=1⌊pn​⌋​φ(i))−1

所以可以使用线性筛预处理 φ \varphi φ 函数， 在预处理 φ \varphi φ 函数的前缀和.
O ( n ) O(n) O(n)时间复杂度求解.

A C AC AC.