struct_GS的博客

前置知识： 最小生成树，前缀和 题目描述： 解题思路： 又是熟悉的区间判断问题，对于这一类的问题，可以尝试考虑前缀和。 询问给定的区间就等同于提供了前缀和的差值，记录第 i 个数的前缀和为 sum[i] ，即区间 [l,r] 的和可以转化为 sum[r] - sum[l-1] 。 题目给出的任务是解出所有未知数的值。达到这个目的只需要判断是否每一个单独的区间都可以通过前缀和相减的方式得到，而题目要求得到代价和的...

目录： 前置知识 题目描述 解题思路 AC 代码 前置知识： 并查集，前缀和 题目描述： 解题思路： 题意让我们判断小红的话在第几句出现了错误，如果直接 BF 的话肯定会爆（你问我为什么，因为我试过··· ···），那就要考虑优化，既然是一个连续的区间，那就可以声明一个前缀和数组 sum 来优化算法，既然有了前缀和，那么是不是可以用并查集来维护 - k (mod p)关系？是的，这道题目用并查集恰到好处。那么接下来就该考虑并查集的内部程...

区间DP 简介： 正所谓区间 DP ，就是在区间上进行 DP 。区间 DP 以区间的长度划分阶段，记录两个端点的坐标，通过合并小区间的最优解来求出大区间的最优解。 在一般的 区间 DP 题目中，区间 DP 的转移依赖于枚举分割点，由此，一般的区间 DP 的时间复杂度为 O() 。 一维区间 DP： 一维区间 DP 又被称为普通的区间 DP 。顾名思义，就是在一维的数组上进行区间 DP。其中，最典型的例子就是 石子合并。 题目大意...

小编有在洛谷找到一样的题目：Brownie Slicing G 目录： 前缀知识： 题目要求： 解题思路: 直接上代码： 前缀知识： 本题解需要大家熟练掌握前缀和和二分算法的相关知识 题目要求： 把n*m的矩阵分成a*b块，求最小价值块的价值最大。 解题思路: 最大化最小点权之和，显然考虑二分答案。考虑二分一个值x，如何判断x是否能作为答案，也就是判断x是否能作为所有点的点权之和最小的一块小子矩阵的点权之和。等价于其他的所有小子矩阵的...