自动搬运

查看原文

来自洛谷，原作者为

	Ag2WO4 Ag2WO4是钨酸银的意思哦～

搬运于2025-08-24 21:17:58，当前版本为作者最后更新于2025-03-08 01:41:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很有意思也很麻烦的一道构造题。

为方便讨论，将起始值 $a$ 从 $b$ 和 $x$ 中扣除，得到一个 $0\sim b$ 的序列。显然当 $x=0$ 或 $x=b$ 极端值时由于一定存在极端值以内的值，无法达到。

注意到以下构造方法：

• $0+2\rightarrow1$
• $1+1\rightarrow1$
• $1+3\rightarrow2$
• $2+4\rightarrow3$
• $...$
• $x+(x+2)\rightarrow(x+1)$

同理可以从大到小构建生成的数字不断减少的方法。它可以消除一串数，得到的结果和未消除的串相隔一个空位。接下来分类讨论：

• 当 $x=1$ 或 $x=b-1$ 时，直接消到底即可；
• 当 $x=2$ 或 $x=b-2$ 时，由于不能直接消到底，需要将垫在后面的极端值消去从而转化为上一种情况，分类讨论：
  • 如果 $b$ 是偶数，消除两端再将产物自消即可；
  • 如果 $b$ 是奇数，对于 $x=2$ 的情况会消除 $0$ 和 $b-1$ 这两个数，生成 $\frac{b-1}2$ 这个数，此时可以直接消除直到用掉既有的 $\frac{b-1}2$ 同时有一个 $\frac{b+1}2$ 生成，依然能得到上一种情况；以上讨论对 $x=b-2$ 同理。
• 除此以外的情况可以两端消除直到只剩下 $x-2,x,x+2$ 三个数，再消除两次即可。

因此我们可以得到复杂度为 $O(b-a)$ 的构造方法。注意题目中的“小号储存平均值，大号消失”的规则，需要小心变换数和位置的关系，这里的方法请你自行构建，盯着他人的思路容易互相绕晕。

Python 代码

a,b,x=map(int,input().split());x-=a;b-=a
if(b-x)*x:
    if x==1:
        print(b-2,b)
        for a in range(b-1):print(b-2-a,b-1-a)
    elif x==b-1:
        print(0,2);print(0,1)
        for a in range(b-2):print(0,a+3)
    elif x==2:
        print(0,b-b%2);print(b-3+b%2,b-1+b%2)
        for a in range(b-b//2-1):print(b-3-a,b-2-a)
        print(0,b//2-1)
        for a in range(b//2-2):print(0,b//2-2-a)
    elif x==b-2:
        print(b%2,b);print(1-b%2,3-b%2);print(1-b%2,2+b%2)
        for a in range(b-b//2-2):print(1-b%2,a+4)
        print(0,1)
        for a in range(b//2-2):print(0,b//2+b%2+2+a)
    else:
        print(0,2);print(0,1);print(b-2,b)
        for a in range(x-3):print(0,a+3)
        for a in range(b-x-2):print(b-2-a,b-1-a)
        print(0,x+1);print(0,x)
else:print(-1)

C/C++ 代码

#include<stdio.h>
int a,b,x;
int main()
{
    scanf("%d%d%d",&a,&b,&x);
    b-=a;
    x-=a;
    if((b-x)*x)
    {
        if(x==1)
        {
            printf("%d %d\n",b-2,b);
            for(a=0;a<b-1;++a)
            {
                printf("%d %d\n",b-2-a,b-1-a);
            }
        }
        else if(x==b-1)
        {
            printf("%d %d\n",0,2);
            printf("%d %d\n",0,1);
            for(a=0;a<b-2;++a)
            {
                printf("%d %d\n",0,a+3);
            }
        }
        else if(x==2)
        {
            printf("%d %d\n",0,b-b%2);
            printf("%d %d\n",b-3+b%2,b-1+b%2);
            for(a=0;a<b-b/2-1;++a)
            {
                printf("%d %d\n",b-3-a,b-2-a);
            }
            printf("%d %d\n",0,b/2-1);
            for(a=0;a<b/2-2;++a)
            {
                printf("%d %d\n",0,b/2-2-a);
            }
        }
        else if(x==b-2)
        {
            printf("%d %d\n",b%2,b);
            printf("%d %d\n",1-b%2,3-b%2);
            printf("%d %d\n",1-b%2,2+b%2);
            for(a=0;a<b-b/2-2;++a)
            {
                printf("%d %d\n",1-b%2,a+4);
            }
            printf("%d %d\n",0,1);
            for(a=0;a<b/2-2;++a)
            {
                printf("%d %d\n",0,b/2+b%2+2+a);
            }
        }
        else
        {
            printf("%d %d\n",0,2);
            printf("%d %d\n",0,1);
            printf("%d %d\n",b-2,b);
            for(a=0;a<x-3;++a)
            {
                printf("%d %d\n",0,a+3);
            }
            for(a=0;a<b-x-2;++a)
            {
                printf("%d %d\n",b-2-a,b-1-a);
            }
            printf("%d %d\n",0,x+1);
            printf("%d %d\n",0,x);
        }
    }
    else
    {
        putchar(45);
        putchar(49);
    }
}