广告设计网站官网,焦作做网站最专业的公司,专业3合1网站建设,ps做网站头部一维前缀和
S[i] a[1] a[2] ... a[i]
a[l] ... a[r] S[r] - S[l - 1]二维前缀和
S[i, j] 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角#xff0c;(x2, y2)为右下角的子矩阵的和为#xff1a;
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] S[x1 - 1, y1 - …一维前缀和
S[i] a[1] a[2] ... a[i]
a[l] ... a[r] S[r] - S[l - 1]二维前缀和
S[i, j] 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角(x2, y2)为右下角的子矩阵的和为
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] S[x1 - 1, y1 - 1]练习题
562. 壁画
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 5e6 10;
int n;
int s[N];
char str[N];int main()
{int T;scanf(%d, T);for (int x 1; x T; x ){scanf(%d, n);scanf(%s, str 1);memset(s, 0, sizeof s);for (int i 1; i n; i ) s[i] s[i - 1] str[i] - 0;int k (n - 1) / 2 1;int sum 0;for (int i k; i n; i )sum max(sum, s[i] - s[i - k]);printf(Case #%d: %d\n, x, sum);}return 0;
}795. 前缀和
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1e5 10;
int n, m;
int s[N];int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ) {scanf(%d, s[i]);s[i] s[i - 1];}while (m -- ) {int l, r;scanf(%d%d, l, r);printf(%d\n, s[r] - s[l - 1]);}return 0;
}796. 子矩阵的和
#include iostream
#include algorithm
#include cstringusing namespace std;int n, m, q;
const int N 1010;
int s[N][N];int main()
{scanf(%d%d%d, n, m, q);for (int i 1; i n; i ) for (int j 1; j m; j ) scanf(%d, s[i][j]);for (int i 1; i n; i ) for (int j 1; j m; j ) s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1];while(q -- ){int x1, y1, x2, y2;cin x1 y1 x2 y2;printf(%d\n, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]);}return 0;
}1230. K倍区间
#include cstdio
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;
const int N 100010;int n, k;
LL s[N], cnt[N];int main()
{scanf(%d%d, n, k);for (int i 1; i n; i ) {scanf(%d, s[i]);s[i] s[i - 1];}// for (int i 1; i n; i ) printf(%d , s[i]);LL res 0;cnt[0] ;for (int i 1; i n; i ) {res (LL)cnt[s[i] % k];cnt[s[i] % k] ;}printf(%lld\n, res);return 0;
}4405. 统计子矩阵
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;
const int N 510;
int n, m, k;
int s[N][N];int main()
{scanf(%d%d%d, n, m, k);for (int i 1; i n; i ) for (int j 1; j m; j ) {scanf(%d, s[i][j]);s[i][j] s[i - 1][j];}LL res 0; // 枚举上下边界for (int i 1; i n; i ) for (int j i; j n; j )// 双指针降低一层循环来枚举左右边界for (int l 1, r 1, sum 0; r m; r ) {sum s[j][r] - s[i - 1][r];while (sum k) {sum - s[j][l] - s[i - 1][l];l ;}res r - l 1;}printf(%lld\n, res);return 0;
}
