专题记录1-前缀和差分
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
C - 前缀极差
2023HUEL寒假集训: 1.10 前缀和 - Virtual Judge (vjudge.net)
#include <cstdio>
#include <iostream>
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.com.cn)
使用前缀和取模。
我们假设n=5k=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]=2add[1]=3;
我们先看mod=0的时候所对应的数是34在3,4]区间中注意是左开右闭4%2=0满足条件
mod=1的时候所对应的数是125在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 <iostream>
using namespace std;
long long mod[100010],add[100010];
int main()
{
int n,k,a;
long long cnt=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<n;i++)
{
cnt+=add[i]*(add[i]-1)/2;//排列组合
}
cout<<cnt+add[0];
return 0;
}P6568 [NOI Online #3 提高组] 水壶
P6568 [NOI Online #3 提高组] 水壶 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
AC Code
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
int a[N], sum[N];
int main()
{
ios::sync_with_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.com.cn)
AC Code:
注意开long long!
#include <iostream>
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.com.cn)
方法一:dp
AC Code:
//方法1:dp
#include <iostream>
#include <cmath>
using namespace std;
const int N=2e5+5;
int a[N],n,dp[N];
int main()
{
ios::sync_with_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 <iostream>
#include <cstdio>
using namespace std;
int main()
{
ios::sync_with_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.com.cn)
知识点:一维差分与一维前缀和
AC Code:
#include <iostream>
#include <algorithm>
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();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (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;
while (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.com.cn)
知识点:二维前缀和与二维差分
AC Code:
#include <iostream>
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();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main()
{
n = read(), m = read();
while (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("%d\n", sum[i][j]);
}
}
return 0;
}2021级训练赛20211004 - Virtual Judge (vjudge.net)
注意开long long !
AC Code:
#include <iostream>
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();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (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();
while (q--)
{
l = read(), r = read();
printf("%lld\n", sum[r + l - 1] - sum[l - 1]);
}
return 0;
}2021级训练赛20211004 - Virtual Judge (vjudge.net)
注意把最后的减法运算改为异或运算!
AC Code:
#include <iostream>
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();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (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();
while(m--)
{
l=read(),r=read();
printf("%d\n",prexor[r]^prexor[l-1]);
}
return 0;
}2021级训练赛20211004 - Virtual Judge (vjudge.net)
需要注意的点:
1.每次while循环,首先要把差分数组清零,不然会因为上一轮的操作改变数组d的值.
2.注意找n的替身!
AC Code:
#include <iostream>
#include <cstring>
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();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
int main()
{
while (cin >> n, n != 0)
{
memset(d, 0, sizeof d); // 清零
int x = n; // 替身
while (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("%d\n", d[i]);
}
}
return 0;
}前缀和差分练习 - Virtual Judge (vjudge.net)
AC Code:
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
while (~scanf("%d%d", &n, &m))
{
int monitor, thieves;
scanf("%d", &monitor);
int ldx, ldy, rux, ruy;
vector<vector<int>> record(n + 2, vector<int>(m + 2)), glass(n + 2, vector<int>(m + 2));
while (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 row = 1; row <= n; ++row)
{
for (int col = 1; col <= m; ++col)
record[row][col] += record[row - 1][col] + record[row][col - 1] - record[row - 1][col - 1];
}
for (int row = 1; row <= n; ++row)
{
for (int col = 1; col <= m; ++col)
glass[row][col] += glass[row - 1][col] + glass[row][col - 1] - glass[row - 1][col - 1] + (record[row][col] > 0 ? 1 : 0);
}
scanf("%d", &thieves);
while (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("YES\n");
else
printf("NO\n");
}
}
return 0;
}前缀和差分练习 - Virtual Judge (vjudge.net)
AC Code:
#include<iostream>
#include<cstdio>
#include<cmath>
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<n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
ll k;
if((2*sum%(n*(n+1)))!=0)
{
printf("NO");
return 0;
}
k=2*sum/n/(n+1);
for(int i=0;i<n;i++)
{
if(i==n-1)
dis[i]=a[i]-a[0];
else
dis[i]=a[i]-a[i+1];
}
for(int i=0;i<n;i++)
{
if(dis[i]+k<0||(dis[i]+k)%n!=0)
{
printf("NO");
return 0;
}
}
printf("YES");
return 0;
}B - Average Superhero Gang Power
前缀和差分 - Virtual Judge (vjudge.net)
题目大意对于一群超级英雄他们分别有最初的力量值有两种操作1、给任意英雄力量加一2、去掉任意一个英雄。求操作后英雄们平均力量的最大值。共有n个超级英雄每个人最多操作k次即力量最多加k总可操作次数为m。
思路先初始化总力量sum和平均力量ans=(sum+min(k*n,m))/n; 因为n个人每人操作k次的总数有可能超过m所以是min(k*n,m)然后力量从小到大排序每次减掉一个人依次比较上次的ans和新的ans2取大值。对了还要注意数据范围。
AC Code:
#include <iostream>
#include <algorithm>
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("%.20f\n", ans);
}前缀和差分 - Virtual Judge (vjudge.net)
这个题目是思维题我开始也想直接暴力就是直接枚举k的次方直到它到达10的14次方
这个不是很大如果是2都只要几十次所以肯定不会超时不过不知道怎么操作。
看了题解觉得map真是一个好东西它可以存很大的数耗费的空间也不是很大。
我们就可以把数值存到map里面。
具体就是先处理这些数求出前缀和然后就是求出k的幂。
最后枚举。
AC Code:
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
ll a[maxn];
ll kc[maxn];
map<ll,ll>mp;
int main()
{
int n, k;
cin >> n >> k;
for(int i=1;i<=n;i++)
{
scanf("%lld", &a[i]);
a[i] += a[i - 1];//求前缀数组
}
int cnt = 2;
kc[1] = 1;//这个是幂为0的时候
if (k == -1)//当k=-1的时候就两种可能这个要特殊枚举
{
kc[2] = -1;
cnt++;
}
else if(k!=1)
{
ll temp = k;
while(temp<1e15&&temp>-1e15)
{
kc[cnt++] = temp;
temp *= k;
}
}
ll ans = 0;
for (int i = 1; i < cnt; i++) mp[kc[i]] = 1;
for(int i=1;i<=n;i++)
{
if (mp[a[i]]) ans+=mp[a[i]];
for(int j=1;j<cnt;j++)
{
mp[a[i] + kc[j]]++;
}
}
printf("%lld\n", ans);
return 0;
}