题目：[[2024.9.26 题目]]。 ## 智乃的差分 对于数组 $a$ 而言，其差分 $d$ 数组 $d_i=\begin{cases}a_1&\text{if}~i=1\\a_i-a_{i-1}&\text{else}\end{cases}$。现让你重新排列 $a$ 数组，使 $a$ 的差分数组 $d$ 内没有整数 $x$。 --- 对于 $x>0$ 的情况，我们可以输出 $a$ 的降序来使 $d_i<0$；对于 $x<0$ 的情况，我们可以输出 $a$ 的升序来使 $d_i>0$；对于 $x=0$，我们可以随便造出一组相邻不相等、$a_1\ne 0$ 的情况。这三种构造方式只要有任意一种满足条件即可，不需要特殊判断 $x$。至于第一个数的特殊情况？可以赌出题人只会随机数据。 那么当 $x=0$ 时，我们又该如何构造出相邻两个数不相等的情形呢？首先使用 [[map]] 记录各个数出现了多少次，然后以出现次数的比较方式丢进优先队列里面，接着一直从优先队列里面取出出现次数最多但是与上一个数不相等的数，就可以构造出方案了。 如果以上三种方式都不能构造出正确答案的话，那么就只能输出无解了（其实我也不知道这种构造方式究竟能不能考虑到所有情况）。时间复杂度 $\mathcal O(\sum n\log_2 n)$。 ~~赛时变量名写错挂 10 分。~~ ## 牛牛的旅行 一景区有 $n$ 个景点，有 $n-1$ 条边连接两个景点，第 $i$ 个景点的优美程度为 $a_i$。对于两个不相邻的景区 $(u,v)$，定义 $f(u,v)$ 为路径上最大优美程度减去路径长度，求 $\sum\limits_{1\le i,j\le n,i\ne j}f(i,j)$。 --- 首先，我们可以将 $\sum f(i,j)$ 拆成 ${} \sum \max(i,j)-\sum dis(i,j) {}$。显然，$\sum dis(i,j)$ 很好求，对于每一个字数大小 $s$，答案类加上 $2\times s\times (n-s)$ 即可。但是 $\sum \max(i,j)$ 又该怎么求呢？ 我们可以采用类似联通块的思路。对于一个点 $i$，它的联通块内所有点 $j$ 均满足 $a_j\le a_i$，这代表着联通块内任意两个不同的子树之间的路径的最大权值都为 $i$。不难发现，对于 $i$ 的任意邻点 $j$，如果其在联通块内，那么答案需要累加上 $a_i\times s_i\times s_j$，其中 $s_i$ 表示为 $i$ 所在联通块的大小。 那么我们该如何保证权值大的联通块没有包含权值小的联通块呢？我们可以先对 $a$ 从小到大进行排序，这样子就可以使权值小的联通块先被计算，就不存在包含的问题了。时间复杂度 $\mathcal O(n\log n)$。 > [!question] 为什么我 T 了 > > 因为你没有用关同步流的 cin 读入。 ## 第 K 排列 没有看懂题目，输出 $-1$，得 $20$。 ## 牛牛的 border 使用最坏时间复杂度 $\mathcal O(n^4)$ 的暴力枚举，成功 $20$ 分。 ## 总结 - **排名**：$3$； - **比赛分数**：$150/400$；` - **情况**：相比与 [[2024.9.25 模拟赛]] 一般； - **问题**：变量名写错。