P11001 [蓝桥杯 2024 省 Python B] 连连看
Love_13_always
·
·
题解
我们先考虑暴力（因为数据量只有 $1000$）。
每次只需斜向下判定（因为是对角线），最后再将结果乘以二即可。
时间复杂度 $O(nm^2)$。极端条件是 $10^9$，很明显过不了，但也是拿到 $80$ 分的高分。
```cpp
#include<iostream>
#include<cmath>
#define lowbit(x) (x & -x)
using namespace std;
inline int read() {
char c = getchar();
int _num_in_ = 0, _num_sign_ = 1;
for(; !isdigit(c); c = getchar())
if(c == '-') _num_sign_ = -1;
for(; isdigit(c); c = getchar())
_num_in_ = (_num_in_ << 3) + (_num_in_ << 1) + (c ^ 48);
return _num_in_ * _num_sign_;
}
int a[1001][1001], n, m, cnt, y;
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
for(int k = 1; k <= m; k++) {
y = i - abs(j - k);
if(y > 0 && j != k)
if(a[y][k] == a[i][j])
++cnt;
}
cout << cnt * 2;
return 0;
}
```
可见即使将读入改为快读，去掉所有宏定义，甚至连万能头都去了，还是会超时。
说明这个代码仍然是有待优化的。
把问题简化一下其实就在求求每一条对角线上相同的数字总共有多少对，那么可以设每次对应一个数在判定时记录单个方向相同的数的个数为 $x$，每次扫描完之后，将结果加上 $x(x−1)$ 即可。
此时应定义两个二维数组 $vis1$ 和 $vis2$ 分别记录像左下和右下判定时经过的点以防止重复扫描
时间复杂度 $O(nm)$，可以理解是优化后的 $O(nm^2)$。
```cpp
#include<iostream>
#include<cmath>
using namespace std;
inline int read() {
char c = getchar();
int _num_in_ = 0, _num_sign_ = 1;
for(; !isdigit(c); c = getchar())
if(c == '-') _num_sign_ = -1;
for(; isdigit(c); c = getchar())
_num_in_ = (_num_in_ << 3) + (_num_in_ << 1) + (c ^ 48);
return _num_in_ * _num_sign_;
}
int a[1001][1001], n, m, ans, y, cnt;
bool vis1[1001][1001], vis2[1001][1001];
signed main() {
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
a[i][j] = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
cnt = 0;
for(int k = 1; k < j; k++) {
if(vis1[i][j]) break;
if(i + j - k > n) continue;
if(a[i + j - k][k] == a[i][j]) {
++cnt;
vis1[i + j - k][k] = true;
}
}
ans += cnt * (cnt + 1);
cnt = 0;
for(int k = j + 1; k <= m; k++) {
if(vis2[i][j]) break;
if(i + k - j > n) continue;
if(a[i + k - j][k] == a[i][j]) {
++cnt;
vis2[i + k - j][k] = true;
}
}
ans += cnt * (cnt + 1);
}
cout << ans;
return 0;
}
```