题解：P16849 [GKS 2021 #D] Arithmetic Square

zhouhuan2013 · 2026-06-08 18:58:16 · 题解

题目传送门

一道非常基础的数学题。

我们可以发现，只有这个 3 \times 3 网格的中心格子是空出来的，因此就可以想到暴力枚举。但是观察数据范围后，可以感觉到暴力枚举中心格子大概率会超时，因此我们考虑优化枚举范围。

观察网格可以发现，只有中间行，中间列，从左上到右下的对角线和从右上到左下的对角线这 4 条线会受到中间数的影响。因此这 4 条线想要成为等差数列，都可以确定一个唯一的中间数 mid。由此，我们只需要枚举 4 个 mid 的取值，然后对于每个 mid，统计 8 条线中有多少条线构成等差数列即可。这样大大地优化了算法的时间复杂度。

代码如下。

#include<bits/stdc++.h>
using namespace std;
bool check(int x,int y,int z){
    return 2*y==x+z;//判断是否为等差数列
}
int main(){
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        int g[3][3],p[5],ans=0;
        cin>>g[0][0]>>g[0][1]>>g[0][2];
        cin>>g[1][0]>>g[1][2];
        cin>>g[2][0]>>g[2][1]>>g[2][2];
        p[1]=g[1][0]+g[1][2];
        p[2]=g[0][1]+g[2][1];
        p[3]=g[0][0]+g[2][2];
        p[4]=g[0][2]+g[2][0];
        for(int j=1;j<=4;j++){//枚举
            int mid=p[j]/2,cnt=0;
            if(check(g[0][0],g[0][1],g[0][2]))
                cnt++;
            if(check(g[1][0],mid,g[1][2]))
                cnt++;
            if(check(g[2][0],g[2][1],g[2][2]))
                cnt++;
            if(check(g[0][0],g[1][0],g[2][0]))
                cnt++;
            if(check(g[0][1],mid,g[2][1]))
                cnt++;
            if(check(g[0][2],g[1][2],g[2][2]))
                cnt++;
            if(check(g[0][0],mid,g[2][2]))
                cnt++;
            if(check(g[0][2],mid,g[2][0]))
                cnt++;
            ans=max(ans,cnt);
        }
        cout<<"Case #"<<i<<": "<<ans<<'\n';
    }
    return 0;
}