前缀和
截断数组(acwing)
题面:
给定一个长度为 n 的数组 a
现在,要将数组从中间截断,得到三个 非空 子数组。
要求,三个子数组内各元素之和都相等,问有几种截法。
数据范围:
$$1 \leq n \leq 10^5 , -10000 \leq a_i \leq 10000$$
题解:
如果整个数组之和 除不尽3,那么一定分割不成功,如果现在的段刚好为sum / 3那么说明这一段能分出来,用 a去记录可以分成几段,最后在找一个位置,使得sum / 3 * 2的位置即可。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| void JiuCherish(){ int n; std::cin >> n; i64 sum = 0; for(int i=1;i<=n;i++) { std::cin >> a[i]; b[i] = b[i - 1] + a[i]; sum += a[i]; } int aa = 0; i64 ans = 0; if(sum % 3) { std::cout << 0 << endl; return; } else { for(int i=1;i<n;i++) { if(b[i] == sum / 3 * 2) ans += aa; if(b[i] == sum / 3) aa++; } std::cout << ans << endl; } }
|
前缀和
题面:
给你一个长度为 n 的整数序列。
在进行 m 次询问,每次询问输入一对l,r
问:区间[l,r]的和。
数据范围:
$$1 \leq l \leq r\leq n$$
$$1 \leq n,m \leq 100000$$
$$-1000 \leq a_i \leq 1000$$
题解:
模板题。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13
| void JiuCherish(){ int n,q; std::cin >> n >> q; for(int i=1;i<=n;i++) { std::cin >> a[i]; b[i] = b[i - 1] + a[i]; } while(q--) { int l,r; std::cin >> l >> r; std::cout << b[r] - b[l - 1] << endl; } }
|
子矩阵的和
题意:
给n 行 m 列的整数矩阵,在给 q次询问
问 x1,y1,x2,y2 所围成的矩阵数值之和是多少?
数据范围
$$1 \leq n,m \leq 1000$$
$$1 \leq q \leq 200000$$
$$1 \leq x_1 \leq x_2 \leq n$$
$$1 \leq y_1 \leq y_2 \leq m$$
$$-1000 \leq a_i \leq 1000$$
题解:
模板题
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void JiuCherish(){ int n,m,q; std::cin >> n >> m >> q; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { std::cin >> a[i][j]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j]; } } while(q--) { int x1,x2,y1,y2; std::cin >> x1 >> y1 >> x2 >> y2; std::cout << b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1] << endl; } }
|
k倍区间
题意:
给长度为 n 的数列,约定 k 倍区间表示 数列区间[i,j]的和是 k 的倍数。
问数列中有几个 k 被区间。
数据范围
$$1 \leq n,k \leq 100000$$
$$1 \leq a_i \leq 100000$$
题解:
只需要知道
$$(a + b)mod c 等价于 a modc + bmod c$$
即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void JiuCherish(){ int n,k; std::cin >> n >> k; i64 sum = 0; for(int i=1;i<=n;i++) { std::cin >> a[i]; b[i] = b[i - 1] + a[i]; } res[0] = 1; for(int i=1;i<=n;i++) { sum += res[b[i] % k]; res[b[i] % k]++; } std::cout << sum << endl; }
|
差分
改变数组元素
给定一个空数组 V 和一个整数数组a。
现在对数组V进行 n 次操作
第 i 次操作的具体流程如下:
- 从数组 V 尾部插入整数 0。
- 将位于数组 V 末尾的 ai 个元素都变为 1(已经是 1 的不予理会)。
注意:
- ai 可能为 0,即不做任何改变。
- ai 可能大于目前数组 V 所包含的元素个数,此时视为将数组内所有元素变为 1。
请你输出所有操作完成后的数组 V。
数据范围
$$1 \leq T \leq 20000$$
$$1 \leq n \leq 2 \times 10^5$$
$$0 \leq a_i \leq n$$
保证 $$\sum T * n < 2 \times 10^5$$
题解:
维护区间,用当前数是k,就把该数和该数前面k个数变成1。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| void JiuCherish(){ int n; std::cin >> n; for(int i=1;i<=n;i++) std::cin >> a[i]; int l = 1e9; std::vector<int> ans; for(int i=n;i>=1;i--) { l = std::min(l,i - a[i] + 1); if(l <= i) { ans.pb(1); } else { ans.pb(0); } } std::reverse(ans.begin(),ans.end()); for(auto x : ans) std::cout << x << " "; std::cout << endl; }
|
差分
给你一个 长度为 n 的数组
你有 m 次操作,包括了 l,r,c,表示将数组 [l,r] 之间的每个数都加上 c
请你输出进行完成所有操作后的数组。
数据范围:
$$1 \leq l \leq r\leq n$$
$$1 \leq n,m \leq 100000$$
$$-1000 \leq c \leq 1000$$
$$-1000 \leq a_i \leq 1000$$
题解
模板
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void JiuCherish(){ int n,q; std::cin >> n >> q; for(int i=1;i<=n;i++) { std::cin >> a[i]; b[i] = a[i] - a[i - 1]; } while(q--) { int l,r,x; std::cin >> l >> r >> x; b[l] += x; b[r + 1] -= x; } int x = 0; for(int i=1;i<=n;i++) { x += b[i]; std::cout << x << " "; } }
|
差分矩阵
输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
数据范围:
$$1 \leq n,m \leq 1000$$
$$1 \leq q \leq 100000$$
$$1 \leq x_1 \leq x_2\leq n$$
$$1 \leq y_1 \leq y_2\leq m$$
$$-1000 \leq c \leq 1000$$
$$-1000 \leq a_i \leq 1000$$
题解
模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| void JiuCherish(){ int n,m,q; std::cin >> n >> m >> q; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { std::cin >> res[i][j]; ans[i][j] = -res[i - 1][j] - res[i][j - 1] + res[i - 1][j - 1] + res[i][j]; } } while(q--) { int x1,x2,y1,y2,val; std::cin >> x1 >> y1 >> x2 >> y2 >> val; x2++; y2++; ans[x1][y1] += val; ans[x1][y2] -= val; ans[x2][y2] += val; ans[x2][y1] -= val; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + ans[i][j]; std::cout << res[i][j] << " "; } std::cout << endl; } }
|
增减序列
给定一个长度为 n 的数列,每次可以选一个区间 [l,r] 使下标在这个区间内的数都加一或者都减一。
求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。
数据范围:
$$0 < n \leq 10^5$$
$$0 \leq a_i < 2147483648$$
题解:
找到中位数即可。
最少操作次数就是最少的pos或neg 加上这两个差值的绝对值。
结果就是:差值绝对值+1。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void JiuCherish(){ int n; std::cin >> n; for(int i=1;i<=n;i++) { std::cin >> a[i]; b[i] = a[i] - a[i - 1]; } i64 pos = 0,neg = 0; for(int i=2;i<=n;i++) { if(b[i] > 0) pos += b[i]; else neg -= b[i]; } std::cout << std::min(pos,neg) + std::abs(pos - neg) << endl; std::cout << std::abs(pos - neg) + 1 << endl; }
|
二分
数的范围
给一个升序的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(从 0 开始计数)
如果数组中不存在该元素,返回两个 -1 -1。
数据范围:
$$1 \leq n \leq 100000$$
$$1 \leq q \leq 10000$$
$$1 \leq k \leq 10000$$
题解:
第一次二分看看左边界是否能找到数,找不到直接结束。
输出第一次左边界找到的。
第二次二分找到最右边是否能找到数。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| void JiuCherish(){ int n,q; std::cin >> n >> q; for(int i=0;i<n;i++) std::cin >> a[i]; while(q--) { int x; std::cin >> x; int l = 0,r = n - 1; int mid = 0; while(l < r) { mid = l + r >> 1; if(a[mid] >= x) r = mid; else l = mid + 1; } if(a[l] != x) { std::cout << "-1 -1" << endl; continue; } std::cout << l <<" "; l = 0,r = n - 1; while(l < r) { mid = l + r + 1 >> 1; if(a[mid] <= x) l = mid; else r = mid - 1; } std::cout << l << endl; } }
|