首页 > 代码库 > 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