直播看着看着发现题解还没写，反正题目比较简单，我就随便写一下题解然后就接着去浪吧。

P.S. 写好一句话题解被吕老师叫回来重写了，伤心到变形。

感觉这一套题虽然总体难度不大，但是细节比较多，套上捆绑还是比较恶心的..而且验题的时候感觉样例比较弱（造题的不是我我不背锅）

看了一下榜感觉这个难度挺兹瓷的？以后就按照这个出吧。

题目排列顺序

from jiry_2，数据 from cy

算法一

聪明的你肯定发现了把所有位置按照权值第一关键字升序，下标第二关键字降序排序，依次分配 $1$ 到 $n$ 这 $n$ 个数就直接 work 了。

咦我好像不会排序那怎么办办呢？只好写个冒泡排序了。

时间复杂度 $O(n^2)$，期望得分 $60$ 分。

算法二

哇我好像知道一个叫做 std::sort 的东西耶，赶紧来试一试吧。

时间复杂度 $O(n \log n)$，期望得分 $100$ 分。

题目交流通道

from jiry_2，数据 from SkyDec

算法一

先来考虑 $d_{u,v}>0$ 的情况。

对于边 $(u,v)$，我们先来看是否存在一个点 $k$ 满足 $d_{u,v}=d_{u,k}+d_{k,v}$，如果不存在这样的 $k$，那么这条边的权值就只能是 $d_{u,v}$，否则这条边只要大于等于 $d_{u,v}$ 就可以了，即有 $K-d_{u,v}+1$ 种方案。把所有边的方案乘起来就可以了。

时间复杂度 $O(n^3)$，期望得分 $30$ 分。

算法二

考虑边可以等于 $0$ 的情况，这时 $d_{u,v}=0$ 的边肯定在图中连成了若干个团。我们把每一个团给缩起来。

两个团之间的点对距离一定是相等的，考虑团与团之间的边，此时相当于有重边的 $d_{u,v}>0$ 的情况。假设这是一条 $a$ 重边，如果存在 $k$ 有 $d_{u,v}=d_{u,k}+d_{k,v}$，那么所有边只要大于等于 $d_{u,v}$ 就可以了，即有 $(K-d_{u,v}+1)^a$ 种方案。如果不存在，那么至少要有一条边等于 $d_{u,v}$，其他边都要大于它，即有 $(K-d_{u,v}+1)^a-(K-d_{u,v})^a$ 种方案。

考虑团内部的边，每个团肯定由 $0$ 的边连成了一个联通块，这是一个经典的容斥，令 $f_i$ 为 $n$ 个点的距离为 $0$ 的团的方案数，$g_i$ 为 $n$ 个点的图的方案数。则有 $g_n=(K+1)^{\binom{n}{2}}$，$f_n=g_n-\sum_{i=1}^{n-1} f_i \times g_{n-i} \times \binom{n-1}{i-1} \times K^{i(n-i)}$。

把所有部分的答案乘起来就好了。时间复杂度 $O(n^3)$，期望得分 $100$ 分。

当然最重要的是要判对无解的情况，大致有四种，分别是 $d_{i,j} >K$，$d_{i,i} \neq 0$，$d_{i,j} \neq d_{j,i}$，$d_{i,j} > d_{i,k}+d_{k,j}$，大力 check 一下就可以了。

题目难度提升

from jiry_2，数据 from cy

这道题还是挺简单的，本来是出给 hiho 的 A 题，后来感觉有点难了（其实是最开始想简单了）就出 UR 了，感觉主要难度在于细节稍微多了点。

算法一

按位枚举，判断合法性只需要把后面所有的数升序排序然后检查一下就可以了。

直接裸写时间复杂度 $O(n^4)$ 已经够了，期望得分 $20$ 分。

算法二

考虑没有相同的数的情况。那么这个时候假设中位数是 $m$，新加入的数是 $a$。如果 $a < m$，那么中位数减少；如果 $a > m$，那么中位数增大；否则中位数不变。

按位枚举，一个前缀有解当且仅当前缀的中位数 $m$ 小于等于所有还没有放的数。

最开始先放最小的数，每一阶段放两个数进去。阶段开始时因为有奇数个数，所以中位数一定落在某个数上。

假设开始时中位数是 $m$，大于 $m$ 的第一个还没有放的数是 $K$，如果 $(m,K)$ 中已经有数放了，那么这个数不管放什么都可以，直接放最大的数就可以了。否则新放入的数 $a$ 一定要满足 $a+m \leq 2K$，即 $a \leq 2K-m$，令 $R=2K-m$。如果 $(m,R]$ 中已经有数放了，直接放最大的数就可以了，否则找到 $(m,R]$ 中最大的数放进去即可。

假设此时中位数是 $M$，大于等于 $M$ 的第一个还没有放的数是 $L$，如果 $(m,L)$ 中已经有数放了，那么直接放最大的数，否则就只能放 $L$ 了。

可通过第 4 个子任务，结合算法一可获得 $50$ 分。

算法三

有相同的数其实也不难。令所有数的中位数是 $m$，如果小于等于中位数的数中没有重复出现的数字，那么算法一仍然适用，否则令 $R$ 为第一个小于等于 $m$ 的重复出现的数字。

那最开始两个数最大字典序的情况一定是两个 $R$。因为如果更大的话中位数就没机会落在重复数上了，这时就满足算法一的性质，然而最大的数还没有放，所以无解。

放了两个 $R$ 后接下来就可以贪心了，每次放一个最大的数和一个小于等于 $R$ 最大的数，这个时候中位数在两个 $R$ 中左右横跳，一直没有变化，直到小于等于 $R$ 的数都用完了。这时就回到了算法一的情况，接着用算法一就可以了。

如果暴力实现的时间复杂度 $O(n^2)$，期望得分 $40$ 分。

可以发现所有的操作都是可以用 set 方便的做到。时间复杂度 $O(n \log n)$，期望得分 $100$ 分。

后半部分直接按位枚举也是可以的，稍微优化一下可以做到 $O(n \log^2 n)$ 或者 $O(n \log n)$，细节会稍微少一点。因为要降难度，所以也没去卡 $O(n log^2 n)$ 的做法，感觉还是比较良心的。