转换构造题解

xu_zhihao · 2025-11-22 12:20:24 · 题解

题目是做梦梦到的。

先考虑什么情况下无解。

1. 当 n\le k 时。因为当需要操作 k 次时 a 长度至少为 k+1。
2. 当 k=1 时。因为假设 a 是符合构造条件，那么序列定形如 a_1,\pm a_1,\dots \pm a_1。因为 a_i \in \mathbb{N}_0，故 a_i=0。然而 a 不能有重复元素，故无解。
3. 当 k=0 且 n \neq 1。当 k=0,n=1 时显然有唯一合法构造 a_1=0。对于其他情况，由于a 不能有重复元素，故无解。

Subtask #1

大概就是留给选手一个暴力乱搞的部分分。

Subtask #2

输出 -1 即可。

Subtask #3

同样是先要判掉无解。

我想到的最简单的构造是令 a_i=i。

可以发现 a_i=g(i)，即构造合法。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int p,t;
    cin>>p>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        if(k>=n){
            cout<<"-1\n";
            continue;
        }
        for(int i=1;i<=n;i++){
            cout<<i<<" ";
        }
        cout<<"\n";
        for(int i=1;i<=n;i++){
            if(i==1)cout<<"1 3 -1 2\n";
            else if(i==2)cout<<"1 3 -1 1\n";
            else cout<<"1 1 1 "<<i-1<<"\n";
        }
    }
    return 0;
}

Subtask #4

这是我想到这档部分分最好写的构造方法。

容易联想到构造的序列和序列前缀和有关：

令 a_i=f(i)（1\le i \le n）。

对于 1\le i \le k，有合法方案 a_i=a_{k+1}-\sum_{j=1,j \neq i}^{k}a_j。

对于 k+1\le i \le n，有合法方案 a_i=a_{i-1}+\sum_{j=1}^{k-1}a_j。

显然，a_n=k+\frac{(n - k)k(k-1)}{2}，它在 n=1000,k=667 时有最大值 73963630 < 10^8。

故构造合法。

复杂度 O(nk)，瓶颈在于输出。可以通过此档部分分。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){

        int n,k;
        cin>>n>>k;
        if(n==1 && k==0){
            cout<<"0\n\n";
            continue;
        }
        if(k>=n || k<=1){
            cout<<"-1\n";
            continue;
        }
        for(int i=1;i<=k;i++){
            a[i]=i;
        }
        int pre_sum=k*(k-1)/2;
        for(int i=k+1;i<=n;i++){
            a[i]=pre_sum+a[i-1];
        }
        for(int i=1;i<=n;i++){
            cout<<a[i]<<" ";
        }
        cout<<"\n";
        for(int i=1;i<=k;i++){//前k个数 
            for(int j=1;j<=k;j++)if(i!=j){
                cout<<"-1 "<<j<<" ";
            }
            cout<<"1 "<<k+1<<"\n";
        }
        for(int i=k+1;i<=n;i++){
            for(int j=1;j<k;j++){
                cout<<"1 "<<j<<" ";
            }
            cout<<"1 "<<i-1<<"\n";
        }
    }
    return 0;
}

Subtask #5

构造方法有些劣，欢迎补充。

Subtask #4 可以得出一定的启发，然后就得到了下面的方法。

先不考虑 a_i<a_{i+1}，分块，块长为 k+1。对于每个整块，区间为 [l, r]，前 k 个元素依次记为当前最小的未被使用过的正整数。然后 a_r=\sum_{i=l}^{r-1}a_i。

若有余块^*，那么余块在的区间是 [n-n \mod (k+1)+1,n]。定义 sum=\sum_{i=n-n \mod (k+1)+1-k-1}^{n-n \mod (k+1)}a_i（即余块前的最后一个整块的元素和），然后 a_i=sum-a_{i-k-1}（i \in [n-n \mod (k+1)+1,n]）。 感性理解，这样构造的序列内所有的元素都不重复^{**}。

对于每个整块，区间为 [l, r]。前 k 个元素都有 a_i=a_r-\sum_{j=l, j\neq i}^{r-1} a_j，第 k+1 个元素有 a_r=\sum_{j=l}^{r-1} a_j。对于余块也有类似如此的情况符合题目要求^{***}。当 n=1000,k=998 时 a_n 有最大值 997001<10^6（卡的非常的死）。

故构造合法。

所以最后构造完之后把 a 和输出方案都按规则排序即可。

复杂度 O(nk)，常数略大。可以通过此档部分分。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e3+10;
int f[N];
int a[M];
int id[M][M],s[M][M];
int g[M];
int _g[M];
int cnt=1;
void init(){
    memset(f,0,sizeof(f));
    for(int i=1;i<M;i++)g[i]=i;
    memset(a,0,sizeof(a));
    f[0]=1;
    cnt=1;
    return;
}
int mex(){//返回mex 
    while(f[cnt])cnt++;
    f[cnt]=1;
    return cnt;
}
bool cmp(int A,int B){
    return a[A]<a[B];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int p,T;
    cin>>p>>T;
    while(T--){
        init();
        int n,k;
        cin>>n>>k;
        if(n<=k || k==1){
            cout<<"-1\n";
            continue;
        }
        if(k==0){
            if(n!=1)cout<<"-1\n";
            else cout<<"0\n";
            continue;
        }
        //构造整块 
        int t=n/(k+1);
        for(int i=1;i<=t;i++){
            for(int j=1;j<=k;j++){
                a[j+(i-1)*(k+1)]=mex();
                a[i*(k+1)]+=a[j+(i-1)*(k+1)];
            }
            f[a[i*(k+1)]]=1;
        }
        //构造余块
        int sum=0;
        for(int i=1;i<=k+1;i++){
            sum+=a[t*(k+1)-i+1];
        } 
        for(int i=t*(k+1)+1;i<=n;i++){
            a[i]=sum-a[i-k-1];
        }
        //处理整块 
        for(int i=1;i<=t;i++){
            for(int j=1;j<=k;j++){//当前到的位置 
                id[j+(i-1)*(k+1)][1]=i*(k+1);
                s[j+(i-1)*(k+1)][1]=1;
                int c=1;
                for(int x=1;x<=k;x++)if(x!=j){
                    c++;
                    id[j+(i-1)*(k+1)][c]=x+(i-1)*(k+1);
                    s[j+(i-1)*(k+1)][c]=-1;
                }
            }
            for(int j=1;j<=k;j++){
                id[i*(k+1)][j]=j+(i-1)*(k+1);
                s[i*(k+1)][j]=1;
            }
        }
        //处理余块
        for(int i=t*(k+1)+1;i<=n;i++){
            int c=1;
            for(int j=t*(k+1);j>=(t-1)*(k+1)+1;j--)if(j!=i-k-1){
                id[i][c]=j;
                s[i][c]=1;
                c++;
            }
        } 
        sort(g+1,g+n+1,cmp);
        for(int i=1;i<=n;i++){
            _g[g[i]]=i;
        }
        for(int i=1;i<=n;i++){
            cout<<a[g[i]]<<" ";
        }
        cout<<"\n";
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                cout<<s[g[i]][j]<<" "<<_g[id[g[i]][j]]<<" ";
            }
            cout<<"\n";
        }
    }
    return 0;
}