题解：CF2031C Penchick and BBQ Buns

· · 题解

偶数情况很简单，两个两个放就可以了，重点是奇数情况。

首先，如果要放奇数个，一定有至少一个数出现了奇数次。

其次，如果这个数出现了超过三次，因为放三个的约束条件小于放更多个，所以可以把多出来的那些给换成别的成对的数。

那么情况就转化成了如何放下三个同一个数。一旦放下同一个数三次，后面的就可以直接按照偶数的方法无脑放，所以考虑如何在最短的长度内放满 3 个同样的数。

设这个数三次分别出现在位置 p,p+X,p+X+Y，根据题目要求，X 和 Y 是平方数，且 (X+Y) 也是平方数，所以设 x^2=X,y^2=Y,z^2=X+Y，那么有 x^2+y^2=z^2。

这一段的长度为 z^2+1，而使其最小的 z=5，对应的 x=3,y=4，所以思考如何向下面的数列中填数：

1 _ _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1

前一半有 8 个空，按照偶数方法填入；后一半有 15 个空，偶数方法填不完，但是剩下的一个可以考虑组合成距离 4：

1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 12 11 11 1 12

这样，只用 27 个数就可以放入三个相同的数，后面按照偶数方法加即可得到任意奇数，前面的无解（26 已经是放三个的理论最小长度）。

然后就做出来了：

int main()
{
    int T; read(T);
    while(T--)
    {
        int n; read(n);
        if(n&1)
        {
            if(n<27) puts("-1");
            else
            {
                printf("1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 12 11 11 1 12 ");
                for(int i=1;i<=(n-27)>>1;i++)
                    write(i+14,' '),write(i+14,' ');
                putchar('\n');
            }
        }
        else
        {
            for(int i=1;i<=n>>1;i++)
                write(i,' '),write(i,' ');
            putchar('\n');
        }
    }
    return 0;
}