HDU 5749 BestCoder Round #84 Colmerauer（暴力贡献）

HDU 5749 BestCoder Round #84 Colmerauer（暴力贡献）

Colmerauer

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 220    Accepted Submission(s): 94

Problem Description

Peter has an n×m matrix M. Let S(a,b) be the sum of the weight all a×b submatrices of M. The weight of matrix is the sum of the value of all the saddle points in the matrix. A saddle point of a matrix is an element which is both the only largest element in its column and the only smallest element in its row. Help Peter find out all the value ofS(a,b). Note: the definition of saddle point in this problem may be different with the definition you knew before.

Input

There are multiple test cases. The first line of input contains an integerT, indicating the number of test cases. For each test case: The first contains two integers n and m(1≤n,m≤1000) -- the dimensions of the matrix. The next n lines each contain m non-negative integers separated by spaces describing rows of matrix M (each element of M is no greater than 106).

Output

For each test case, output an integerW=(∑a=1n∑b=1ma⋅b⋅S(a,b)) mod 232.

Sample Input

3 2 2 1 1 1 1 3 3 1 2 3 4 5 6 7 8 9 3 3 1 2 1 2 3 1 4 5 2

Sample Output

4 600 215

Source

​​BestCoder Round #84​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5751​​​ ​​5750​​​ ​​5746​​​ ​​5745​​​ ​​5744​​

题解：

Peter有一个n×m的矩阵M.定义S(a,b)为M的所有大小为a×b的子矩阵的权值和.一个矩阵的权值是这个矩阵所有鞍点的值的和.在矩阵中,一个数在所在行中是唯一的最小值,在所在列中是唯一的最大值,则被称为鞍点.帮助Peter找出所有S(a,b)的值.

输出：

已知一个点的Up,Down,Left,Right，即上下左右的扩展范围，然后计算鞍点对答案的贡献。

把所有可能的矩形的长算出来，得到和，宽也是一样，然后按照乘法原理乘起来就好。

AC代码：

//#include#include#include#include#include#include#define N 1010using namespace std;int n,m;int a[N][N];int stk[N],top;int L[N][N],R[N][N],U[N][N],D[N][N];int readint(){ char c; while((c=getchar())&&!(c>='0' && c<='9')); int ret= c- 48; while((c=getchar())&&( c>='0' && c<='9')) ret = ret * 10 + c-48; return ret;}unsigned int calc(int l,int x,int r){ unsigned int d1=r-x+1; unsigned int d2=x-l+1; unsigned int ret=d1 * (d1+1) / 2 * d2 + d2* (d2-1)/2 *d1; return ret;}int main(){ int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=readint(); } } for(int i=1;i<=n;i++) { top=0; for(int j=1;j<=m;j++) { while(top && a[i][stk[top-1]] > a[i][j]) --top; if(top==0) L[i][j]=1; else L[i][j]=stk[top-1]+1; stk[top++]=j; } } for(int i=1;i<=n;i++) { top=0; for(int j=m;j>=1;--j) { while(top && a[i][stk[top-1]] > a[i][j]) --top; if(top==0) R[i][j]=m; else R[i][j] = stk[top-1] - 1; stk[top++] = j; } } for(int i=1;i<=m;i++) { top=0; for(int j=1;j<=n;j++) { while(top && a[stk[top-1]][i] < a[j][i]) --top; if(top==0) U[j][i]=1; else U[j][i] = stk[top-1]+1; stk[top++]=j; } } for(int i=1;i<=m;i++) { top=0; for(int j=n;j>=1;--j) { while(top && a[stk[top-1]][i] < a[j][i]) --top; if(top==0) D[j][i]=n; else D[j][i] = stk[top-1]-1; stk[top++]=j; } } unsigned int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ans += (unsigned int)a[i][j]*calc(L[i][j],j,R[i][j])*calc(U[i][j],i,D[i][j]); } } printf("%u\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。