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; }
构造专题
笔记