CFGYM104017B

CFGYM104017B Drone Photo

题意

给一个n*n矩阵，由一个排列构成，取四个点构成一个长方形，使得最小的两个点不在对角线上。

题解

观察出来可得一个合法的矩形肯定有两个顺时针/逆时针递增的L形状序列，那么统计这种序列的个数然后除2既是答案。

代码

//
// Created by mrx on 2023/4/9.
//
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#include <map>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector mat(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)std::cin >> mat[i][j];
    std::vector order_x(n, std::vector<int>(n)), order_y(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
        std::vector<int> tmp(n);
        std::iota(tmp.begin(), tmp.end(), 0);
        std::sort(tmp.begin(), tmp.end(), [&](int a, int b) { return mat[i][a] < mat[i][b]; });
        for (int j = 0; j < n; ++j) order_x[i][tmp[j]] = n - 1 - j;
        std::sort(tmp.begin(), tmp.end(), [&](int a, int b) { return mat[a][i] < mat[b][i]; });
        for (int j = 0; j < n; ++j) order_y[tmp[j]][i] = n - 1 - j;
    }
    
    i64 ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ans += order_x[i][j] * (n - 1 - order_y[i][j]) + order_y[i][j] * (n - 1 - order_x[i][j]);
        }
    }
    std::cout << ans / 2 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    solve();
    
    return 0;
}