本期主要讲解差分技巧。知识点我们令原数组为\(a_i\)，则当且仅当\(d_i=a_i-a_{i-1}\)时，我们称\(d_i\)是\(a_i\)的差分数组。特别的，\(d_1=0\)，\(d_{n+1}=-n\)。差分数组\(d_i\)有以下三个性质：\(d_i\)的前缀和数组为\(a_i\)。将\(a_{L\simR}\)这个区间统一加

ProblemT1/*思路：因为题目要求最大水量，所以K次操作需要都用上，并且由于每次都是将x倒入x+1中,所以K次操作之后的最大水量应当是x~x+k+1之和；于是问题就转变成了求一段长度为k+1的连续子段的和的最大值，因此维护一个前缀和即可。*/#include<bits/stdc++.h>usingnamespacestd

ProblemT1我们考虑一种贪心策略：对于价格前\(n-1\)小的咖啡，我们求出一种最优方案使得按照此方案买完咖啡后钱数\(\ge20\)且最接近\(20\)。至于如何求出最优方案，进行一遍01背包即可。#include<bits/stdc++.h>usingnamespacestd;intn,k;inta[1031],dp[1031];i

ProblemT1为了方便处理，我们令男生为\(1\)，女生为\(-1\)。求一遍前缀和\(sum\)，若存在两个下标\(l,r\)使得\(sum_l=sum_r\)，则说明区间\([l+1,r]\)的和为\(0\)，即男女人数相等。在这样的区间中取长度最大的即可。需要特殊处理\(sum_0\)。#include<bits/stdc++.h>#defi