前缀和
截断数组（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;
}
}
|
四平方和
求一个数，他恰好能写成4个正整数的平方和，并按顺序输出。
数据范围
$$0 < N < 5 \times 10 ^ 6$$
题解：
先预处理出一对能求和的，模拟成哈希表存值，在暴力枚举a和b，通过查询数组发现如果存在的话，那么说明是一定有解的。
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
| void JiuCherish(){
int n;
std::cin >> n;
memset(R,-1,sizeof R);
for(int i=0;i * i <= n;i++) {
for(int j=i;j * j + i * i <= n;j++) {
int now = j * j + i * i;
if(R[now] == -1) {
R[now] = i;
}
}
}
for(int i=0;i*i<=n;i++) {
for(int j=i;j*j + i*i <= n;j++) {
int last = n - (j * j + i * i);
if(R[last] == -1) {
continue;
}
int c = R[last];
int d = sqrt(last - c * c);
std::cout << i << " " << j << " " << c << " " << d << endl;
return;
}
}
}
|
分巧克力
儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
- 形状是正方形，边长是整数
- 大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？
数据范围
$$1 \leq n,k \leq 10^5$$
$$1 \leq H_i,W_i \leq 10^5$$
题解：
直接二分就好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool check(int x,int n,int k) {
int res = 0;
for(int i=1;i<=n;i++) {
res += (h[i] / x) * (w[i] / x);
if(res >= k) return true;
}
return res >= k;
}
void JiuCherish(){
int n,k;
std::cin >> n >> k;
for(int i=1;i<=n;i++) std::cin >> h[i] >> w[i];
int l = 0,r = 1e5 + 10;
while(l < r) {
int mid = l + r + 1 >> 1;
if(check(mid,n,k)) l = mid;
else r = mid - 1;
}
std::cout << l << endl;
}
|
双指针
字符串删减
给定一个由 n 个小写字母构成的字符串。
现在，需要删掉其中的一些字母，使得字符串中不存在连续三个或三个以上的 x。
请问，最少需要删掉多少个字母？
如果字符串本来就不存在连续的三个或三个以上 x，则无需删掉任何字母。
数据范围
$$3 \leq n \leq 100$$
题解：
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void JiuCherish(){
int n;
std::string s;
std::cin >> n >> s;
int cnt = 0;
for(int i=0;i<n;i++) {
int j = i;
while(s[j] == s[i] && s[i] == 'x' && j < n) j++;
if(j - i > 2) {
cnt += (j - i - 2);
}
i = j;
}
std::cout << cnt << endl;
}
|
最长连续不重复子序列
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
数据范围
$$1 \leq n \leq 10^5$$
1
2
3
4
5
6
7
8
9
10
11
12
| void JiuCherish(){
int n;
std::cin >> n;
for(int i=1;i<=n;i++) std::cin >> a[i];
int ans = 0;
for(int i=1,j=1;i<=n;i++) {
b[a[i]]++;
while(b[a[i]] > 1) --b[a[j++]];
ans = std::max(ans,i - j + 1);
}
std::cout << ans << endl;
}
|
数组元素的目标和
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i] + B[j] = x 的数对 (i,j) 。
数据保证有唯一解。
数据范围
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,m,x;
std::cin >> n >> m >> x;
for(int i=1;i<=n;i++) std::cin >> a[i];
for(int i=1;i<=m;i++) std::cin >> b[i];
for(int i=1;i<=n;i++) {
int y = x - a[i];
int l = 1,r = m;
while(l <= r) {
int mid = l + r >> 1;
if(b[mid] == y) {
std::cout << i - 1 << " " << mid - 1 << endl;
return;
} else if(b[mid] > y) {
r = mid - 1;
} else {
l = mid + 1;
}
}
}
}
|
判断子序列
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
数据范围
$$1 \leq n \leq m \leq 10^5$$
$$-10^9 \leq a_i,b_i \leq 10^9$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void JiuCherish(){
int n,m;
std::cin >> n >> m;
for(int i=1;i<=n;i++) std::cin >> a[i];
for(int i=1;i<=m;i++) std::cin >> b[i];
int now = 1;
for(int i=1;i<=m;) {
if(a[now] == b[i] && now < n + 1) {
now++;
i++;
} else {
i++;
}
}
std::cout << (now == n + 1 ? "Yes" : "No") << endl;
}
|
日志统计
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。
其中每一行的格式是：
表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。
给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。
数据范围
$$1 \leq K \leq N \leq 10^5 $$
$$0 \leq ts,id \leq 10^5$$
$$1 \leq D \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
| struct Node {
int x,y;
}t[MAXN];
bool cmp(Node a,Node b) {
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
void JiuCherish(){
int n,d,k;
std::cin >> n >> d >> k;
for(int i=0;i<n;i++) std::cin >> t[i].x >> t[i].y;
std::sort(t,t + n,cmp);
for(int i=0,j=0;i<n;i++) {
int now = t[i].y;
cnt[now]++;
while(abs(t[i].x - t[j].x) >= d && j < n) {
cnt[t[j].y]--;
j++;
}
if(cnt[t[i].y] >= k) {
ans[t[i].y] = true;
}
}
for(int i=0;i<=100005;i++) {
if(ans[i]) std::cout << i << endl;
}
}
|