刚刚结束的比赛 E 题部分分求条，悬 2 关

rt, 赛时打的是 1\le c\le 4\times 10^6 的部分分，然后爆零了。

我的构造方法是让 a_1=0,a_2=1，然后 a_i(i>2)=a_{i-1} 或 a_i(i>1)=a_{i-1}+1，容易发现这时 \text{mex} 的区间和就是 \sum (a_i+1)，具体就是先找到这个序列的最短长度 k，然后直接在 0,1,2\ldots k-3,k-2 里面插入一个数就构造好了，但是必须 a_2\ne 0，所以改成 0,1,1,2,3\ldots k-5,k-4,k-3,k-3 即可。

拍没拍出来 /kk

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,k,c;
signed main(){
    cin>>T;
    while(T--){
        cin>>n;
        if(!n){//特判
            cout<<"1\n1\n";
            continue;
        }
        if(n==1){
            cout<<"1\n0\n";
            continue;
        }
        if(n==2){
            cout<<"2\n0 2";
            continue;
        }
        if(n==4){
            cout<<"4\n0 2 2 2\n";
            continue;
        }
        int k=(int)sqrt(n*2);//找最短长度，这里写的有点抽象，勿喷 QwQ
        if((k-2)*(k-1)>=2*n)k=k-2;
        else if((k-1)*k>=2*n)k=k-1;
        else if(k*(k+1)>=2*n)k=k;
        else if((k+1)*(k+2)>=2*n)k=k+1;
        else if((k+2)*(k+3)>=2*n)k=k+2;
        n-=(k-1)*k/2;c=-1;//先有 0,1,2...k-2 然后插一个数进去
        if(n==1){//特判 a2=0，这时对序列进行微小调整
            cout<<k<<"\n";
            cout<<"0 1 1 ";
            for(int i=4;i<k;i++){
                cout<<i-2<<" ";
            }cout<<k-3<<"\n";
            continue;
        }
        cout<<k<<"\n";
        for(int i=1;i<=k;i++){
            if(c==n-1){
                cout<<c<<" ";
                n=-1;
            }
            else cout<<++c<<" ";
        }cout<<"\n";
    }
}