[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