题解：B4225 [常州市程序设计小能手 2024] 黑板

Ag2WO4 · 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);
    }
}