P9582 题解（2023 激励计划评分 6）

· · 题解

Task 1~3

四重循环暴力枚举每一对方格即可。

Task 4~5

保证了 a_i \le 1，也就是每一个方格内的数都相等。

我们考虑每一个位置的方格。

对于在角落的方格，共有 nm-3 个好朋友；

对于在边上的方格，共有 nm-4 个好朋友；

对于在中间的方格，共有 nm-5 个好朋友；

考虑每个位置的方格的数量，与该位置的方格的好朋友的数量相乘再相加即可。

时刻铭记不开 long long 见祖宗。

Task 6~7

由于特殊性质保证了任意两个相邻的方格中的数不相等，所以判定两个方格是否为好朋友的条件等价于这两个方格中的数字是否相同。

那我们开一个桶 c，记录每一个数字出现的次数，根据乘法原理，对于所有中间的数字为 i 的方格，好朋友的数量的总和就是 c_i \times (c_i-1)。

所以答案就是 \sum\limits^9_{i=1} c_i \times (c_i-1)。

Task 8~10

现在相邻的方格中的数可能相等，那我们可以用刚才求出的答案 \sum\limits^9_{i=1} c_i \times (c_i-1) 减去不合法的情况。

而不合法的情况其实就是两个相邻的方格中的数相等。

那么对于每一个方格，我们统计与其相邻且中间的数字相同的方格的数量，将答案减去这个值即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,A=15;
int n,m,a[N][N],c[A];
ll ans;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            c[a[i][j]]++;
        }
    }
    for(int i=1;i<=9;i++) ans=ans+1ll*c[i]*(c[i]-1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==a[i-1][j]) ans--;
            if(a[i][j]==a[i][j-1]) ans--;
            if(a[i][j]==a[i+1][j]) ans--;
            if(a[i][j]==a[i][j+1]) ans--;
        }
    }
    cout<<ans;
    return 0;
}