CF1793B Fedya and Array 题解

ivyjiao · 2023-02-13 17:45:32 · 题解

本题构造方法：我们令 a_1=a,a_m=b,a_n=a-1，此时 n=(a-b+1)+((a-1)-(b+1))+1，去括号得 n=2a-2b。

证明：我们先令 a_1=a,a_2=a-1\dots a_m=b，能保证这样是最省的，由于对于任意的 i 都要满足 |a_i-a_{(i-1+n)\bmod n}|=|a_i-a_{(i+1+n)\bmod n}|=1，所以我们还要继续往上构造 a_{m+1}=b+1,a_{m+2}=b+2\dots a_n=a-1，那么就构造完了，这样也是最省的。

#include<iostream>
#include<algorithm>
using namespace std;
long long t,a,b;
int main(){
    cin>>t;
    while(t--){
        cin>>a>>b;
        cout<<2*a-2*b<<endl;
        for(int i=a;i>=b;i--) cout<<i<<" ";
        for(int i=b+1;i<a;i++) cout<<i<<" ";
        cout<<endl;
    }
}