1.[AcWing562.壁画]
题目描述
Thanh 想在一面被均分为 \(N\) 段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分，这表示它的美观程度（如果它的上面有画的话）。
不幸的是，由于洪水泛滥，墙体开始崩溃，所以他需要加快他的作画进度！
每天 Thanh 可以绘制一段墙体。
在第一天，他可以自由的选择任意一段墙面进行绘制。
在接下来的每一天，他只能选择与绘制完成的墙面相邻的墙段进行作画，因为他不想分开壁画。
在每天结束时，一段未被涂颜料的墙将被摧毁（Thanh 使用的是防水涂料，因此涂漆的部分不能被破坏），且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。
Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。
Thanh 想要保证，无论墙壁是如何被摧毁的，他都可以达到至少 \(B\) 的美观总分。
请问他能够保证达到的美观总分 \(B\) 的最大值是多少。
输入格式
第一行包含整数 \(T\)，表示共有 \(T\) 组测试数据。
每组数据的第一行包含整数 \(N\)。
第二行包含一个长度为 \(N\) 的字符串，字符串由数字 \(0∼9\) 构成，第 \(i\) 个字符表示第 \(i\) 段墙面被上色后能达到的美观评分。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 Case #x: y，其中 \(x\) 为组别编号（从 \(1\) 开始），\(y\) 为 Thanh 可以保证达到的美观评分的最大值。
数据范围
\(1≤T≤100,\)
存在一个测试点 \(N=5∗10^6\)，其他测试点均满足 \(2≤N≤100\)
输入样例
4
4
1332
4
9583
3
616
10
1029384756
输出样例
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
样例解释
在第一个样例中，无论墙壁如何被破坏，Thanh 都可以获得 \(6\) 分的美观总分。在第一天，他可以随便选一个美观评分 \(3\) 的墙段进行绘画。在一天结束时，第一部分或第四部分将被摧毁，但无论哪一部分都无关紧要。在第二天，他都可以在另一段美观评分 \(3\) 的墙段上作画。
在第二个样例中，Thanh 在第一天选择最左边的美观评分为 \(9\) 的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体，因为最左边的墙壁被涂上了颜料。在第二天，他可以选择在左数第二段评分为 \(5\) 的墙面上作画。然后右数第二段墙体被摧毁。请注意，在第二天，Thanh 不能选择绘制第三段墙面，因为它不与任何其他作画墙面相邻。这样可以获得 \(14\) 分的美观总分。
解题思路
因为每次被摧毁的墙体都只与一个未被破坏的墙体相邻，因此每次被摧毁的墙体只能是两侧的墙体，因此根据此性质确定最后绘画的墙体长度。根据固定区间长度求解最大值，利用前缀和预处理。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6;
int T;
int sum[N];
int main() {
cin >> T;
for (int i = 1; i <= T; i++) {
int n;
string S;
cin >> n >> S;
// 前缀和预处理
for (int j = 1; j <= n; j++) sum[j] = sum[j - 1] + S[j - 1] - '0';
// 区间长度
int m = (n + 1) / 2;
int maxv = 0;
for (int j = 1; j + m - 1 <= n; j++)
maxv = max(maxv, sum[j + m - 1] - sum[j - 1]);
cout << "Case #" << i << ": " << maxv << "\n";
}
return 0;
}
2.[AcWing1236.递增三元组]
题目描述
给定三个整数数组
\(A=[A_1,A_2,…A_N],\)
\(B=[B_1,B_2,…B_N],\)
\(C=[C_1,C_2,…C_N],\)
请你统计有多少个三元组 \((i,j,k)\) 满足：
\(1≤i,j,k≤N\)
\(A_i<B_j<C_k\)
输入格式
第一行包含一个整数 \(N\)。
第二行包含 \(N\) 个整数 \(A_1,A_2,…A_N\)。
第三行包含 \(N\) 个整数 \(B_1,B_2,…B_N\)。
第四行包含 \(N\) 个整数 \(C_1,C_2,…C_N\)。
输出格式
一个整数表示答案。
数据范围
\(1≤N≤10^5,\)
\(0≤A_i,B_i,C_i≤10^5\)
输入样例
3
1 1 1
2 2 2
3 3 3
输出样例
27
解题思路
提供两种思路，两种思路都是以 \(B\) 数组作为连接。
- 二分。对 \(A\) 和 \(C\) 排序，对于每一个 \(B_i\) 在 \(A\) 中找到小于其的所有数的个数，在 \(C\) 中找到大于其的所有数的个数，这里进行数的查找可以使用二分。此方法的时间复杂度为 \(O(nlogn)\)。
- 前缀和。\(cnt\) 数组统计针对 \(A\) 和 \(C\) 统计每个数的个数，\(s\) 表示 \(cnt\) 的前缀和，即数 \(1\) 至 \(i\) 在 \(A\) 和 \(C\) 中的个数。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long LL;
int n;
int a[N], b[N], c[N];
int cnt[N], s[N];
int as[N], cs[N];
int main() {
scanf("%d", &n);
// 自增是为了方便前缀和计算
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i]++;
for (int i = 1; i <= n; i++) scanf("%d", &b[i]), b[i]++;
for (int i = 1; i <= n; i++) scanf("%d", &c[i]), c[i]++;
for (int i = 1; i <= n; i++) cnt[a[i]]++;
// s[i] 表示数组 a 中从 0 到 i 的数的个数
for (int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
for (int i = 1; i <= n; i++) as[i] = s[b[i] - 1];
memset(cnt, 0, sizeof cnt);
memset(s, 0, sizeof s);
for (int i = 1; i <= n; i++) cnt[c[i]]++;
for (int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
for (int i = 1; i <= n; i++) cs[i] = s[N - 1] - s[b[i]];
LL res = 0;
for (int i = 1; i <= n; i++)
res += (LL) as[i] * cs[i];
printf("%ld", res);
/*
// 二分解法
sort(a + 1, a + n + 1);
sort(c + 1, c + n + 1);
LL res = 0;
for (int i = 1; i <= n; i++) {
int l1 = 1, r1 = n;
while (l1 < r1) {
int mid = l1 + r1 + 1 >> 1;
if (a[mid] < b[i]) l1 = mid;
else r1 = mid - 1;
}
int l2 = 1, r2 = n;
while (l2 < r2) {
int mid = l2 + r2 >> 1;
if (c[mid] > b[i]) r2 = mid;
else l2 = mid + 1;
}
if (a[r1] >= b[i] || c[r2] <= b[i])
continue;
res += (LL) r1 * (n - r2 + 1);
}
printf("%ld", res);
*/
return 0;
}
3.[AcWing4405.统计子矩阵]
题目描述
给定一个 \(N×M\) 的矩阵 \(A\)，请你统计有多少个子矩阵 (最小 \(1×1\)，最大 \(N×M\)) 满足子矩阵中所有数的和不超过给定的整数 \(K\)?
输入格式
第一行包含三个整数 \(N,M\) 和 \(K\)。
之后 \(N\) 行每行包含 \(M\) 个整数，代表矩阵 \(A\)。
输出格式
一个整数代表答案。
数据范围
对于 \(30\%\) 的数据，\(N,M≤20\)，
对于 \(70\%\) 的数据，\(N,M≤100\)，
对于 \(100\%\) 的数据，\(1≤N,M≤500;0≤A_{ij}≤1000;1≤K≤2.5×10^8\)。
输入样例
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
输出样例
19
样例解释
满足条件的子矩阵一共有 \(19\)，包含：
大小为 \(1×1\) 的有 \(10\) 个。
大小为 \(1×2\) 的有 \(3\) 个。
大小为 \(1×3\) 的有 \(2\) 个。
大小为 \(1×4\) 的有 \(1\) 个。
大小为 \(2×1\) 的有 \(3\) 个。
解题思路
最简单的思路，二维前缀和预处理，枚举出每一个子矩阵进行判断，这样时间复杂度是 \(O(n^4)\)。
如何优化？
利用双指针，限定子矩阵上下边界，两个指针指向左右边界，当左指针移动时，子矩阵的值必然减小。
C++代码
#include <iostream>
using namespace std;
const int N = 510;
typedef long long LL;
int n, m, k;
int a[N][N];
LL 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", &a[i][j]);
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + a[i][j];
}
LL res = 0;
for (int i = 1; i <= m; i++) // 上边界
for (int j = i; j <= m; j++) // 下边界
for (int l = 1, r = 1; r <= n; r++) { // 左右边界
while (l <= r && a[r][j] - a[l - 1][j] - a[r][i - 1] + a[l - 1][i - 1] > k)
l++;
if (l <= r)
res += r - l + 1;
}
printf("%lld", res);
return 0;
}