思路:二进制枚举

考虑要找n个数，使得这n个数的或和为k，那么我们可以枚举k的二进制表示中的每一位，如果这一位是1，那么我们就可以选这一位，否则不选。

这样我们可以找到2^x个数，其中x是k的二进制表示中1的个数。

一种情况导致答案不存在：

1.如果n > 2^x，那么答案一定不存在

代码

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        
        List<Integer> posOne = new ArrayList<>();
        for (int i = 0; i < 61; i++) {
            if ((k & (1L << i)) != 0) {
                posOne.add(i);
            }
        }
        
        int numOne = posOne.size();
        long states = 1L << numOne; // 2^x
        List<Long> res = new ArrayList<>();
        
        for (int i = 1; i < states; i++) {
            long now = 0;
            for (int j = 0; j < numOne; j++) {
                if ((i & (1 << j)) != 0) {
                    now += (1L << posOne.get(j));
                }
            }
            res.add(now);
            if (res.size() == n) {
                break;
            }
        }
        if (res.size() < n) {
            System.out.println("NO");
        } else {
            res.set(res.size() - 1, k);
            System.out.println("YES");
            for (long val : res) {
                System.out.print(val + " ");
            }
        }
    }
}

python

n , k = map(int, input().split())
pos_one = []
for i in range(61):
    if k & (1 << i):
        pos_one.append(i)
num_one = len(pos_one)
states = 1 << num_one
res = []
for i in range(1 , states):
    now = 0
    for j in range(num_one):
        if i & (1 << j):
            now += 1 << pos_one[j]
    res.append(now)
    if len(res) == n:
        break
if len(res) < n:
    print("NO")
else:
    res[-1] = k 
    print("YES")
    print(*res)

cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;

    vector<int> posOne;
    for (int i = 0; i < 61; i++) {
        if ((k & (1LL << i)) != 0) {
            posOne.push_back(i);
        }
    }

    int numOne = posOne.size();
    long long states = 1 << numOne; // 2^x
    vector<long long> res;

    for (int i = 1; i < states; i++) {
        long long now = 0;
        for (int j = 0; j < numOne; j++) {
            if (i & (1 << j)) {
                now += (1LL << posOne[j]);
            }
        }
        res.push_back(now);
        if ((int)res.size() == n) {
            break;
        }
    }

    if ((int)res.size() < n) {
        cout << "NO" << endl;
    } else {
        res[n - 1] = k;
        cout << "YES" << endl;
        for (long long val : res) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小明认为一个序列${a_1,a_2,…,a_n}$是完美序列需要满足以下条件

对于仼意的$2≤i≤n$, 都满足$0<a_{i-1}<a_i≤2^{60}$;

$a_1$ $or$ $a_2$ $or...or$ $a_n=k$

现在他给你$n$和$k$，请你帮助他构造一个合法的序列$a$。

在本题中，$or$代表位运算中的按位或运算。

输入描述

在一行上输入两个整数$n,k(1≤n≤10^5; 0≤k≤2^{60})$。

输出描述

如果存在这样的合法序列，在第一行输出一个$YES$;随后，第二行输出$n$个整数代表序列。

否则，直接输出$NO$。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。

注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

3 7

输出

YES
2 3 7

说明

在这一个测试数据中，${1,2,4}、{1,2,7}$等也是合法的构造方案。

示例2

输入

2 1

输出

NO