P11001【连连看】题解

· · 题解

这道题有一定的思维难度，不过不是特别难想。

题意简述

给定一个矩阵，求有多少对点值相等并且在同一个正方形的对角线上的两个顶点。从 \lceil 说明/提示 \rfloor 中可以看出，一对点需要计算两次。

样例分析

1 2
2 3
3 2

我们可以结合样例理解题意，如上图。我们可以看出两个正方形，分别是

1 2
2 3

和

2 3
3 2

第一个正方形，两个 2 位于从右上到左下的对角线上。

第二个正方形，两个 2 和两个 3 分别在两条对角线上。

大致思路

通过样例，我们可以猜测，我们是否可以通过对角线来计算答案呢？

我们依旧结合样例来验证这个思路。观察可知，共有 4 条对角线，分别是 (1,1)\to (2,2)，(2,1)\to (3,2)，(1,2)\to (2,1)，(2,2)\to (3,1)。这些对角线的顶点的值相等的有 3 对，每对要计算 2 次，所以答案为 6。

另造一组样例试试。

1 1 1
1 1 1
1 1 1

共有 6 条对角线：

最终答案为 (1+3+1+1+3+1)\times 2=20，而手算出的答案也相同。

并且，根据这个样例，可以分析得知，对于一条对角线上的 n 个相同的数，会使答案增加 [1+2+3+\cdots + (n-2)+(n-1)]\times 2=n\times(n-1)。这个问题类似于一条直线上有 n 个点，求有多少条线段。

根据上述思路，我们可以遍历所有对角线，统计每条对角线上的数字以及数量，计算贡献即可。

警示后人

对于打暴力的玩家 （我是不会告诉你我一开始就是打的暴力的），分两种情况。

  1. 20 pts，\Theta(n^4)，枚举点对。
  2. 35~40 pts，\Theta(n^3)，枚举顶点和正方形边长。

可见暴力拿不到高分，建议写正解。

时间复杂度

总共有 2\times(n + m - 1) 条对角线，忽略常数，约 n+m 条。每条对角线最长 \min(n,m)，视为 n。所以总时间复杂度约为 \Theta((n+m)\times n)。

作者实测，本题用 C++ 14(GCC 9) 是最快的。开 O2 时间 700ms，不开 O2 时间 1.1s，当前最优解。?

每个人有自己的写法，所以代码就不放了，留给读者自己发挥，并且真挚地希望读者都能够彻底理解这道题的原理。