CF1793B Fedya and Array 题解

· · 题解

下文中我将称 local maximum 为邻域最大数， local minimum 为邻域最小数，很显然邻域最大数大于他两侧的数，邻域最小数小于他两侧的；称 a_{i+1}=a_i+1 为一次上升， a_{i+1}=a_i-1 为一次下降 。

我们来考虑这个数列的结构，不难发现：数列中邻域最大数和邻域最小数交替出现。

证明如下：对于一个邻域最大数 a_i ，他右侧的数 a_{i+1} 一定小于它，如果 a_{i+2}>a_{i+1} 则 a_{i+1} 为一个邻域最小数，否则 a_i,a_{i+1},a_{i+2} 一直下降，重复此过程即可。由于相邻两数的差的绝对值等于 1 ，所以在重复考虑到 a_i 之前，必然会出现一次 a_{j+1}>a_j ，所以必然会出现一个邻域最小数。其他情况可以同理证明。

另一种理解方式是将数列图像化，它就是一条波动的折线，波峰和波谷是交替出现的。

根据我们上面的证明，发现，一个领域最大数和领域最小数之间的数是不断上升或者下降的，假设其中某两个相邻的邻域最大数和最小数分别为 x_i 和 y_i ，他们两个以及期间的数会出现形如 x_i,x_i-1\dots y_i+1,y_i 或者 x_i,x_i+1\dots y_i-1,y_i 的结构，在这种情况下，领域最大数和邻域最小数的差是等于这两个数下标的差的（出现关于 n 和 1 的衔接问题是可额外加或者减一个 n ）。

由于数列中邻域最大数和邻域最小数交替出现，可以进行一一对应，如果，也就意味着，所有领域最大数的和减去所有领域最小数的和，也就是 x-y ，等于数列中上升或者下降的次数。

由于序列是环状的，所以上升次数和下降次数应该是相等的才能符合要求。

于是假设序列长度为 n ，我们就可以知道 n=2(x-y) 。所以说只有这种情况下的 n 可能合法，现在我们只需考虑构造。最简单的构造就是出现一个邻域最大数为 x 和一个领域最小数为 y ，中间一直上升或者下降即可。

#include <bits/stdc++.h>
using namespace std;
int Qread()
{
    int x=0;bool f=false;char ch=getchar();
    while(ch<'0'||ch>'9') f|=('-'==ch),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x; 
}
long long x,y;
long long dis;
long long ans;
void solve()
{
    x=Qread(),y=Qread();
    dis=x-y;
    printf("%lld\n",dis*2);
    for(int i=0;i<dis;i++) printf("%lld ",x-i);
    for(int i=0;i<dis;i++) printf("%lld ",y+i);
    printf("\n");
    return;
}
int T;
int main()
{
    T=Qread();
    while(T--) solve();
    return 0;
}