首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces Round 618 (Div. 2)C. Anu Has a Function

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

作者头像
xiaohejun
发布2020-02-21 11:09:39
3090
发布2020-02-21 11:09:39
举报

题目大意

原题链接C. Anu Has a Function

定义$f(x, y) = (x|y)-y$,有一个数组$A$可以为$[a_1, a_2, …, a_n]$,重排$A$中的元素使得$f(f(…f(f(a_1,a_2),a_3),…a_{n-1}),a_{n})$的值最大,输出重排后的$A$

题解

思路1:

对于式子$f(x, y)=(x|y)-y$,考虑$x$和$y$的二进制位

当$y$的第$i$位是1的时候,$x$的$i$位是0还是1对结果的第$i$位都没有影响,结果的第$i$位都是0

当$y$的第$i$位是0的时候,结果的第$i$位等于$x$的第$i$位

最终的结果只和把谁放在$A$中第一的位置有关,也就是说对于$a_1, a_2, a_3, …, a_n$如果想把其中的一个数字$x$放在第一个,那么当$x$的第$i$位是1的时候,数组中的其他数字的第$i$位必须全部是0函数的结果的第$i$位置才能取得1,如果$x$的第$i$位是0的话,那么函数的结果的第$i$位一定是0,所以对与每一个$a_i$我们都算一下函数的最终结果,然后把最大的位置的那个放在第一个即可。

以上思路来自Akura_Mea

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e5+100;
int a[MAX_N];
int bit[60];
 
void in(int a){
    int idx = 0;
    while(a){
        if(a&1){
            bit[idx]++;
        }
        a >>= 1;
        ++idx;
    }
}
 
int out(int a){
    int idx = 0, ans = 0;
    while(a){
        if((a&1) && (bit[idx] == 1)){
            ans = ans + (1 << idx);
        }
        a >>= 1;
        ++idx;
    }
    return ans;
}
 
int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int mx = 0;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        in(a[i]);
    }
    int idx = -1;
    for(int i = 0; i < n; ++i) {
        int tmp = out(a[i]); 
        if(tmp > mx){
            idx = i;
            mx = tmp;
        }
    }
    if(idx != -1) cout << a[idx] << ' ';
    for(int i = 0; i < n; ++i){
        if(i == idx) continue;
        cout << a[i] << ' ';
    }
    return 0;
}

思路2:

官方题解的做法是$f(x, y) = (x|y)-y = x \& (\sim y)$,

要求$f(f(…f(f(a_1,a_2),a_3),…a_{n-1}),a_{n})$,

等价于求$a_1\&(\sim a_2)\&(\sim a_3)\&…\&(\sim a_{n-1})\&(\sim a_{n})$,

从式子可以看出最终的结果只和哪一个放在第一的位置有关,所以维护一个取反的前缀和还有一个取反的后缀和,就能算出哪一个放在$a_1$的位置得到的最终结果最大

def wrapper(func):
    def inner():
        return next(func)
    return inner

#input = wrapper(open('in.txt'))

n = int(input())
a = list(map(int, input().strip().split()))
INF = (1 << 60) - 1
pre = [0] * (n+1)
pre[n] = INF
for i in range(n):
    if i == 0:
        pre[i] = ~a[i]
    else:
        pre[i] = pre[i-1] & (~a[i])
suf = [0] * (n+1)
suf[n] = INF
for i in range(n-1, -1, -1):
    if i == n-1:
        suf[i] = ~a[i]
    else:
        suf[i] = suf[i+1] & (~a[i])
mx, id = -1, -1
for i in range(n):
    tmp = a[i] & pre[i-1] & suf[i+1]
    if tmp > mx:
        mx = tmp
        id = i
print(a[id], end=' ')
for i in range(n):
    if i == id:
        continue
    print(a[i], end = ' ')

总结

可以看出上面两种思路实现方法不一样,但是原理都一样

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-02-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 题解
    • 思路1:
      • 思路2:
      • 总结
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档