编程题
B4415 排兵布阵
【题目来源】
洛谷：B4415 [GESP202509 四级] 排兵布阵 - 洛谷
【题目描述】
作为将军，你自然需要合理地排兵布阵。地图可以视为 \(n\) 行 \(m\) 列的网格，适合排兵的网格以 \(1\) 标注，不适合排兵的网格以 \(0\) 标注。现在你需要在地图上选择一个矩形区域排兵，这个矩形区域内不能包含不适合排兵的网格。请问可选择的矩形区域最多能包含多少网格？
【输入】
第一行，两个正整数 \(n,m\)，分别表示地图网格的行数与列数。
接下来 \(n\) 行，每行 \(m\) 个整数 \(a_{i,1},a_{i,2},…,a_{i,m}\)，表示各行中的网格是否适合排兵。
【输出】
一行，一个整数，表示适合排兵的矩形区域包含的最大网格数。
【输入样例】
4 3
0 1 1
1 0 1
0 1 1
1 1 1
【输出样例】
4
【算法标签】
《洛谷 B4415 排兵布阵》 #枚举# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 15; // 定义矩阵的最大尺寸int n, m; // 矩阵的行数和列数
int maxn = 0; // 存储全1子矩阵的最大面积
int a[N][N]; // 存储原始矩阵
int sa[N][N]; // 存储二维前缀和数组int main()
{// 输入矩阵的行数和列数cin >> n >> m;// 输入矩阵数据for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}// 计算二维前缀和数组for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){sa[i][j] = sa[i-1][j] + sa[i][j-1] - sa[i-1][j-1] + a[i][j];}}// 枚举所有可能的子矩阵for (int x1 = 1; x1 <= n; x1++) // 子矩阵左上角行坐标{for (int y1 = 1; y1 <= m; y1++) // 子矩阵左上角列坐标{for (int x2 = x1; x2 <= n; x2++) // 子矩阵右下角行坐标{for (int y2 = y1; y2 <= m; y2++) // 子矩阵右下角列坐标{// 计算子矩阵的和int t = sa[x2][y2] - sa[x2][y1-1] - sa[x1-1][y2] + sa[x1-1][y1-1];// 如果子矩阵的和等于其面积（即全1矩阵）if (t == ((x2 - x1 + 1) * (y2 - y1 + 1))){// 更新最大面积maxn = max(maxn, t);}}}}}// 输出最大全1子矩阵的面积cout << maxn << endl;return 0;
}
【运行结果】
4 3
0 1 1
1 0 1
0 1 1
1 1 1
4
B4416 最长连续段
【题目来源】
洛谷：B4416 [GESP202509 四级] 最长连续段 - 洛谷
【题目描述】
对于 \(k\) 个整数构成的数组 \([b_1,b_2,…,b_k]\)，如果对 \(1≤i\)\(<\)\(k\) 都有 \(b_{i+1}\)\(=\)\(b_{i+1}\)，那么称数组 \(b\) 是一个连续段。
给定由 \(n\) 个整数构成的数组 \([a_1,a_2,…,a_n]\)，你可以任意重排数组 \(a\) 中元素顺序。请问在重排顺序之后，\(a\) 所有是连续段的子数组中，最长的子数组长度是多少？
例如，对于数组 \([1,0,2,4]\)，可以将其重排为 \([4,0,1,2]\)，有以下 \(10\) 个子数组：
\([4],[0],[1],[2],[4,0],[0,1],[1,2],[4,0,1],[0,1,2],[4,0,1,2]\)其中除 \([4,0],[4,0,1],[4,0,1,2]\) 以外的子数组均是连续段，因此是连续段的子数组中，最长子数组长度为 \(3\)。
【输入】
第一行，一个正整数 \(n\)，表示数组长度。
第二行，\(n\) 个整数 \(a_1,a_2,…,a_n\)，表示数组中的整数。
【输出】
一行，一个整数，表示数组 \(a\) 重排顺序后，所有是连续段的子数组的最长长度。
【输入样例】
4
1 0 2 4
【输出样例】
3
【算法标签】
《洛谷 B4416 最长连续段》 #离散化# #排序# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 定义数组最大长度int n; // 输入数字的个数
int cur = 0; // 记录去重后的数字个数
int maxn = 0; // 存储最长连续序列的长度
int a[N]; // 存储去重后的数字
map<int, int> mp; // 哈希表，用于判断数字是否重复int main()
{// 输入数字个数cin >> n;// 输入数字并去重for (int i = 1; i <= n; i++){int x;cin >> x;// 如果数字未出现过，则加入数组if (mp[x] == 0){a[++cur] = x;}// 标记数字已出现mp[x] = 1;}// 对去重后的数字进行排序sort(a + 1, a + cur + 1);// 计算最长连续序列的长度int cnt = 1; // 当前连续序列的长度for (int i = 2; i <= cur; i++){// 如果当前数字与前一个数字连续if (a[i] == a[i - 1] + 1){cnt++;}// 如果不连续，则更新最大值并重置计数器else{maxn = max(maxn, cnt);cnt = 1;}}// 处理最后一个连续序列maxn = max(maxn, cnt);// 输出最长连续序列的长度cout << maxn << endl;return 0;
}
【运行结果】
4
1 0 2 4
3