ARC172D

_LHF_ · 2024-02-23 20:27:09 · 题解

很有意思的构造题/诈骗题。

首先我们知道 n 个点确定一个 n-1 维平面，但出题人硬要出成 n 维空间，这是为什么呢？

首先先考虑一个简单的构造：如果我们要求任意两点间的距离全相等，我们能怎么构造。

显然是令 p_{i,j}=[i=j]。

然后考虑如何调整使得题目的要求能被满足。

首先不妨令 p_{i,j}=10^8[i=j]，注意到 K=10^8 很大，我们可以近似看作 +\infty，然后我们进行一些微调。

如果不进行调整，有 dis(p_i,p_j)=\sum_{k=1}^n(p_{i,k}-p_{j,k})^2=2K^2，如果我们把 p_{i,j} 加上 1 的话答案就变成了 2K^2-2K+O(1)，注意到后面的 O(1) 是远小于 2K 和 K^2 的。

再看对于 x\not=i,x\not=j，dis(p_i,p_x) 的变化量也只是 O(1) 的，也就是说我们如果给每一个 dis(p_i,p_j) 都减去一个 c_{i,j}\times K，那么剩下的 O(1) 变化量就可以忽略不计了，而 2K^2 是不会改变的，所以说如果我们保证 c_{i,j} 互不相同，那么影响 dis(p_i,p_j) 的排名的就只有 c_{i,j} 了，直接构造即可。

写出来就是：

scanf("%d",&n);
for(int i=1;i<=n*(n-1)/2;i++) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++) ans[i][i]=1e8;
for(int i=1,s=n*(n-1)/2;i<=n*(n-1)/2;i++) ans[b[i]][a[i]]+=s,s--;

然后我因为 a,b 数组开小了结果罚时两发。