[ARC172D] Distance Ranking 题解

题目链接：[ARC172D] Distance Ranking

题意：

\(N\) 维空间中有 \(N\) 个点，每个点的每一维坐标都是在 \([0,10^8]\) 上的整数。

已知这些点两两连边的长度大小关系，从小到大给出，每次给出 \(a_i,b_i\) 以表示他们的连边。

求一个满足上述条件的 \(N\) 个点的构造方案。保证有解。（不能有两条边长度相等）

数据范围：

\(3 \le N \le 20,~ 1 \le a_i < b_i \le N~\left(1 \le i \le \frac{N(N-1)}{2}\right)\) 。保证 \(a_i,b_i\) 互不相同。

首先考虑任意两个不同点之间的距离均相等的情况怎么做。

显然这个时候可以构造 \(p_{i,j} = [i=j]\) ，其中 \(p_{i,j}\) 表示点 \(i\) 的第 \(j\) 维坐标。

不过这个 \([0,1]\) 的范围似乎有些小了，不方便我们进行修改，以满足原题的要求。

因此我们可以将其缩放为 \(p_{i,j} = K \times [i=j]\) ，其中 \(K=10^8\) 表示一个足够大的值（确实足够大）。

那么两点之间的距离有 \[ \mathrm{dis}(i, j) = \sum_{k=1}^n (p_{i,k}-p_{j,k})^2 = 2K^2 \] 此时如果我们令 \(p_{i,j} \gets p_{i,j} + 1\) ，则有 \[ \mathrm{dis}(i, j) = \sum_{k=1}^n (p_{i,k}-p_{j,k})^2 = 2K^2 - 2K + \mathcal{O}(1) \] 这里 \(\mathcal{O}(1) \ll 2K\) ，显然也远小于 \(2K^2\) 。

注意到，对于 \(x \ne i \land x\ne j\) 的 \(x\) ，\(\mathrm{dis}(i,x)\) 的变化量也是 \(\mathcal{O}(1)\) 的。

换句话说，如果我们给每个 \(\mathrm{dis}(i,j)\) 都减去一个 \(c_{i,j} \times K\) ，剩下 \(\mathcal{O}(1)\) 的变化率可以忽略不计了。

而 \(2K^2\) 是固定不变的，那么当 \(c_{i,j}\) 互不相同时，影响 \(\mathrm{dis}(i,j)\) 的排名的就只有 \(c_{i,j}\) 了。

于是我们只需要令 \[ p_{a_i,b_i}\gets p_{a_i,b_i} + \left(\frac{n(n-1)}{2} - i + 1\right) \] 这道题就做完了，代码非常简单。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
const int INF = 1e8;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(66))
#define N2 6666

int a[N2], b[N2], p[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    rep(i, 1, n * (n - 1) / 2) cin >> a[i] >> b[i];
    rep(i, 1, n) p[i][i] = INF;
    int o = n * (n - 1) / 2;
    rep(i, 1, n * (n - 1) / 2) { p[b[i]][a[i]] += o; --o; }
    rep(i, 1, n) rep(j, 1, n) cout << p[i][j] << " \n"[j == n];
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/q882qzsa