CF2072C Creating Keys for StORages Has Become My Main Skill

题目描述

Akito 仍然无处可住，而小房间的价格却居高不下。为此，Akito 决定在银行找一份为存储设备创建密钥的工作。

在这个魔法世界中，一切都与众不同。例如，代码为 $(n,x)$ 的存储设备的密钥是一个满足以下条件的长度为 $n$ 的数组 $a$：

• $a_1\mid a_2\mid a_3\mid \dots \mid a_n=x$，其中 $a\mid b$ 表示数 $a$ 和 $b$ 的按位或运算。
• MEX ( { a 1 , a 2 , a 3 , … , a n } ) \text{MEX}(\{ a_1, a_2, a_3, \ldots, a_n \}) MEX({a1​,a2​,a3​,…,an​}) ${}^{\text{∗}}$ 在所有满足条件的数组中达到最大值。

Akito 勤奋地工作了几个小时，但突然头痛发作。请代替他工作一小时：对于给定的 $n$ 和 $x$，创建任意一个满足代码为 $(n,x)$ 的存储设备的密钥。

${}^{\text{∗}}$ $\text{MEX}(S)$ 是满足以下条件的最小非负整数 $z$：$z$ 不在集合 $S$ 中，且所有满足 $0\le y<z$ 的 $y$ 都在集合 $S$ 中。

输入格式

第一行包含一个数 $t$（$1\le t\le 10^4$）——测试用例的数量。

每个测试用例的唯一一行包含两个数 $n$ 和 $x$（$1\le n\le 2\cdot 10^5$，$0\le x<2^{30}$）——数组的长度和按位或运算的目标值。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $a_i$（$0\le a_i<2^{30}$）——满足所有条件的密钥数组元素。

如果存在多个符合条件的数组，输出其中任意一个即可。

形式化题面

给你两个整数 $n$ 和 $x$，你需要构造一个长度为 $n$ 的数列，使整个数列或起来的结果为 $x$，且包含尽量多的从零开始的连续的数。

思路

本题并没有用什么高超的算法。

我们知道，一个数或上另一个数，每一个二进制位一定不会减少。所以，从零考虑，依次或上连续的自然数，当结果有一位大于 $n$ 时，就没有办法或上任何个数的数结果为 $n$ 了。

如果将 0 到 $n-1$ 的数或起来，仍然到不了 $x$，则 MEX 值一定到不了 $n$ ,而如果我们的方案 MEX 值为 $n-1$，则是最优解。

于是可以贪心……

code

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,x,cnt=0;
		cin>>n>>x;
		for(int i=0;i<n;i++){
			cnt|=i;
			if((cnt|x)>x){//当或上这个数cnt有任意一位大于x
				for(;i<n;i++){//不要这个数了，最后输出x凑数
					cout<<x<<" ";
				}
				break;
			}
			if(i==n-1){
				if(cnt<x){//把0到n-1全或上也不够x
					cout<<x;//直接或上x不就够了吗
					break;
				}
			}
			cout<<i<<" ";
		} 
		cout<<'\n';
	}
  return 0;
}