题解：CF1957B A BIT of a Construction

lailai0916 · 2024-04-22 22:02:55 · 题解

题意简述

构造长度为 n 的自然数列 a，满足 \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 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<<'\n';
            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;
}