Codeforces 1299A/1300C - Anu Has a Function

题目大意：

给定一种函数F(x,y)=(x|y)-y，| 即按位或运算

给定一个长度为n的数组a[1],a[2],a[3]...a[n]

可以重新排列数组a，使得 F ( ...... F ( F ( a[1] , a[2] ) , a[3] ) ...... , a[n] ) 最后得到的答案最大

问这样的一个排列（答案不唯一输出任意一个）

解题思路：

首先拿到这种函数，可以去找他的规律

举例两个二进制的数

11111

01010

这两个数先进行取或运算，得到

11111

再减去第二个数，得到

10101

可以发现，这种运算的意义就是

如果在二进制中，后一个数字的第 i 位是1，那么结果中的这一位必定为0

如果在二进制中，后一个数字的第 i 位是0，那么结果中的这一位相等于前一个数字的这一位的值

因为最终答案的计算方式是把数列中每个元素都一层一层套下去

所以可以发现，对于答案的第 i 位而言，如果有大于等于两个数字，或者没有一个数字第 i 位的值为1，那么答案的第 i 位必定为0

理由为：

　　1、如果没有一个数字第 i 位为1，显而易见第 i 位不可能突然冒出来一个1

　　2、如果大于等于两个数字第 i 位为1，那么不论怎么这两个数（或这些数）的先后顺序，后一个数字在函数执行完后都必会把这一位变成0

所以，最终答案的二进制中一定会有一位是在所有数字内只出现过一次的（如果答案不为0）

然后还能发现，只要前面套出来的答案中第 i 位已经为0，那么后面的所有数字中不论第 i 位是0还是1，最终答案的第 i 位都是0

所以，要尽量让大的数字靠前

又因为根据二进制而言，10000一定比01111大，即最高位比较高的数字一定大

所以答案就很明显了：

　　从高位往低位找，如果找到某一位只出现过一次，把这一位对应的那个数字提到数列最前端，其余数字随意排列均可，对答案不会造成影响。

以样例为例子

4 0 11 6

化为二进制即

0100

0000

1011

0110

得到（右数）第一位和第四位均只出现过一次

从最高位往最低位找，明显直接取第四位

出现的第四位为1的数是1011，即11

那么只要11出现在这个数列的头部，剩余三个任意排列，都不会改变答案的值（9）

即排列

11 0 4 6

11 0 6 4

11 4 0 6

11 4 6 0

11 6 0 4

11 6 4 0

六种排列答案相同

另外，如果没有任何一位满足要求，那么整个数组随便排列都行，因为答案必定为0

***题外话：如果此时求的是答案最大值的话，实际上也是这种求法，找到这个需要提到第一个位置的数后，检查这个数字剩余的值为1的位是不是也只出现过一次，把所有是1的只出现过一次的位提出来，就是答案。样例就是这样，第一位和第四位只出现一次的数都在1011，即11这个数上，那么答案就是把第一位和第四位取出，即1001，即9

代码为：

#include<bits/stdc++.h>

using namespace std;

int ar[],tim[],which[];

int main(){

    ios::sync_with_stdio();

    cin.tie();cout.tie();

    int n,i,j,k;

    cin>>n;

    memset(tim,,sizeof tim);

    for(i=;i<n;i++){

        cin>>ar[i];

        for(j=,k=;j<;j++){

            if(ar[i]&k){

                if(!tim[j])

                    which[j]=i;//记录第一次出现第j位为1的数

                tim[j]++;

            }

            k<<=;

        }

    }

    for(j=;j>=;j--){

        if(tim[j]==){//这一位是所有只出现一次的1的最高位

            swap(ar[],ar[which[j]]);

            break;

        }

    }

    for(i=;i<n;i++)

        cout<<ar[i]<<' ';

    return ;

}

巴特西

Codeforces 1299A/1300C - Anu Has a Function

最新文章

热门文章