首页 > 代码库 > 洛谷 U360 子矩阵 （NOIP模拟赛T1）题解
洛谷 U360 子矩阵 （NOIP模拟赛T1）题解
题目链接：https://www.luogu.org/problem/show?pid=U360
题目背景
夏令营
题目描述
小A有一个N×M的矩阵，矩阵中1~N*M这(N*M)个整数均出现过一次。现在小A在这个矩阵内选择一个子矩阵，其权值等于这个子矩阵中的所有数的最小值。小A想知道，如果他选择的子矩阵的权值为i(1<=i<=N×M)，那么他选择的子矩阵可能有多少种？小A希望知道所有可能的i值对应的结果，但是这些结果太多了，他算不了，因此他向你求助。
输入输出格式
输入格式：
第一行，两个整数N, M。
接下来的N行，每行M个整数，表示矩阵中的元素。
输出格式：
N×M行，每行一个整数，其中第i行的整数表示如果小A选择的子矩阵权值为i，他选择的子矩阵的种类数。
输入输出样例
输入样例#1：
2 32 5 16 3 4
输出样例#1：
645111
分析：
这题是听WZY大佬和DYZ大佬讲的。
猛一看这题好像可以用暴力，但是显然矩阵并不是一个规则的矩形，暴力枚举边界的后果就是绝对超时。
考虑使用部分枚举扫描列、单调栈。
首先我们假想两条线，就是子矩阵的上下边界，用两个for循环从上往下扫。
一开始，这两条线是重合的，都在矩阵的第一行。此时我们记录下每一列的值，作为子矩阵在某一列的最小值（因为此时的子矩阵只有这一行，也就是每列只有一个数）。
然后把一条线往下挪，每次挪一行，用新的行中每一列的数与“最小值”作比较，更新“最小值”。（递推求最小值）
这时候两条线之间就形成了一个空间，选择每一列的当前的最小值，向左右方向沿直线扩展，直到遇到一个比它更小的数为止，这时它的上、下、左、右边界就围成了一个矩阵。记录下此时对于这个最小值生成的子矩阵的数量（公式：（K-L+1）*(R-K+1) , 其中K为当前选择的列，L为往左扩展最远到达的列，R为往右扩展最远到达的列）。
上面的计算用单调栈来实现。
同理继续向下递推，可以计算出每一个点的子矩阵数。随着边界的移动，同一个点可能会被计算多次，也就是说这个矩阵不是一个标准的矩形，因此最后应该把每一个点计算出的多个结果相加，得到正确结果。
AC代码（由WZY大佬提供）：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 inline void read(int &x){x = 0;char ch = getchar();char c = ch;while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar();if(c == ‘-‘)x = -x;} 7 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;} 8 inline int max(int a, int b){return a > b ? a : b;} 9 inline int min(int a, int b){return a < b ? a : b;}10 11 const int INF = 0x3f3f3f3f;12 const int MAXN = 5000 + 10;13 const int MAXM = 100000;14 15 int n,m,num[MAXN][MAXN];16 int stack[MAXM], top;17 int mi[MAXM];18 int L[MAXM],R[MAXM];19 int ans[MAXM];20 21 int main()22 {23 read(n);read(m);24 for(int i = 1;i <= n;++ i)25 for(int j = 1;j <= m;++ j)26 read(num[i][j]);27 //枚举上面的行i28 for(register int i = 1;i <= n;++ i)29 {30 //注意清为最大值 31 memset(mi, 0x3f, sizeof(mi));32 33 //枚举i以下的行j 34 for(register int j = i;j <= n;++ j)35 {36 //求得行[i,j]范围内的每一列的最小值 37 for(register int k = 1;k <= m;++ k)38 mi[k] = min(mi[k], num[j][k]);39 40 41 //正向扫描求R，维护一个递增（或相等）单调栈42 for(register int k = 1;k <= m;++ k)43 {44 while(top && mi[k] < mi[stack[top]])45 {46 R[stack[top]] = k - 1;47 -- top;48 }49 stack[++top] = k;50 }51 while(top)52 {53 R[stack[top]] = m;54 -- top;55 }56 57 //反向扫描求L，维护一个递增（或相等）单调栈58 for(int k = m;k >= 1;k --)59 {60 while(top && mi[k] < mi[stack[top]])61 {62 L[stack[top]] = k + 1;63 -- top;64 }65 stack[++top] = k;66 }67 while(top)68 {69 L[stack[top]] = 1;70 -- top;71 }72 73 //扫描列，累加答案 74 for(register int k = 1;k <= m;k ++)75 {76 ans[mi[k]] += (k - L[k] + 1) * (R[k] - k + 1);77 } 78 }79 }80 register int tmp = n * m;81 for(register int i = 1;i <= tmp;++ i)82 {83 printf("%d\n", ans[i]); 84 }85 return 0;86 }
洛谷 U360 子矩阵 （NOIP模拟赛T1）题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。