Codeforces Round #618 (Div. 2)：C. Anu Has a Function

红太狼 2023-07-05 10:16 6阅读 0赞

**Discription**  
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.

**Examples**  
**input**

4
    4 0 11 6

**output**

11 6 4 0

**input**

1
    13

**output**

**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.

\[11,4,0,6\] is also a valid answer.

**题意**  
给定一个公式：f(x,y)=(x|y)−y  
给定n个数，要求将这n个数任意排序，使满足公式的结果最大（前两项的结果做下一项的第一项）  
输出任意一个最大结果的项。

**思路**  
在二进制状态下求解在所有的数中，某一位只出现了一次1，且为最大的那个，放在第一位，剩下的按任意顺序输出。  
eg：二进制状态下：  
1100 1101 1100 1110  
则将1110放在第一位。

**AC代码**

#include <bits/stdc++.h>
    using namespace std;
    int a[100010];
    int n,cnt,k,t;
    int main()
    { 
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int j=30; j>=0; j--)
        { 
            cnt=0;
            for(int i=1; i<=n; i++)
                if((a[i]>>j)&1)
                    cnt++,k=i;
            if(cnt==1)
                break;
        }
        if(cnt==1)
            t=a[1],a[1]=a[k],a[k]=t;
        printf("%d",a[1]);
        for(int i=2; i<=n; i++)
            printf(" %d",a[i]);
        printf("\n");
    }