锐客网

  1. 首页 > 生活百科 > it技术 > >

CF 1299.A——Anu Has a Function二进制

IT知识二进制function

胸怀万里世界， 放眼无限未来。这篇文章主要讲述CF 1299.A——Anu Has a Function二进制相关的知识，希望能为你提供帮助。


??题目传送门??
Anu has created her own function f: f(x,y)=(x|y)?y where | denotes the bitwise OR operation. For example, f(11,6)=(11|6)?6=15?6=9. It can be proved that for any nonnegative numbers x and y value of f(x,y) is also nonnegative.
She would like to research more about this function and has created multiple problems for herself. But she isn’t able to solve all of them and needs your help. Here is one of these problems.
A value of an array [a1,a2,…,an] is defined as f(f(…f(f(a1,a2),a3),…an?1),an) (see notes). You are given an array with not necessarily distinct elements. How should you reorder its elements so that the value of the array is maximal possible?
Input
The first line contains a single integer n (1≤n≤105).
The second line contains n integers a1,a2,…,an (0≤ai≤109). Elements of the array are not guaranteed to be different.
Output
Output n integers, the reordering of the array with maximum value. If there are multiple answers, print any.
inputCopy

4
4 0 11 6
1
13
outputCopy
11 6 4 0
13
Note
In the first testcase, value of the array [11,6,4,0] is f(f(f(11,6),4),0)=f(f(9,4),0)=f(9,0)=9.
【CF 1299.A——Anu Has a Function二进制】[11,4,0,6] is also a valid answer.
题意
  • 定义一个函数
  • 给定一个长度为 数列 ，定义

    为这个数列的值
  • 现在，请你将数列改变一种顺序，使得最后的值最大。
  • 输出你改变后的数列。
题解
  • 我们发现这个函数实际上就是把y二进制有1的位，在x中减去，就是x的二进制去掉了y二进制有1的位
  • 那么其实答案之和第一个数有关，剩下的顺序无关
  • 找到最大的、某一位只有一个1的，将这个数方到最前面就行。
AC-Code
#include< bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 7;

int a[maxn];

int main()
ll n; while (cin > > n)
for (ll i = 0; i < n; ++i)
cin > > a[i];
bool flag = true;
for (ll i = 30; i > = 0 & & flag;

    推荐阅读


    上一篇：2020牛客寒假算法基础集训营5.J——牛牛战队的秀场

    下一篇：2020牛客寒假算法基础集训营5.C——C语言IDE超级大模拟