专题记录1-前缀和差分

C - 前缀极差

2023HUEL寒假集训: 1.10 前缀和 - Virtual Judge (vjudge.)

#include 
#include 
using namespace std;
const int N = 1e5 + 100;
int a[N];
int p[N], t[N];
int x[N];
int main()
{
 int n, q;
 scanf("%d%d", &n, &q);
 for (int i = 1; i <= n; i++)
 {
  scanf("%d", &a[i]);
  if (i == 1)
   p[i] = a[i], t[i] = a[i];
  else
   p[i] = max(p[i - 1], a[i]),
   t[i] = min(t[i - 1], a[i]);
 }
 for (int i = 1; i <= q; i++)
 {
  scanf("%d", &x[i]);
  x[i] = p[x[i]] - t[x[i]];
 }
 for (int i = 1; i < q; i++)
  printf("%d ", x[i]);
 printf("%d", x[q]);
 return 0;
}

P8649 [蓝桥杯 2017 省 B] k 倍区间

P8649 [蓝桥杯 2017 省 B] k 倍区间 - 洛谷 | 计算机科学教育新生态 (luogu..)

使用前缀和取模。

我们假设n=5；k=2；

输入的5个数为1,2,3,4,5的话

程序输出6 这6种情况分别是123  1234  2345  345  2  4;

若我们将前i项和的模存到一个数组mod[i]中,mod[1]表示前一项的和的模，mod[2]表示前两项的和的模，以此类推，再将mod[i]相同的个数用一个数组add[mod[i]]存起来，只需要计算C 2 add[i]（高中数学的排列组合，2在上面，add[i]在下面）再加上add[0]的所有结果，便可求得正确答案，极大简化了运算时间。

还是上面那个例子1 2 3 4 5  假如是输入这5个数

可得mod[1]=1(1%2=1)  mod[2]=1((1+2)%2=1)  mod[3]=0  mod[4]=0  mod[5]=1

mod=1的个数有3个，mod=0的个数有2个，所以add[0]=2，add[1]=3;

我们先看mod=0的时候，所对应的数是3，4，在（3,4]区间中（注意是左开右闭），4%2=0满足条件，

mod=1的时候，所对应的数是1，2，5，在（1,2]区间中，2%2=0满足条件，（1,5]区间中，2345满足条件(2+3+4+5)%2=0,在(2,5]区间中，345满足条件。

所以可以得出结论，从每一种前缀和(所选两个数的中间的数的和)的情况中任意选择两个数组成的区间都满足是k倍区间，其计算方法其实就是排列组合，上面的例子即可表示为C2 2加上C2 3结果为1+3=4，但实际结果有6种，是由于区间是左开右闭的，加上add[0]的所有结果也就是2和4两种，相当于区间左闭右闭，这两个数本身构成一个k倍区间，4+2=6，刚好是正确答案。

于是可得如下代码

