题解：CF1957B A BIT of a Construction

原题链接

• 洛谷 CF1957B A BIT of a Construction

题意简述

构造长度为 $n$ 的数列 $a$（$a_i\ge 0$），满足 $\sum a_i=k$，且让数列 $a$ 按位或结果的二进制 $1$ 的个数最多。

解题思路

把第 $i$ 位变成 $1$ 的代价为 $2^i$，显然越低位代价越小，所以要让低位尽可能变成 $1$。

从低到高遍历第 $i$ 位，如果能变成 $1$，就让 $a_1$ 加上 $2^i$。

剩下 $k-a_1$ 没用了，不妨全都放到 $a_2$ 上，然后让其他 $a_i=0$（$3\le i \le n$）。

特别地，当 $n=1$ 时，$a_1$ 只能等于 $k$。

参考代码

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

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=200005;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		if(n==1)
		{
			cout<<k<<' ';
			continue;
		}
		int a1=0;
		for(int i=0;i<=30;i++)
		{
			int x=1<<i;
			if(a1+x<=k)a1+=x;
		}
		cout<<a1<<' '<<k-a1<<' ';
		for(int i=3;i<=n;i++)cout<<0<<' ';
		cout<<'\n';
	}
	return 0;
}