题解：P11001 [蓝桥杯 2024 省 Python B] 连连看

liuyi0905 · 2024-08-29 19:15:17 · 题解

给定一个 n\times m 的矩阵，要你求出有多少对格子 (i,j) 和 (x,y) 使得 a_{i,j}=a_{x,y} 且 |i-x|=|j-y|>0。

对于每一个格子 (i,j)，我们会发现与它横纵坐标之差相等的格子会与 (i,j) 呈“X”的形状，(i,j) 与在这个“X”中与 a_{i,j} 相等的格子即是满足条件的格子对。

考虑维护每一条斜着的线上元素为 x 的有多少个，c_{0,i,j} 表示在第 i 条正对角线上元素为 j 的格子个数，c_{1,i,j} 同理。这里正对角线表示左下到右上，反对角线表示左上到右下。

在维护 (i,j) 这个格子的 c 时，累加 c_{0,i+j,a_{i,j}} 和 c_{1,i-j+m,a_{i,j}} 即可。注意：

• 在维护反对角线时下标 i-j 可能为负数，所以需要加一个偏移量。
• 在维护正对角线和反对角线时的下标 i+j 和 i-j+m 可能会超出 n 或 m，所以数组要开到两倍大小。

得到了 c，求答案就很容易了。枚举每一个元素，只需将以它为中心的“X”里与它相等的元素数量累加即可。即 c[0][i+j][x]-1+c[1][i-j+m][x]-1。

代码就很容易写出来了：

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const int N=2005;
int n,m,a[N][N],c[2][N][N];
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>a[i][j];
      c[0][i+j][a[i][j]]++;
      c[1][i-j+m][a[i][j]]++;
    }
  }
  LL s=0;
  for(int i=1;i<=n;i++){
    for(int j=1,x;j<=m;j++){
      x=a[i][j];
      s+=max(0,c[0][i+j][x]-1)+max(0,c[1][i-j+m][x]-1);
    }
  }
  cout<<s;
  return 0;
}