#include 
using namespace std;
long long mod[100010],add[100010];
int main()
{
	int n,k,a;
	long long t=0;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		mod[i]=(mod[i-1]+a)%k;
		add[mod[i]]++;
	}
	for(int i=0;i 
P6568 [NOI Online #3 提高组] 水壶 
P6568 [NOI Online #3 提高组] 水壶 - 洛谷 | 计算机科学教育新生态 (luogu..)
 
AC Code
 
#include 
using namespace std;
const int N = 1e6 + 5;
int a[N], sum[N];
int main()
{
 ios::sync_ith_stdio(false);
 cin.tie(nullptr), cout.tie(nullptr);
 int n, m;
 cin >> n >> m;
 for (int i = 1; i <= n; i++)
 {
  cin >> a[i];
 }
 for (int i = 1; i <= n; i++)
 {
  sum[i] = sum[i - 1] + a[i];
 }
 int max = 0;
 for (int i = 1; i + m <= n; i++)
 {
  int k = sum[i + m] - sum[i - 1]; // 前缀和计算，注意，水壶倒的次数比子段长度小1（自己想想为什么）
  if (k > max)
   max = k; // 判断大小
 }
 printf("%d", max); // 输出
 return 0;
}
 
P8772 [蓝桥杯 2022 省 A] 求和 
P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷 | 计算机科学教育新生态 (luogu..)
 
AC Code:
 
 
 
注意开long long!
 
 
#include 
using namespace std;
const int N = 2e5 + 5;
int a[N], n;
long long sum[N], ans;
int main()
{
 cin >> n;
 for (int i = 1; i <= n; i++)
  cin >> a[i];
 for (int i = 1; i <= n; i++)
  sum[i] = sum[i - 1] + a[i];
 for (int i = 1; i < n; i++)
 {
  ans += a[i]  (sum[n] - sum[i]);
 }
 cout << ans;
 return 0;
}
 
P1115 最大子段和 
P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu..)
 
 
 
方法一:dp
 
 
AC Code:
 
//方法1:dp
#include 
#include 
using namespace std;
const int N=2e5+5;
int a[N],n,dp[N];
int main()
{
 ios::sync_ith_stdio(false);
 cin.tie(nullptr),cout.tie(nullptr);
 cin >> n;
 for(int i=1;i<=n;i++)
 {
  cin >> a[i];
 }
 dp[1]=a[1];
 for(int i=2;i<=n;i++)
 {
  dp[i]=max(dp[i-1]+a[i],a[i]);
 }
 int maxx=-10000;
 for(int i=1;i<=n;i++)
 {
  if(dp[i]>maxx)
   maxx=dp[i];
 }
 cout << maxx;
 return 0;
}
 
 
 
方法二:双指针 
 
 
 AC Code:
 
#include 
#include 
using namespace std;
int main()
{
 ios::sync_ith_stdio(false);
 cin.tie(nullptr), cout.tie(nullptr);
 int a, n, s = 0, ans = -2e9;
 cin >> n;
 for (int i = 1; i <= n; i++)
 {
  cin >> a;
  if (s + a > a)
   s += a;
  else
   s = a;
  ans = max(ans, s);
 }
 cout << ans;
 return 0;
}
 
P2367 语文成绩 
P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu..)
 
 
 
知识点:一维差分与一维前缀和
 
 
AC Code:
 
#include 
#include 
using namespace std;
const int N = 5e6 + 5;
int a[N], d[N], n, p;
inline int read()
{
 bool sym = 0;int res = 0;char ch = getchar();
 hile (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
 hile (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
 return sym ? -res : res;
}
int main()
{
 n = read(), p = read();
 for (int i = 1; i <= n; i++)
  a[i] = read();
 for (int i = 1; i <= n; i++)
  d[i] = a[i] - a[i - 1];
 int x, y, z;
 hile (p--)
 {
  x = read(), y = read(), z = read();
  d[x] += z, d[y + 1] -= z;
 }
 for (int i = 1; i <= n; i++)
  d[i] += d[i - 1];
 int minn = 1000;
 for (int i = 1; i <= n; i++)
  if (d[i] < minn)
   minn = d[i];
 printf("%d", minn);
 return 0;
}
 
P3397 地毯 
P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu..)
 
 
 
知识点:二维前缀和与二维差分
 
 
AC Code:
 
#include 
using namespace std;
const int N = 1e3 + 5;
int n, m, map[N][N],sum[N][N],x1, y1, x2, y2;
inline int read()
{
 bool sym = 0;int res = 0;char ch = getchar();
 hile (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
 hile (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
 return sym ? -res : res;
}
int main()
{
 n = read(), m = read();
 hile (m--)
 {
  x1 = read(), y1 = read(), x2 = read(), y2 = read();
  map[x1][y1]++;
  map[x2+1][y1]--;
  map[x1][y2+1]--;
  map[x2+1][y2+1]++;
 }
 for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=n;j++)
  {
   sum[i][j]=map[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
  }
 }
 for (int i = 1; i <= n; i++)
 {
  for (int j = 1; j <= n; j++)
  {
   if (j != n)
    printf("%d ", sum[i][j]);
   else
    printf("%dn", sum[i][j]);
  }
 }
 return 0;
}
 
A - 子段求和
 
2021级训练赛20211004 - Virtual Judge (vjudge.)
 
 
 
注意开long long !
 
 
AC Code:
 
#include 
using namespace std;
const int N = 5e4 + 5;
long long sum[N];
int n, q, l, r, a[N];
inline int read()
{
 bool sym = 0;int res = 0;char ch = getchar();
 hile (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
 hile (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
 return sym ? -res : res;
}
int main()
{
 n = read();
 for (int i = 1; i <= n; i++)
  a[i] = read();
 for (int i = 1; i <= n; i++)
  sum[i] = sum[i - 1] + a[i];
 q = read();
 hile (q--)
 {
  l = read(), r = read();
  printf("%lldn", sum[r + l - 1] - sum[l - 1]);
 }
 return 0;
}
 
F - 前缀异或
 
2021级训练赛20211004 - Virtual Judge (vjudge.)
 
 
 
注意把的减法运算改为异或运算!
 
 
AC Code:
 
#include 
using namespace std;
const int N=1e5+5;
int a[N],n,m,l,r,prexor[N];
inline int read()
{
 bool sym = 0;int res = 0;char ch = getchar();
 hile (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
 hile (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
 return sym ? -res : res;
}
int main()
{
 n=read();
 for(int i=1;i<=n;i++)
 {
  a[i]=read();
 }
 prexor[1]=a[1];
 for(int i=2;i<=n;i++)
 {
  prexor[i]=prexor[i-1]^a[i];
 }
 m=read();
 hile(m--)
 {
  l=read(),r=read();
  printf("%dn",prexor[r]^prexor[l-1]);
 }
 return 0;
}
 
G - Color the ball
 
2021级训练赛20211004 - Virtual Judge (vjudge.)
 
 
 
需要注意的点:
 
 
1.每次hile循环,要把差分数组清零,不然会因为上一轮的操作改变数组d的值.
 
 
2.注意找n的替身!
 
 
AC Code:
 
#include 
#include 
using namespace std;
const int N=1e5+5;
int n,d[N],a,b;
inline int read()
{
 bool sym = 0;int res = 0;char ch = getchar();
 hile (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
 hile (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
 return sym ? -res : res;
}
int main()
{
 hile (cin >> n, n != 0)
 {
  memset(d, 0, sizeof d); // 清零
  int x = n;     // 替身
  hile (n--)
  {
   a = read(), b = read();
   d[a]++, d[b + 1]--;
  }
  for (int i = 1; i <= x; i++)
  {
   d[i] += d[i - 1];
  }
  for (int i = 1; i <= x; i++)
  {
   if (i != x)
    printf("%d ", d[i]);
   else
    printf("%dn", d[i]);
  }
 }
 return 0;
}
 
I - Monitor
 
前缀和差分练习 - Virtual Judge (vjudge.)
 
AC Code:
 
#include 
#include 
using namespace std;
int main()
{
 int n, m;
 hile (~scanf("%d%d", &n, &m))
 {
  int monitor, thieves;
  scanf("%d", &monitor);
  int ldx, ldy, rux, ruy;
  vector> record(n + 2, vector(m + 2)), glass(n + 2, vector(m + 2));
  hile (monitor--)
  {
   // 左上角x,y 右下角x,y
   scanf("%d%d%d%d", &ldx, &ldy, &rux, &ruy);
   ++record[ldx][ldy];
   ++record[rux + 1][ruy + 1];
   --record[ldx][ruy + 1];
   --record[rux + 1][ldy];
  }

  for (int ro = 1; ro <= n; ++ro)
  {
   for (int col = 1; col <= m; ++col)
    record[ro][col] += record[ro - 1][col] + record[ro][col - 1] - record[ro - 1][col - 1];
  }

  for (int ro = 1; ro <= n; ++ro)
  {
   for (int col = 1; col <= m; ++col)
    glass[ro][col] += glass[ro - 1][col] + glass[ro][col - 1] - glass[ro - 1][col - 1] + (record[ro][col] > 0 ? 1 : 0);
  }

  scanf("%d", &thieves);

  hile (thieves--)
  {
   scanf("%d%d%d%d", &ldx, &ldy, &rux, &ruy);
   int area = glass[rux][ruy] - glass[rux][ldy - 1] - glass[ldx - 1][ruy] + glass[ldx - 1][ldy - 1];
   if (area == (rux - ldx + 1)  (ruy - ldy + 1))
    printf("YESn");
   else
    printf("NOn");
  }
 }
 return 0;
}
 
J - Boxes
 
前缀和差分练习 - Virtual Judge (vjudge.)
 
AC Code:
 
#include
#include
#include
typedef long long ll;
using namespace std;
ll n;
ll a[100010];
ll dis[100010];
int main()
{
 ll sum=0;
 scanf("%lld",&n);
 for(int i=0;i 
B - Average Superhero Gang Poer
 
前缀和差分 - Virtual Judge (vjudge.)
 
 
 
题目大意对于一群超级英雄，他们分别有最初的力量值，有两种操作1、给任意英雄力量加一，2、去掉任意一个英雄。求操作后英雄们平均力量的最大值。共有n个超级英雄，每个人最多操作k次（即力量最多加k），总可操作次数为m。
 
 
思路先初始化总力量sum和平均力量ans=(sum+min(kn,m))/n; 因为n个人每人操作k次的总数有可能超过m，所以是min(kn,m)，然后力量从小到大排序，每次减掉一个人，依次比较上次的ans和新的ans2，取大值。对了还要注意数据范围。
 
 
AC Code:
 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 100010;
double a[maxn];
int main()
{
 ll n, k, m;
 double sum = 0;
 cin >> n >> k >> m;
 for (int i = 1; i <= n; i++)
 {
  cin >> a[i];
  sum += a[i];
 }
 sort(a + 1, a + n + 1);
 double ans = (sum + min(k  n, m)) / n;
 for (int i = 0; i < n && i <= m; i++)
 {
  sum -= a[i];
  double ans2 = (sum + min(k  (n - i), m - i)) / (n - i);
  ans = max(ans, ans2);
 }
 printf("%.20fn", ans);
}
 
H - Molly's Chemicals
 
前缀和差分 - Virtual Judge (vjudge.)
 
 
 
这个题目是思维题，我开始也想直接暴力，就是直接枚举k的次方，直到它到达10的14次方，
 这个不是很大，如果是2都只要几十次，所以肯定不会超时，不过不知道怎么操作。
 看了题解，觉得map真是一个好东西，它可以存很大的数，耗费的空间也不是很大。
 我们就可以把数值存到map里面。
 具体就是，先处理这些数，求出前缀和，然后就是求出k的幂。
 枚举。
 
 
AC Code:
 
#include 
#include 
#include 
#include