CF1793B题解

· · 题解

题意

定义一个长为 n 的序列 a 中 a_1 和 a_2,a_3 和 a_4,\dots,a_{n-1} 和 a_n,a_n 和 a_1 为相邻的。

定义局部最大值为与其相邻的元素都小于它的数，局部最小值为与其相邻的元素都大于它的数。

给出一个序列的局部最大值之和 x 和局部最小值之和 y，求一个最短的序列满足 x,y。

思路

设第 i 个局部最大值为 a_i，第 i 个局部最小值为 b_i，序列长度为 n。

为了让 b_i 接上 a_i，则需要 a_i-b_i 个数字。

\therefore n=(a_1-b_1)+(a_2-b_1)+(a_2-b_2)+\dots+(a_k-b_k)+(a_1-b_k)=2\times(a_1+a_2+\dots+a_k)-2\times(b_1+b_2+\dots+b_k)=2(x-y)

此时有一种显然的构造方法：x,x-1,x-2,\dots,y,y+1,y+2\dots,x-1。

代码：

#include <bits/stdc++.h>
using namespace std;
long long t, x, y;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) {
        cin >> x >> y;
        if(x > y)
            swap(x, y);
        cout << 2 * abs(x - y) << '\n' << x << ' ';
        for(long long i = x + 1; i < y; i++)
            cout << i << ' ';
        for(long long i = y; i > x; i--)
            cout << i << ' ';
        cout << '\n';
    }
    return 0;
}