url: https://www.luogu.com.cn/problem/UVA1629tag:动态规划，枚举，前缀和思路：用 dp[lx][ly][rx][ry] 来记录某一个区间中，为使每一块蛋糕都有樱桃的最小代价。使用dfs来枚举每一种可能性。使用记忆化搜索来减少时间。前缀和快速计算出某一块区域樱桃的数量。代码：#include <i…

url: https://www.luogu.com.cn/problem/P2672tag:NOIP2015 普及组，贪心，线段树，树状数组，前缀和，动态规划。思路：思路都是用贪心的策略，有两种情况，一种是取前x个a最大的客户，第二种是取前x - 1个a最大的客户，然后再从第i到n个中选择距离最远的一个去替换第x个a最大的客户，两种情况取最大值输…

url: https://www.luogu.com.cn/problem/P2568tag:数论，欧拉函数，筛法，前缀和思路：假设又两个互质的整数a, b，则gcd(a, b) = 1，那么对于任意的自然数p有gcd(a p, b p) = p。利用这个结论，对于这道题我们可以先求欧拉函数，然后求一遍gcd(a, b) = 1 的前缀和，这里求前…

url: https://www.luogu.com.cn/problem/P1083tag:差分，前缀和，二分思路：因为要求第一个不满足要求的订单，所以可以想到用二分。二分查找的是不满足要求的情况。通过订单的编号来查找，因为题目中写道有一个不满足要求的订单，后面就会停止分配，这可以抽象成假如有一个订单不满足，后面的订单一定也不满足，而前面的订单或…

url: https://www.luogu.com.cn/problem/P2004tag：前缀和思路：先求前缀和，然后遍历右下端点，求出每个对应的子矩阵的总和，判断是否大于res，如果大的话就更新res和坐标x，y。最后输出x和y即可。ps：这道题很简单，本来不应该传博客的，但是觉得自己写的好优美，忍不住传一下，以后偶尔可以翻出来看看。真的好优…

url: https://www.luogu.com.cn/problem/P2280tag：前缀和思路：这是一道二维前缀和。根据题意可以知道边长为m的爆破正方形最多可以破坏 m m 个目标，所以题目就变成了找到地图范围内，大小为m m的子矩阵中总价值最大的值。地图的范围可以直接定义成边界5000 5000，也可以像代码中的一样，一开始为m m表示…