题解：P11001 [蓝桥杯 2024 省 Python B] 连连看
yl1740
·
·
题解
题目大意
给定一个矩阵，求其中每一条斜线中数字相同的数对的个数（每一对重复算两次）。
解法
这个数据大小显然不能直接暴力枚举（ O(n^{2}m) 左右的复杂度），这里可以通过空间节省时间。
预处理
首先在输入时进行预处理，使用桶并把它处理成斜线格式。
| x\y |
1 |
2 |
| 1 |
1 |
2 |
| 2 |
2 |
3 |
| 3 |
3 |
2 |
具体方法（以样例为例）：
先看每一条斜向上的线，不难发现其横坐标 j 和纵坐标 i 之和相等（如 3+1=2+2=2 ）。
所以有 u[i+j][x]++; ( x 即为 A_{i,j} )。
同理，斜向下的线则有 i 与 j 之差相等的共同点。
不过由于 i 与 j 的大小不确定，所以这里下标都加上一千( A_{i,j} 的最大值)以防止数组越界，所以有 d[1000+i-j][x]++; 。
计算答案
对于每一条斜线上，若有 x 个相同的数，则有 x(x-1) 个符合要求的数对。
原因：
$x=3$ 时，有一和二，一和三，二和三三种，重复则有六对。
依次类推，当 $x=k$ 时，共有 $k(k-1)/2$ 种（高斯求和），所以有 $k(k-1)$ 对。
用变量 $ans$ 累加答案即可。
## AC code：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,u[2001][2001],d[2001][2001],x,ans;
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&x);
u[i+j][x]++;
d[1000+i-j][x]++;
}
}
for(int i=1;i<=2000;i++)
{
for(int j=1;j<=2000;j++)
{
ans+=(-1+u[i][j])*u[i][j];
ans+=(-1+d[i][j])*d[i][j];
}
}
}
cout<<ans;
return 0;
}
```