资讯详情

P12025 [USACO25OPEN] Sequence Construction S

Ref：P12025 [USACO25OPEN] Sequence Construction S 题解 - Little_x_starTYJ

我们的构造要满足三个条件：

• \(1\le N\le 100\)
• \(\sum_i^N A_i=M\)
• \(\bigoplus_i^N \text{popcount}(i)=K\)

异或和的条件不是很好看，考虑先解决它。

考虑紧贴下界（最小化和）进行构造，只需依次取出 \(K\) 的每个 lowbit \(x\)，将 \(2^x-1\) 加入答案即可。

记此时的和还差 \(M'\) 到 \(M\)。

我们分类讨论一下：

• \(M'<0\)：最小化和的情况下仍不合法，所以无解。

• \(M'=0\)：已经合法。

• \(M'=1\)：

  • 若当前方案中存在 \(1\)，则将这个 \(1\) 变成 \(2\)。
  • 若当前方案中不存在 \(1\)，则无解。

• \(M'>1\) 且 \(M'\) 为偶数：补两个 \(\dfrac{M'}{2}\)。

• \(M'>1\) 且 \(M'\) 为奇数：先补 \(1,2\)，再补两个 \(\dfrac{M'}{2}\)。

这样构造序列长度的上界大概是 \(5+4=9\)。

点击查看代码

#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
int t,m,k;
vector<int> ans;
inline int lb(int x){return x&-x;}
inline void output(){cout<<ans.size()<<"\n";for(int i:ans) cout<<i<<" ";cout<<"\n";
}
signed main(){cin>>t;while(t--){ans.clear();cin>>m>>k;for(int i=k;i;i-=lb(i)){int t=(1<<lb(i))-1;ans.eb(t);m-=t;}if(m<0) cout<<"-1\n";else if(m==0){output();}else if(m==1){bool flg=0;for(int& i:ans) if(i==1){i=2,flg=1;break;}if(flg) output();else cout<<"-1\n";}else if(m&1){ans.eb(1),ans.eb(2);m-=3;if(m) ans.eb(m/2),ans.eb(m/2);output();}else{ans.eb(m/2),ans.eb(m/2);output();}}return 0;
}