题解：P17665 [IO 2025 #3] LOIS

111122a · 2026-10-22 15:31:01 · 题解

题目传送门

我们可以发现，当数组中存在不相等的元素时，交换一下即可；当数组中有 0 时，末尾补一个 0 即可。接下来再讨论元素全部相同的情况：

1. 当所有元素为 1 时，显然无解。
2. 当有两个及以上的 2 时，可以把两个 2 变为一个 4(前提是 k \geq 4)。
3. 当所有数为质数时，显然无解。
4. 当所有数为合数时，只需要将一个元素 x 拆分成 a \cdot b 的形式，再在序列末尾补上 x - a -b 个 1 把序列的和补齐即可。

证明非常简单，这里就不过多赘述了，直接看代码：

code

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i!=1 && a[i]!=a[i-1])f=0;//标记是否全部相等 
        t[a[i]]++; 
    }
    if(t[0]){
        cout<<n+1<<'\n';
        for(int i=1;i<=n;i++)cout<<a[i]<<' ';
        cout<<0;
        return ;
    }
    if(f){
        if(a[1]==1){
            cout<<"-1\n";
            return ;
        }
        if(a[1]==2){
            if(n<2){
                cout<<"-1\n";
                return ;
            }
            if(k<4){
                cout<<"-1\n";
                return ;
            }
            cout<<n-1<<'\n';
            for(int i=1;i<n-1;i++)cout<<"2 ";
            cout<<4;
            return ;
        }
        int x=-1,y=-1;
        for(int i=2;i*i<=a[1];i++){
            if(a[1]%i==0){
                x=i;y=a[1]/i;
                break;
            }
        }
        if(x==-1){
            cout<<"-1\n";
            return ;
        }
        cout<<n+1+a[n]-x-y<<'\n';
        for(int i=1;i<n;i++)cout<<a[i]<<' ';
        cout<<x<<' '<<y<<' ';
        for(int i=1;i<=a[n]-x-y;i++)cout<<"1 ";
        return ;
    }
    for(int i=1;i<n;i++){
        if(a[i]!=a[i+1]){
            swap(a[i],a[i+1]);
            break;
        }
    }
    cout<<n<<'\n';
    for(int i=1;i<=n;i++)cout<<a[i]<<' ';
}