题解 P7510 【铃解缀】

· · 题解

小学数学经典题。小学曾在多个 MO 课听过做法。可是赛时由于设备原因写代码太麻烦了不想写，否则应该可以首 A（

首先，我们发现 a-b 与 a+b 奇偶性相同，即 \sum\limits_{i=1}^{n}(a_i-b_i) \equiv \sum\limits_{i=1}^{n}(a_i+b_i) \pmod{2}。

上式左边是 \dfrac{n(n+1)}{2}，右边是 \dfrac{2n(2n+1)}{2}。推一推发现需要 n \equiv 0,1 \pmod{4}。

然后感觉这个问题不是很好处理，联想到有解条件是 n \equiv 0,1 \pmod{4}，并且差取遍 1 \sim n，想到小学时很喜欢的一个问题：

把 1 至 n 各两个排成一列，使两个 i 之间隔 i 个数。

当时脑抽以为这个问题有解条件也是 n \equiv 0,1 \pmod{4}，推了下小情况发现是 n \equiv 0,-1 \pmod{4}（

但是发现如果把 i 变成 i+1 再加两个相邻的 1，正好变成两个 i 的下标差 i，并且有解条件是 n \equiv 0,1 \pmod{4}。于是我就做出来了？

回忆了一下以前讲的构造，记得我特别喜欢它的原因是除了几个数外都是两个 x+2 套着两个 x 的形式。搞了一下搞出来了。

然后发现我的构造和 std 一模一样。。。大概就是这题引申过来的吧（

Code:

#include<cstdio>
#define rg register
int n;
int ans[2][1000003];
int main()
{
    scanf(" %d",&n);
    if(n&2)return 0&puts("-1 0");
    int m=n>>2;
    if(n&1)
    {
        ans[0][1]=1,ans[1][1]=2;
        ans[0][n]=n,ans[1][n]=n<<1;
        ans[0][n-2]=m+2,ans[1][n-2]=n+m;
        ans[0][n>>1]=n+(n>>1),ans[1][n>>1]=m<<3|1;
        ans[0][n-1]=(m+1)<<1,ans[1][n-1]=n+(m<<1|1);
        for(rg int i=1;i<m;++i)
        {
            ans[0][n-((i+1)<<1)]=2+i,ans[1][n-((i+1)<<1)]=n-i;
            ans[0][i<<1]=((m+1)<<1)-i,ans[1][i<<1]=((m+1)<<1)+i;
            ans[0][n-(i<<1|1)]=n+i,ans[1][n-(i<<1|1)]=(m<<3|1)-i;
            ans[0][i<<1|1]=n+(m<<1)-i,ans[1][i<<1|1]=n+(m<<1|1)+i;
        }
    }
    else
    {
        ans[0][1]=1,ans[1][1]=2;
        ans[0][n-1]=m+2,ans[1][n-1]=n+m+1;
        ans[0][n>>1]=n|1,ans[1][n>>1]=n+(m<<1|1);
        ans[0][n]=(m+1)<<1,ans[1][n]=n+((m+1)<<1);
        for(rg int i=1;i<m;++i)
        {
            ans[0][n-(i<<1|1)]=2+i,ans[1][n-(i<<1|1)]=n-i+1;
            ans[0][n-(i<<1)]=n+i+1,ans[1][n-(i<<1)]=(n<<1|1)-i;
            ans[0][i<<1]=((m+1)<<1)-i,ans[1][i<<1]=((m+1)<<1)+i;
            ans[0][i<<1|1]=n+(m<<1|1)-i,ans[1][i<<1|1]=n+((m+1)<<1)+i;
        }
    }
    for(rg int i=1;i<=n;++i)printf("%d %d\n",ans[1][i],ans[0][i]);
    return 0;
}