CF 578B "Or" Game

解题思路

题意大概是给你一个数列，可以进行k次操作，每次操作可以选择一个数乘x，问操作后的或的最大值。根据位运算，位数越高答案越优，所以贪心的使这k次操作全都放到一个数上，这样的结果肯定较优。之后算一个原数列的前缀or和与后缀or和，枚举每一个数使其乘x^k并更新答案。后缀or和的思想非常巧妙。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN = 200005;

typedef long long LL;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,k,x,a[MAXN];

LL ans,sum1[MAXN],sum2[MAXN];  //sum1表示前缀异或和，sum2表示后缀

inline LL fast_pow(int a,int b){

    LL ret=1;

    for(;b;b>>=1){

        if(b&1) ret*=a;

        a*=a;

    }

    return ret;

}

int main(){

    n=rd();k=rd();x=rd();

    for(register int i=1;i<=n;i++){

        a[i]=rd();

        sum1[i]=(sum1[i-1]|a[i]);

    }

    for(register int i=n;i;i--) sum2[i]=(a[i]|sum2[i+1]);

    LL mx=fast_pow(x,k);

    for(register int i=1;i<=n;i++)

        ans=max(ans,(LL)a[i]*mx|sum1[i-1]|sum2[i+1]);

    printf("%lld",ans);

    return 0;

}

巴特西

CF 578B "Or" Game

解题思路

代码

最新文章

热门文章