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

Alexlulu · 2026-06-08 20:29:02 · 题解

题目传送门 & 更好的阅读体验

我们考虑可能生成等差数列的情况，第一种就是给定的元素中已经生成，那么我们可以直接计数；第二种是通过中间行列或对角线生成的，这类等差数列需要依赖中心值。

我们先来考虑如何判断序列 \{a_1,a_2,a_3\} 是否为等差数列。根据等差数列的定义，当序列中相邻两数的差均相等时，序列为等差数列，故当 a_3-a_2=a_2-a_1 时，序列 \{a_1,a_2,a_3\} 为等差数列。

接着我们来考虑当 a_1,a_3 已知且序列 \{a_1,x,a_3\} 为等差数列时 x 的值是多少。已知序列为等差数列，即 a_3-x=x-a_1，化简得 x=\dfrac{a_1+a_3}{2}。题目中为了使等差数列总数最多，我们需要求所有 4 个 x 中有最多有几个相等。

例如对于样例的第一组数据

中，直接由给定的元素中生成的等差数列有 \{11,9,7\} 一个，而由中间行列和对角线得到的 4 个 x，分别是 5,5,5,9.5，共三个相等，故答案为 1+3=4 个。

最后注意一下小心 4 个 x 中可能有分数且恰好占多数，此时千万不能把它计入答案，因为题目要求缺失的是整数，否则会直接爆零……

::::success[AC 代码]{open}

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T, ans, val[10], g[10][10];

signed main()
{
    cin.tie(0) -> sync_with_stdio(false);
    cin >> T;
    for (int cs = 1; cs <= T; cs++)
    {
        ans = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (!(i == 1 && j == 1)) cin >> g[i][j]; // 输入 g，跳过中间值
        ans += (g[0][2] - g[0][1] == g[0][1] - g[0][0]);
        ans += (g[2][2] - g[2][1] == g[2][1] - g[2][0]);
        ans += (g[2][0] - g[1][0] == g[1][0] - g[0][0]);
        ans += (g[2][2] - g[1][2] == g[1][2] - g[0][2]);
        // 计算直接由给定的元素中生成的等差数列数量
        val[1] = g[1][2] + g[1][0];
        val[2] = g[2][1] + g[0][1];
        val[3] = g[2][2] + g[0][0];
        val[4] = g[0][2] + g[2][0];
        // 计算 4 个 x
        int maxn = 0, cnt;
        for (int i = 1; i <= 4; i++)
        {
            int num = val[i];
            // 分别将 4 个 x 作为相等值计算
            if (num % 2) continue; // 跳过分数情况！
            cnt = 0;
            cnt += (val[1] == num);
            cnt += (val[2] == num);
            cnt += (val[3] == num);
            cnt += (val[4] == num);
            maxn = max(maxn, cnt);
            // 取中间行列和对角线得到的等差数列数量的最大值
        }
        ans += maxn;
        cout << "Case #" << cs << ": " << ans << '\n'; // 记得按格式输出
    }
    return 0;
}

::::