Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] B. "Or" Game 线段树贪心

雨点打透心脏的1/2处 2022-04-10 10:24 180阅读 0赞

## B. "Or" Game ##

Time Limit: 1 Sec

Memory Limit: 256 MB

## 题目连接 ##

http://codeforces.com/contest/578/problem/B

## Description ##

You are given *n* numbers *a*1, *a*2, ..., *a**n*. You can perform at most *k* operations. For each operation you can multiply one of the numbers by *x*. We want to make ![d4b868177a5e377be1efa030a14bc456aa7757c9.png][] as large as possible, where ![851f0de9066e03abe3b9d7ff4cc047d9743a0729.png][] denotes the bitwise OR.

Find the maximum possible value of ![d4b868177a5e377be1efa030a14bc456aa7757c9.png][] after performing at most *k* operations optimally.

## Input ##

The first line contains three integers *n*, *k* and *x* (1 ≤ *n* ≤ 200 000, 1 ≤ *k* ≤ 10, 2 ≤ *x* ≤ 8).

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 109).

## Output ##

Output the maximum value of a bitwise OR of sequence elements after performing operations.

## Sample Input ##

3 1 2  
1 1 1

**Sample Output**

## HINT ##

**题意**

给你n个数，你可以操作k次，使得其中的某一个数乘以x

要求最后得到的所有数的或值最大

**题解：**

首先dp是错的，因为a>b不能保证a|c>b|c

这儿有一个贪心的操作，如果又一次乘法给了a1，那么剩下的都得给a1，这样才能得到最优值

因为x>=2可以保证最高位的1在不断增加

**代码：**

//qscqesze
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <ctime>
    #include <iostream>
    #include <algorithm>
    #include <set>
    #include <vector>
    #include <sstream>
    #include <queue>
    #include <typeinfo>
    #include <fstream>
    #include <map>
    #include <stack>
    typedef long long ll;
    using namespace std;
    //freopen("D.in","r",stdin);
    //freopen("D.out","w",stdout);
    #define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
    #define maxn 2000000 + 500
    #define mod 10007
    #define eps 1e-9
    int Num;
    char CH[20];
    //const int inf=0x7fffffff;   //нчоч╢С
    const int inf=0x3f3f3f3f;
    /*
    
    inline void P(int x)
    {
        Num=0;if(!x){putchar('0');puts("");return;}
        while(x>0)CH[++Num]=x%10,x/=10;
        while(Num)putchar(CH[Num--]+48);
        puts("");
    }
    */
    //**************************************************************************************
    long long n , k , x;
    
    struct tree
    {
        int L , R  ;
        ll sum;
    };
    
    tree a[maxn * 4];
    ll d[maxn];
    void build(int x,int l,int r)
    {
        a[x].L = l,a[x].R = r;
        if(l == r)
        {
            a[x].sum = d[l];
            return;
        }
        else
        {
            int mid = (l+r)>>1;
            build(x<<1,l,mid);
            build(x<<1|1,mid+1,r);
            a[x].sum = a[x<<1].sum | a[x<<1|1].sum;
        }
    }
    
    ll query(int o,int QL,int QR)
    {
        int L = a[o].L , R = a[o].R;
        if (QL <= L && R <= QR) return a[o].sum;
        else
        {
            int mid = (L+R)>>1;
            ll res = 0;
            if (QL <= mid) res |= query(2*o,QL,QR);
            if (QR > mid) res |= query(2*o+1,QL,QR);
            return res;
        }
    }
    int main()
    {
        cin>>n>>k>>x;
    
        for(int i = 1 ; i <= n ; ++ i)
        {
            scanf("%I64d",&d[i]);
        }
        build( 1 , 0 , n+1);
        ll ans = 0;
        ll temp = 1;
        for(int i=1;i<=k;i++)
            temp *= x;
        for(int i = 1 ; i <= n ; ++ i)
        {
            ans = max( ans , (d[i]*temp) | query(1,0,i-1) | query(1,i+1,n+1));
        }
        cout<<ans<<endl;
    }

[d4b868177a5e377be1efa030a14bc456aa7757c9.png]: /images/20220331/7f297d9e67094c9abf8bb4e6f4f86b23.png
[851f0de9066e03abe3b9d7ff4cc047d9743a0729.png]: /images/20220331/49b32f7c45d3482f9b2cd6beba40960e.png