数据结构 2021 小作业6 Hint

[Sakits]

数据结构 2021 小作业6 Hint

  这周的小作业好像难度开始变大了，最后一题是省选联考的压轴题，大概能在考场上切掉这个题的应该也不会出现在交大了。希望 ppca 的时候助教哥哥姐姐们下手轻点...

1173. 一道排序题

  最大是 a 正序，b正序的时候。

  最小是 a 正序，b逆序的时候。

  证明可以用各种不等式，或者考虑这么一个简单的证明：

  设 $a, b, c, d > 0$
$$
a * b + (a + c) * (b + d) - [a * (b + d) + b * (a + c)] = c * d > 0
$$
  也就是说对于 $[a, a + c]$ 和 $[b, b + d]$ 这两个序列，$a$ 跟 $b$ 匹配，$a + c$ 跟 $b + d$ 匹配一定比 $a$ 跟 $b + d$ 匹配，$a + c$ 跟 $b$ 匹配得出的值更大。

1174. 两道排序题

  二分一下答案，就知道哪些块会被淹没，根据这个算出实际的高度，如果比二分的答案小就缩小 mid，否则增大 mid。

1175. 三道排序题

  排序之后模拟。

1176. 信息传递

  对于每个点都有且仅有一个出度的图，就是一棵基环树，又叫环套树，就是一个环上挂了很多棵树。

  这题相当于要求环的大小，dfs 一遍就好了。

1179. 四道排序题

  这题似乎有很多做法。

  正解是每次更新答案之后使用冒泡排序，由于每次只会给一个有序数组的每个数最多增加 2，所以冒泡排序也是 $O(n)$ 的复杂度。

  其他的做法比如每次排序前把所有数 $x$ 以及 $x + 1$, $x + 2$ 都找出来离散化之后就可以桶排了，这样排序复杂度也是 $O(n)$ 的。

  或者直接用 $O(n)$ 排序的科技，可见 loj2286 WC2017 挑战。

1177. 火柴排队

  $(a_i - b_i)^2 = a_i^2 + b_i^2 - 2a_ib_i$，由于 $\sum a_i^2 + b_i^2$ 是固定的，所以只要考虑 $-2a_ib_i$，可以发现这就是 1173 那题，得到结论只要两个序列对应升序就是最优的匹配方案。

  那么如果把两个序列离散化之后（离散化是指把一个序列的每个数映射为该数在该序列中的排名，如 114 514 1919 810 离散化之后就是 1 2 4 3，离散化用一个排序就可以做到），我们要做的就是通过最少的交换次数使得这两个序列完全一致。

  如果目标是这个的话，那么交换其中一个序列的数等价于交换两个序列的数，因为交换第一个序列的两个数跟交换第二个序列对应的两个数是完全等价的。

  对于两个离散化之后的序列 ${a_i}, {b_j}$，考虑求一个${c_i}$，表示 $b_i$ 这个数在 ${a_j}$ 中的位置，那要把 ${b_i}$ 通过交换变成 ${a_j}$ 的问题就等价于把${c_i}$排序。

  每次只能交换相邻的两个数，要把一个序列排序的最少次数就是逆序对数，因为每次交换相邻的两个数最多只会使得逆序对数 -1，而对于一个未排序的序列，每次一定能够找到一对相邻的逆序的数，交换它们使得逆序对数 -1。

1178. 排水系统

  直接模拟即可。

  注意分母可能会爆 long long，所以可以用 __int128 或者手动用两个 long long 写一个 __int128 出来，可能用 long double 精度也够。

1180. 序列合并

  对于 $a_i$ 里的任意一个数，一定是按从小到大顺序取得 $b_j$ 中的数，维护一下 $a_i$ 里每个数取到了哪个位置，用堆维护所有 $a_i$ 加上对应 $b_j$ 中的数，每次弹出来的时候塞 $a_i$ 加下一个位置的 $b_j$ 进去。

1181. 丁香之路

  用一条链上多了一堆额外的边来考虑这个问题会更简单。

  枚举终点 $i$，问题相当于求一条从 $s$ 到 $i$ 的欧拉路径，存在这条路径的条件是路径上除了 $s$ 和 $i$ 是奇度数点之外，其他点都是偶度数点。如果加上一条 $i$ 到 $s$ 的边，相当于求一条从 $s$ 出发的欧拉回路，存在欧拉回路的条件是回路里每个点的度数都为偶数。

  所以考虑所有必经边加上 $i$ 到 $s$ 的边构成的图，首先要确保这个图有欧拉回路，我们要做的就是在奇度数点之间连边，使得每个点的度数都为偶数，这个显然把所有奇度数点排序之后让 $p_{i * 2 - 1}$ 和 $p_{i * 2}$ 连边就是最短的。

  但是仅仅是这样可能导致这个欧拉回路并不连通，为了让这个图尽可能连通，上面提到的奇度数点 $i$ 和 $j$ 连边应该拆成 $(i, i + 1), (i + 1, i + 2), ..., (j -1, j)$ 的连边方案，在代价不变的情况下更有可能让所有的点连通起来，连通性用并查集维护即可。除此之外，各个连通块之间还需要连接起来，比较暴力的做法是把存在欧拉回路中的点两两的边找出来做最小生成树，但是这样复杂度就变成 $O(n ^ 3\log n)$了。考虑跟奇数点间连边类似的一个性质，想让这些连通块连通，只要把欧拉回路里的点排序之后编号相邻的两个点的连边就好了，这样的边数就减少到 $O(n)$ 了。总复杂度 $O((m + n^2)\log n)$。