构造专题

P12572 [UOI 2023] An Array and Addition Again

只有数组末尾有一个 $1$ 局限性太大了，考虑先花 $99$ 次操作把整个数组填满 $1$。

之后直接往后面 DFS 即可，即减去当前位置的 $1$，除以 $2$，就是下一个位置需要达到的数，复杂度是两倍的 $log$，可以接受。

代码：

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

int T,g,n;
vector<int> ans;

void dfs(int id,int x){
    if(x<=1) return;
    if(!(x&1)) ans.push_back(id);
    dfs(id+1,(x-1)/2);
    if((x-1)/2) ans.push_back(id),ans.push_back(id);
}

void solve(){
    ans.clear();
    cin>>n;
    for(int i=99;i;i--) ans.push_back(i);
    dfs(1,n);
    cout<<ans.size()<<"\n";
    for(auto x:ans) cout<<x<<" ";
}

signed main(){
    cin>>T>>g;
    while(T--) solve();
    return 0;
}

P16357 [BalticOI 2026] Blocks

显然当 $n$ 为偶数时就是构造回文串，难点在 $n$ 为奇数的时候。

出现次数为偶数的颜色一律在左右两边对称放，为奇数的话就留下 $3$ 个。

记得要在中间放上一个落单的颜色（或者是从 $3$ 个的颜色里拆一个出来，剩下两个左右对称放）

考虑有解的情况就是剩下若干个出现次数为 $3$ 的颜色，观察到 通过列举小范围数据可以算出通项，具体看代码吧：

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

#define int long long
const int N=1e6+5;
int n,k,c[N],ct[N],ans[N];

void solve(){
    memset(ct,0,sizeof ct);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        ct[c[i]]++;
    }
    if(n%2==0){
        int ok=1;
        for(int i=1;i<=k;i++) if(ct[i]&1) ok=0;
        if(!ok){
            cout<<"NO\n";
            return;
        }
        cout<<"YES\n";
        int l=1,r=n;
        for(int i=1;i<=k;i++){
            while(ct[i]>0){
                ans[l++]=i;
                ans[r--]=i;
                ct[i]-=2;
            }
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
        return;
    }
    int c1=0;
    for(int i=1;i<=k;i++) if(ct[i]==1) c1++;
    if(c1>1){
        cout<<"NO\n";
        return;
    }
    int mc=-1;
    if(c1==1){
        for(int i=1;i<=k;i++) if(ct[i]==1){
            mc=i;
            break;
        }
    }
    else{
        for(int i=1;i<=k;i++) if(ct[i]&1){
            mc=i;
            break;
        }
    }
    ct[mc]--;
    vector<int> tp;
    for(int i=1;i<=k;i++) if(ct[i]&1){
        tp.push_back(i);
        ct[i]-=3;
    }
    int t=tp.size(),m=t/2,mid=(n+1)/2;
    for(int i=1;i<=n;i++) ans[i]=0;
    ans[mid]=mc;
    for(int j=1;j<=m;j++){
        int col=tp[j-1];
        ans[mid+j]=col;
        ans[mid+j+m]=col;
        ans[mid-(2*j+m)]=col;
    }
    for(int j=1;j<=m;j++){
        int col=tp[m+j-1];
        ans[mid+(2*m+j)]=col;
        ans[mid-(m-j+1)]=col;
        ans[mid-(m+2*j-1)]=col;
    }
    int l=1,r=n;
    for(int i=1;i<=k;i++){
        while(ct[i]>0){
            while(ans[l]) l++;
            while(ans[r]) r--;
            ans[l]=i;
            ans[r]=i;
            ct[i]-=2;
        }
    }
    cout<<"YES\n";
    for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}