题目链接：https://atcoder.jp/contests/arc172/tasks/arc172_d

题目大意：请你构造 $n$ 个 $n$ 维空间的整点，满足两点间距离的大小排序符合题目给的顺序。

做法

真TM人类智慧，根本想不到。

准确来说有想过先构造使得每条边都一样长，然后再微调，但是压根没想到微调的具体方法。

简单来说，设第 $i$ 个点的坐标是 $(a_{i,1},a_{i,2},…,a_{i,n})$ 。

先令 $a_{i,j}=[i=j]*K$ ，其中 $K$ 是一个很大的数字，显然，这样能使任意两点间的距离都等于 $\sqrt{2}K$ 。

现在的问题是怎么微调？我们假设给 $a_{i,1},a_{i,2},…,a_{i,n}$ 都加个相对于 $K$ 的小量，那么 $i$ 与别的点的距离会怎样变化呢?

将式子列出来可以发现，对于 $i,j$ 的距离的平方可以大致写成 $2K^2+c*K+O(1)$ ，其中 $c$ 与 $a_{i,i},a_{i,j}$ 有关，可以发现，这个式子的三个部分分别对应不同的量级。

对应任意两点的距离，都有 $2K^2$ 这一项，因此如果 $c*K$ 不一样，就可以用这一项控制相对大小了，显然此时 $O(1)$ 不影响相对大小。

接下来就很简单了，随便口胡一下就行了。

时间复杂度：$O(n^2)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=30;
int a[N][N];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)a[i][i]=1e6;
    for(int i=1;i<=n*(n-1)/2;i++){
        int x,y;scanf("%d%d",&x,&y);
        a[x][y]+=n*(n-1)/2-i+1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)printf("%d ",a[i][j]);
        printf("\n");
    }
    return 0;
}

哎，菜就得多练了，根本想不到。

但多练真的有用吗？