20240531每日一题

2024年5月31日 CF1965B 1800

题目链接

CF1965B

题目翻译

给你两个整数 n 和 k 。求一个长度至多为 25 的非负整数序列 a ，使得下列条件成立。

• 没有和为 k 的 a 的子序列。
• 对于 v ≠ k 所在的所有 1 ≤ v ≤ n ，存在一个和为 v 的 a 的子序列。

如果 b 可以从 a 中删除几个（可能是零个或全部）元素，而不改变其余元素的顺序，那么序列 b 就是 a 的子序列。例如， [5, 2, 3] 是 [1, 5, 7, 8, 2, 4, 3] 的子序列。

可以证明，在给定的约束条件下，解总是存在的。

题目思路

由于题目要求答案最多25个数，不考虑k，由于 2²⁰ = 1048576 ，只需要20个数就能填满1-1e6。即 [1, 2, 4, ...2¹⁹] 接下来想办法去掉k。记k二进制数的最高位记为x，例如2的二进制数为10，x=2。 我们先加入 [1, 2, 4, ...2^x − 2] ,我们能获得1到 2^x − 2 的数。（x=1时不加入任何数） 再加入 k-( 2^x − 2 -1)-1，得到1到k-1的数。 加入 [2^x, 2^x + 2, ...2¹⁹] 后，我们只剩下k+1 到 2^x − 1没有添加进去。 加入 k+1 得到 k+1 到 2k的数. 加入 2k+1 我们得到 除了3k+1以外的 1到4k+1的数。 我们能证明3k > 2^x − 1我们就得到了所有的数。 我们用23个数得到了所有的数。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k,cnt;
vector<int>res;
void solve(){
    cin>>n>>k;
    res.clear();
    for(int i=0;i<=20;i++){
        if((1<<(i+1))-1>=k){
            cnt=i;
            res.push_back(k-((1<<cnt)-1)-1);
            res.push_back(k+1);
            res.push_back(2*k+1);
            break;
        }else{
            res.push_back((1<<i));
        }
    }
    for(int i=cnt+1;i<=20;i++){
        res.push_back((1<<i));
    }
    cout<<res.size()<<'\n';
    for(auto i:res){
        cout<<i<<' ';
    }
    cout<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}