P11001 题解

· · 题解

题目分析

这道题的题意比较容易理解，就是求出每一条对角线上相同的数字总共有多少对。

解题思路

暴力

最先想到的是暴力做法，即枚举 n \times m 网格中的每一对点，可利用四重循环求解，时间复杂度为 O(n^2m^2) 。

但是数据范围否定了这种做法。

对于 20\% 的评测用例，1 \leq n, m \leq 50；

对于所有评测用例，1 \leq n, m \leq 1000，1 \leq A_{i,j} \leq 1000。

因此暴力做法会导致超时，但是能拿到 20\% 的部分分。

数学方法

第二个思路为利用数学方法求解。

如果有一条对角线 l 上数字 x 出现了 n 次，那么 l 上的所有 x 两两排列的数量就是 l 上相同数字 x 的对数。

所以我们只需要记录下每条对角线上每个数字出现的次数，再利用上述的方法将所有结果累加起来，就能得到最终的答案。 （似乎也挺暴力的。）

补充一个小知识点：

求在 n 个数中选 m 个数所有排列的数量可以利用下面的公式：

A^m_n=\frac{n!}{(n-m)!}

接下来有一个问题：如何表示每条对角线？

不难发现这样的规律：对于左上到右下的对角线（类似于 \ 这样的）上的所有数，行号与列号的差相等；而对于左下到右上的对角线（类似于 / 这样的）上的所有数，行号与列号的和相等。

根据这个规律我们可得出：如果一个数 x 行号为 i ，列号为 j ，那么 x 所在的左上到右下的对角线编号可表示为 i-j ， x 所在的左下到右上的对角线编号可表示为 i+j 。但要注意：由于 j 有可能大于 i ，所以 i-j 可能会小于零。因此我们可以将所有左上到右下的对角线编号统一加上 1000 保证其非负性。

分析完思路啦，下面是本题 AC 代码。

#include<iostream>
#include<limits.h> 
using namespace std;
int A(int n,int m){ //用于求排列数 
    int res=1;
    for(int i=n-m+1;i<=n;i++){
        res*=i;
    }
    return res;
}
int n,m;
int a[1005][1005];
int bucket1[2005][1005]; //用于统计左上到右下的对角线 
int bucket2[2005][1005]; //用于统计左下到右上的对角线 
int main(){
    cin>>n>>m;
    int maxn=0,minn=INT_MAX; //maxn和minn用于计算循环范围 
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            maxn=max(maxn,a[i][j]);
            minn=min(minn,a[i][j]);
            bucket1[i-j+1000][a[i][j]]++; //记得+1000来保证下标非负 
            bucket2[i+j][a[i][j]]++;
        }
    }
    int sum=0;
    for(int i=1;i<=2001;i++){ //枚举每一条对角线 
        for(int j=minn;j<=maxn;j++){ //枚举每个可能出现的数 
            sum+=A(bucket1[i][j],2)+A(bucket2[i][j],2); //累加排列数 
        }
    }
    cout<<sum;
    return 0;
}