首页 > 代码库 > ZOJ 3955 Saddle Point
ZOJ 3955 Saddle Point
排序。
枚举每一个格子,计算这个格子在多少矩阵中是鞍点,只要计算这一行有多少数字比他大,这一列有多少数字比他小,方案数乘一下就是这个格子对答案做出的贡献。
#include<bits/stdc++.h>using namespace std;int n,m;long long mod = 1e9+7;int a[1200][1200];int num1[1200][1200];int num2[1200][1200];long long b[1200];struct X{ int id,val;}s[1200];bool cmp1(X a,X b){ return a.val<b.val;}bool cmp2(X a,X b){ return a.val>b.val;}int main(){ b[0]=1; for(int i=1;i<=1000;i++) b[i]=(b[i-1]*2)%mod; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(num1,0,sizeof num1); memset(num2,0,sizeof num2); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) s[j].id=j, s[j].val=a[i][j]; sort(s+1,s+1+m,cmp2); for (int j=1,k;j<=m;j=k) { for (k=j;k<=m&&s[k].val==s[j].val;k++) { num1[i][s[k].id]=j-1; } } } for(int j=1;j<=m;j++) { for(int i=1;i<=n;i++) s[i].id=i, s[i].val=a[i][j]; sort(s+1,s+1+n,cmp1); for (int i=1,k;i<=n;i=k) { for (k=i;k<=n&&s[k].val==s[i].val;k++) { num2[s[k].id][j]=i-1; } } } long long ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { long long A=b[num1[i][j]],B=b[num2[i][j]]; long long p=A*B%mod; ans=(ans+p)%mod; } } printf("%lld\n",ans); } return 0;}
ZOJ 3955 Saddle Point
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。