网站怎么做快捷方式,小程序模板免费制作,wordpress文章点赞插件,网站建设所需物资1. CF1689D Lena and Matrix
题目描述 n ⋅ m n \cdot m n⋅m 的矩阵#xff0c;求矩阵上任意一点坐标使得到矩阵上的关键点曼哈顿距离最大值最小。数据范围#xff1a; ∑ n ⋅ m ≤ 1 0 6 \sum n \cdot m \leq 10^6 ∑n⋅m≤106
题目概况
来源#xff1a;Codeforces
…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_2y_1-y_2 disx1−x2y1−y2 d i s x 1 − x 2 y 2 − y 1 dis x_1-x_2y_2-y_1 disx1−x2y2−y1 d i s x 2 − x 1 y 1 − y 2 dis x_2-x_1y_1-y_2 disx2−x1y1−y2 d i s x 2 − x 1 y 2 − y 1 dis x_2-x_1y_2-y_1 disx2−x1y2−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_2y_2) min(x2y2) 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_2y_2) max(x2y2)
先预处理出四至点再暴力每个点到四至点的曼哈顿距离最大值的最小值打擂台.
预处理时间复杂度 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表 贪心
思路点拨 毋庸置疑的是因为每个人的战力不同所以通过双指针直接判定 a 、 b a、b a、b 数组是否一一对应.不对应直接 − 1 -1 −1. 此时 a a a 数组已经被 b b b 数组元素切成了 [ l , r ] [l,r] [l,r] 的区间只需要考虑这样的区间该如何处理. 设 p r − l 1 pr-l1 pr−l1 以下分为 2 2 2 种情况 p k pk pk。处理区间内最大值若最大值大于 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⌋⋅xpmodk⋅y反之 x ( p − k ) ⋅ y x(p-k)\cdot y x(p−k)⋅y 完善 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_{i1}^{n}\sum_{j1}^{n}[\gcd(i,j)p] ∑p∈prime∑i1n∑j1n[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_{i1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)1] ∑p∈prime∑i1⌊pn⌋∑j1⌊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_{i1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot \sum_{j1}^{i}[\gcd(i.j)1])-1) ∑p∈prime∑i1⌊pn⌋((2⋅∑j1i[gcd(i.j)1])−1)③ ∑ p ∈ p r i m e ∑ i 1 ⌊ n p ⌋ ( ( 2 ⋅ φ ( i ) − 1 ) \sum _{p∈prime}\sum_{i1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot\varphi(i) -1) ∑p∈prime∑i1⌊pn⌋((2⋅φ(i)−1)④ ∑ p ∈ p r i m e 2 ⋅ ( ∑ i 1 ⌊ n p ⌋ φ ( i ) ) − 1 \sum _{p∈prime}2 \cdot(\sum_{i1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i))-1 ∑p∈prime2⋅(∑i1⌊pn⌋φ(i))−1
所以可以使用线性筛预处理 φ \varphi φ 函数 在预处理 φ \varphi φ 函数的前缀和. O ( n ) O(n) O(n)时间复杂度求解. A C AC AC.
