首页 > 试题广场 >

完美异或

[编程题]完美异或

热度指数：550 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，如果满足以下两条性质，则称其为伟大数组：
${\hspace{20pt}}_\texttt{1.}\,$ 数组单调非降，且所有元素都是非负整数；
${\hspace{20pt}}_\texttt{2.}\,$ 其异或和 $\displaystyle \bigoplus_{i=1}^{n} a_i$ 是 $n$ 的一个因子，即 $n \bmod \left(\bigoplus_{i=1}^{n} a_i\right)=0$ 。

$\hspace{15pt}$ 现在给定整数 $n$ ，请你构造一个长度为 $n$ 的伟大数组，或者判断不存在这样的数组。

$\hspace{15pt}$ 【名词解释】
$\hspace{23pt}\bullet\,$ 按位异或： $\mathrm{xor}$ 表示按位异或运算，运算方法为对两个整数的对应二进制位进行比较：若两位相同则结果为 $0$ ，不同则结果为 $1$ 。
$\hspace{23pt}\bullet\,$ 异或和： $\displaystyle\bigoplus_{i=1}^{n} a_i$ 表示将所有 $a_i$ 依次按位异或得到的结果。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下： 
在一行上输入一个整数  —— 需要构造的数组长度。 
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据： 
如果存在伟大数组，请在一行上按照非递减顺序输出  个整数 ； 
如果不存在伟大数组，直接输出一个整数 。 
如果存在多种可行答案，你可以输出任意一种即可，系统会自动判定是否正确。

示例1

输入

输出

1
1 3
2 2 3

说明

在这一组样例中： 
 时，数组  的异或和为 ，显然 ； 
 时，数组  的异或和为 ，并且 ； 
 时，数组  的异或和为 ，并且 。

备注:

算法知识视频讲解

DPsans

额...排行最高的那几个直接输出-1的做法是怎么回事(

发表于 2025-12-03 16:51:58 回复(0)

提交观点

问题信息

难度：

1条回答 4收藏 24浏览

相关试题

完美异或

扫描二维码，关注牛客网
意见反馈
下载牛客APP，随时随地刷题

扫一扫，把题目装进口袋

求职之前，先上牛客: 扫描二维码，进入QQ群



扫描二维码，关注牛客公众号

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号

完美异或

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

相关试题