文和906

题解

未归档(4) 项目笔记(5)

/ 注册

全部文章 / 题解（共103篇）

题解 | #【模板】二维差分#

和#【模板】差分#的思路完全一致。使用一个二位数组sum来记录每一位改变的信息，然后通过求前缀和的形式求出每一位一一对应的改变值。最后将sum中的每一个元素与原始数组arr中对应的元素加起来即可得到结果数组。唯一有区别的地方在记录改变信息以及求前缀和上的操作略微复杂化。这里记录的方式与求前缀和的方式...

C++

2021-10-29

0 549

题解 | #【模板】差分#

因为本题直接解决实现起来不难，故一开始选择直接暴力解法。每次接受l，r，k后，直接遍历数组中的第l个到第r个元素，将其加k。这种做法时间复杂度O(n^2)，空间复杂度O(1)。会在第七个用例(共8个)处超时。由于用例输入数据量过大，无法验证是由于循环逻辑出错导致超时，还是由于算法时间复杂度过高导致超...

C++ 动态规划

2021-10-29

0 626

题解 | #【模板】二维前缀和#

思路是用一个二维数组sum来储存(0, 0)到该点所形成的子矩阵中所有数的和。即sum.at(i).at(j)储存着以(0,0)(i,j)为反对角线的矩阵的所有元素的和。当要计算(x1, y1)与(x2, y2)所形成的矩阵中所有元素的和时，只需要用(0, 0)(x2, y2)这个大的矩形，减去(0...

C++ 前缀和动态规划

2021-10-28

0 540

题解 | #abb#

开始时设想使用前缀和的方法，建立一个sum数组，其中sum.at(i)保存的是前i项中abb的个数。按顺序遍历字符串，使用一个二重循环，对每一个字符都统计其在之前出现的次数以及其他字符出现的位置，按照C(2,n)的组合数计算规则可以发现C(2,1), C(2,2), ..., C(2,n)组成的数列...

C++ 后缀和

2021-10-28

2 501

题解 | #【模板】前缀和#

经典前缀和问题。具体做法是在接受输入数字创建数组时，同时创建一个前缀和数组sum，sum.at(i)维护的是数组前i+1项的和(0为首项)。在处理每一组l与r时，直接让前r项的和减去前l项的和在加上第l项的和即可。时间复杂度O(n)，空间复杂度O(n)。 #include <iostream&...

C++ 动态规划前缀和

2021-10-28

0 354

题解 | #nico和niconiconi#

典型的线性动态规划。使用前缀和的思路，建立一个数组用于存储字符串str前i个字符中最大的值，然后寻找其递推关系。显然，每遍历一个字符，都要判断其前i个字符中最大的前缀和的a, b, c的状态，有可能仅是增加1个a, b, c，亦有可能增加3个a，减少一个c。最后，前缀和数组中的末项即为整个字符串最大...

C++ 线性动态规划

2021-10-27

0 483

题解 | #不相邻取数#

开始时使用暴力法，用一个三重循环枚举出所有可能的不相邻数的和，并选出其中最大的和作为输出其核心思想是对每一种可能的间隔，每一种可能的起点，计算出其最大的和。由于数组元素非负，所以在起点与间隔固定的情况下，数字当然越多越好。具体做法为，最外层循环控制间隔，间隔是从1~size()-2的。中间层循环控制...

C++ 线性动态规划

2021-10-27

0 690

题解 | #子数组最大连续和#

从头遍历输入数组，先假设数组中元素不全为负。每次都将当前元素加到sum中，然后判断，sum，若sum<0，则令sum=0。因为之后sum必定已经加到或将会加到一个不为负的数。若sum>max，则令max=sum。然后对数组全为负的情况添加一些判断。此时max必定为负，则当sum<0...

C++ 线性动态规划

2021-10-27

0 468

题解 | #调整数组顺序使奇数位于偶数前面(二)#

思路与调整数组顺序使奇数位于偶数前面(一)完全相同。这里就不赘述。具体讲一下有差异的地方。在(一)中要求奇数之间及偶数之间的相对位置不变，那么在交换奇数偶数时就涉及到稳定性的问题，在(一)中选择使用类似插入排序的操作来保证稳定性。而在(二)中，对稳定性不做要求，这无疑降低了难度，直接交换第一个偶数及...

C++ 数组

2021-10-26

0 396

题解 | #剪绳子#

这题比较偏数学思维了。观察几个数手动切割的结果可以发现，它们最大的乘积都是拆分成若干个2和3相乘得到的，不存在1，5，7。根据这一结论可以将长度为n的数分为两部分，一部分由若干个3相乘得到，另一部分由若干个2相乘得到，且3必定多于2。所以实际操作时，可以先找出3部分的乘积，在得出2部分的乘积。最后将...

C++ 数学

2021-10-26

0 458