Balanced Neighbors 2

· · 题解

首先考虑有什么元素，自然的，有边，有 S_i 表示距离 i 不超过 2 的点集。

边有很多性质，不好处理，可以考虑的是，一条边 (u,v) 可以使得 u 可以花费两条边的代价到达 v 通过一条边到达的点，同时 v 需要一条边到达的点 u 无法如此到达（先不考虑三元环）。

考虑 S_i，不妨让 S_i=T_{i,1}\cup T_{i,2}，显然的 T_{i,2} 更加复杂，我们考虑先处理它。

不妨将 T_{i,2} 的关键元素这么刻画：x\to y\to z，则我们发现，T_{i,2} 相当于找到一个中转点 y，让两个距离 y 为 1 的点之间产生贡献。

比较自然的，我们将 y 与 x 和 z 的边当作划分，此时我们发现，这个划分是双向的。

这个时候我们就要考虑构造了，我们需要让 (\sum_{x\in S_i} x)=k，由于 S_i 是不包括 i 号点的，而包括的点没什么限制，从特殊点入手，我们考虑继续构造一个点不被包括，而这个点需要满足 i+z=p，如果一个点被多次对应，由于对应是双向的，规模被扩大，不好，所以我们考虑建立一一对应，这个时候我们就要考虑 n 是奇数了，不过我们先不管。

假设 n 是偶数，由于是一一对应，而 z=p-i，此时我们发现，如果我们记一次变换 f(x)=p-x，则 f(f(x))=f(p-x)=p-(p-x)=x 也就是说，对应过去的数一定会被唯一的对应回来，无需考虑如何使得对应唯一。

那么我们只要让 f(x) 在定义域下的值域在 [1,n] 即可，不难发现 p=n+1 满足条件。

接着考虑 n 是奇数，如果按照我们那么对应，一定会剩余一个数，三个选择，剩余 \frac{n+1}{2}，剩余 1，剩余 n，带入一下，求一下 k，你会发现如果剩余 n 那么只要让别的点都在 S_n 中即可。

至于如何排斥掉一个点，假设这个对应关系是 (x,z)，则我们只需要保证不存在 y 使得同时存在 (x,y) 和 (z,y)，图论建模不容易处理这个限制，同时建出来也会规模过大了（当然可以取消那些没什么必要的点）。

我们考虑 T_{i,1} 和 T_{i,2} 的关系，我们当然希望他们之间交集为空集（没有三元环），所以我们就可以将需要到达的 n-2 个点平均分为两组（此时两个集合没有本质区别），自然的，i 和 n-i+1 是在不同的组。（保证问题数量尽可能小）

于是构造即可。