date: 2020-07-18 12:00~17:00

2020牛客暑期多校训练营（第三场）

题目大意：

题解：

题目大意：

题解：

题目大意：给你一个“手掌”的图形，可能会被平移和旋转，给的点会按正序或者逆序给出，问你所给的点组成了右手还是左手。

题解：

手掌最底部长度是 9，唯一的 9，找一下。大拇指和小拇指就是相邻的，长度不一样，判一下位置，作为条件 1；大拇指的向量与手掌底部的向量叉积，符号作为条件 2；两个条件异或一下，答案。

题目大意：给偶数个 $a_i$，需要进行配对，记第 $i$ 个元素与第 $p_i$ 个配对，称 $\{p_i\}$ 为配对方案。配对后记配对的代价为配对的两个元素的绝对差的总和。现在要你求出两个不同的配对方案，对每个 $i$ 要满足 $p_i \ne p'_i$，使得两个配对方案的代价和最小。

题解：DP

首先，我们肯定会先考虑给 $a_i$ 排一下序，不会影响到配对。假设我们已经有最优的两个配对方案了，我们把配对关系看成边，两个配对方案放在一张图上，那么就会出现若干个连通块。连通块内边数和点数一样，且度数均为 2，所以是个环。环上的边是方案 A、方案 B、……交替着出现的。

考虑一下答案的物理意义，对于排序后相邻的两个元素 $a_i$ 和 $a_{i+1}$，他俩的绝对差的贡献。如果我们划一刀将 $a_1, \ldots, a_i$ 和 $a_{i+1}, \ldots, a_n$ 切分开，那么被切到的边的数量，就是 $a_{i+1} - a_{i}$ 对答案的贡献。而被切到的边数也必然是偶数个。

那么对于确定的一个连通块，答案的下界显然就是最大值减最小值的差的两倍，且很容易能构造出来这个方案（按顺序连起来，然后最后最大和最小连一下），能够取到答案的下界。

接下来考虑将连通块内位置最大的 $4$ 个或 $6$ 个取出来，记这些元素为 A 组，剩下的元素记为 B 组。我们将 B 组中与 A 组相连的边随便接起来，答案显然不会变大。而 B 组又总有办法弄到只有这几个元素组成的答案的下界的方案。又由于只用 $4$ 和 $6$ 就能组合出所有可能的元素数量，因此取到最优的答案的前提下，连通块的大小总有办法限制为 $4$ 或 $6$ 个元素。

类似上面的证明，也可以证明一个连通块必然对应到了排序后序列的一段区间。

所以很简单，DP 一下，取当前末尾的 4 个或 6 个，转移一下就好。记得 dp[0] = 0, dp[2] = inf。

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：

题目大意：

题解：