题目链接
有一种操作
f
(
x
,
y
)
=
(
x
∣
y
)
−
y
f(x,y)=(x|y)−y
f(x,y)=(x∣y)−y，给你一个序列
a
1
,
a
2
,
.
.
.
,
a
n
。
a1,a2,...,an。
a1,a2,...,an。 让你改变一下序列a的顺序，让
f
(
f
(
.
.
.
f
(
f
(
a
1
,
a
2
)
,
a
3
)
,
.
.
.
,
a
n
−
1
)
,
a
n
)
f(f(...f(f(a1,a2),a3),...,an−1),an)
f(f(...f(f(a1,a2),a3),...,an−1),an)最大。
我们看这样一个操作他代表着什么？
我们把x,y拆解成二进制，x|y就相当于让两方都有1的一起有1了，然后−y就是让y位置上有1的减去。
举个例子，比如说x=1101,y=0111，那么就相当于说把x的最后一位1和第二位1带走了。
把所有数字拆成二进制，如果一个位置上的1，出现了多次（大于1），那么这个位置上的1肯定留不住。
所以我们就找最高位的出现一次的1，然后把它放到最前面去，之后的数字随便摆放。
可以模拟一下这个样例，9 5 9，把5摆到最前面上是最优解。
#include<bits/stdc++.h>
using namespace std
;
const int maxn
= 1e5+10;
int n
, a
[maxn
];
int num
[40];
int cnt
;
int main()
{
scanf("%d", &n
);
for(int i
= 1; i
<= n
; i
++)
{
scanf("%d", &a
[i
]);
int x
= a
[i
];
int tmp
= 0;
while(x
)
{
if(x
&1) num
[tmp
++] += 1;
else num
[tmp
++] += 0;
x
>>= 1;
}
cnt
= max(cnt
, tmp
);
}
int pos
= -1;
for(int i
= cnt
-1; i
>= 0; i
--)
if(num
[i
] == 1)
{
pos
= i
;
break;
}
if(pos
== -1)
{
for(int i
= 1; i
<= n
; i
++)
printf("%d ", a
[i
]);
return 0;
}
for(int i
= 1; i
<= n
; i
++)
{
if(a
[i
]>>pos
&1)
{
swap(a
[i
], a
[1]);
break;
}
}
for(int i
= 1; i
<= n
; i
++)
printf("%d ", a
[i
]);
return 0;
}
