CF1793B题解

Nuyoah_awa · 2023-02-18 18:16:10 · 题解

题目分析

本题是一个简单数学构造题。

首先题目让构造出一个环，使得所有相邻元素差为 1 并且所有值比左右两个相邻值大的数之和为 x，所有值比左右两个相邻值小的数之和为 y。

以样例一的第一组数据（x = 3, y = -2）为例，根据 x，环大致可以分成这两种情况（根据 y 的分类同理）。

我们以上图为例，我们只看局部最大值，如果最大值是 3，可以看成 x 从 0 开始，最后回到 0。我们分成了两种情况，由一个局部最大值 3 构成：从 0 \sim 3 最少 3 个数，从 3 \sim 0 同理；第二种由一个局部最大值 2 和一个局部最大值 1，我们不难发现，通过平移后，我们都可以看成是 0 \sim 2 \sim 0 和 0 \sim 1 \sim 0 两段拼接而成。

由此，我们可以推断出：对于任意 x 可分解为： x = x_1 + x_2 + …… + x_n。若以第一种分类，ans = x \times 2；若以第二种分类，ans = \sum ^{i\leq n}_{i=1}x_{i} \times 2。很明显，前后两式的结果是一样的（对于 y 的同理）。

综上，这两种方法所需要的元素个数是一样的（也最少的）。于是就可以输出最好输出的第一种，即输出从 0 \sim x,x \sim y,y \sim 0。

code

#include <iostream>
#include <cstdio>
using namespace std;
long long x, y, T;
int main()
{
    cin >> T;
    while(T--)
    {
        cin >> x >> y;
        cout << (x - y) * 2 << endl;
        for(int i = 0;i < x - y;i++)
            cout << x - i << " ";
        for(int i = 0;i < x - y;i++)
            cout << y + i << " ";
        cout << endl;
    }
    return 0;
}