20231102 C

_Cyan_ · 2023-11-02 21:05:26 · 个人记录

说真的，做构造题感觉真的随缘

题意首先可以转化为两个 1 \sim n 的排列，选择一半作为加的部分和为 A，另一半为减得部分和为 B，使每个距离不同且和为 \frac{(n-1)n}{2}。

则可得以下等式：

则可得 A=\frac{3n^2+3n}{4}， B=\frac{n^2+n}{4}。

那么这个时候就可以判无解的情况了，那就是 n \mod 4 \ge2

接着我们先考虑 n \mod 4 =0 的情况。

然后就是一个很妙的想法，我们假设前 \frac{n}{2} 个数都是加，后面的都是减，那前面的和就应该等于 A-sum(\frac{n}{2}+1,n)= \frac{3n^2+4n}{8}，而如果我前面填 [\frac{n}{2}+1,n] 的数，本来该有 \frac{3n^2+2n}{8}，所以多出来了一个 \frac{n}{4}，所以我们考虑删掉一个值再加一个更小的值，于是我们把 \frac{n}{2}+1 替换成 \frac{n}{4}+1。

那么这个时候前面的数是 [\frac{n}{2}+2,n] 和 \frac{n}{4}+1，后面的数就是 [1,\frac{n}{4}] 和 [\frac{n}{4}+2,\frac{n}{2}+1]。

现在我们知道了前面和后面分别有哪些数，于是我们开始满足绝对值互不相同这个条件。

有一个下意识的想法，那就是把数倒序填上去，我们先考虑右边，也就是后面的情况，那 [\frac{n}{4}+2,\frac{n}{2}+1] 这一段的值就是 0,2,4,......,\frac{n}{2}-2，[1,\frac{n}{4}]的值就是 \frac{n}{2}+1,\frac{n}{2}+3,...,n-1。

接着考虑左边，首先我们发现 n 不能放在第一个，所以从 n-1 开始，然后经过手模几组数据，我们发现把 \frac{n}{4} +1 放在 \frac{n}{4} 的位置刚好满足！然后再把 n 放在 \frac{n}{2} 的位置，我们有惊奇的发现刚好满足！

于是就解决了 n \mod 4 =0 的情况

然后 n \mod 4 =1 的情况，我们先把 n 放在第一个，接着大致思路没什么区别，只是要单独填的位置成了 1。