Perfect Square

1234567890sjx · 2023-10-24 14:49:36 · 题解

一个矩阵是完美的当且仅当这个矩阵中任意的一个元素 a_{i,j} 和她在矩阵分别旋转 90^\circ，180^\circ，270^\circ 后所在的位置当前的元素的值相等。

因为 2\mid n，所以容易发现上面的四个位置分别在矩形的左上角，左下角，右上角和右下角。

枚举左上角的每一个位置，计算让她和另外三个位置的值全部相等需要的最小代价即可。

void slv(int tc = 0) {
    if (tc) {
        cerr << "Test Case " << tc << '\n';
    }
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    int sum = 0;
    for (int i = 1; i <= n / 2; i++) {
        for (int j = 1; j <= n / 2; j++) {
            // (i, j) (j, n - i + 1) (n - j + 1, i) (n - i + 1, n - j + 1)
            int to = max({a[i][j], a[j][n - i + 1], a[n - j + 1][i], a[n - i + 1][n - j + 1]});
            int s = a[i][j] + a[j][n - i + 1] + a[n - j + 1][i] + a[n - i + 1][n - j + 1];
            sum += 4 * to - s;
        }
    }
    cout << sum << '\n';
}