AT4168

Aryper · 2021-07-10 15:08:14 · 个人记录

[ARC100C] Or Plus Max

ARC 的题。。。高维前缀最大值和次大值感觉倒也说得通，脑子里面还是更喜欢以 DP 的方式理解。

这里 i|j 是或运算的意思。

对于 k 来说，设存在小于 k 的数 p ，则若 i|j\le p 则会有 i|j\le k 。

同时对于 k 来说，在二进制下，若 i,j 的每一位都不大于 k 的对应位，则必有 i|j\le k 。

那么“满足 i,j 的每一位都不大于 p(p\le k) 的对应位的 所有数对 (i,j) ”中 a_i+a_j 最大者就是答案。

这是大体的思路。

下面是关于如何找到 “满足 i,j 的每一位都不大于 k 的对应位的数对 (i,j) ” 中的答案。

用到一点 DP 的想法。

我们的目标是要求出最大值和次大值，定义 f_q 为一个状态，这个状态表示 “满足 i,j 的每一位都不大于 q 的对应位的数对 (i,j) ”中的最大值与次大值。

那么我们需要考虑如何通过之前的状态转移得到 f_q 。

由此我们可知，找到所有的数 r （r 的每一位都不大于 q 的每一位，且必有一位小于 q 的对应位），则所有的 f_r 可推至 f_q 。

所以按此推法，我们不需要找到所有的 r ，只需要找到 s （s 满足 s 的某一位不大于 q ，其余位与 q 相等），则所有的 f_s 即可推至 f_q 。

时间复杂度 O(n\cdot2^n) 。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;

const ll N=1<<18;

ll n,pre,ans;

ll a[N+5],c[N+5],c_[N+5];//c 表示某个状态的最大值，c_ 表示某个状态的次大值

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();

    for(ll i=0;i<(1<<n);i++) {
        a[i]=read();c[i]=a[i];
    }

    for(ll j=0;j<=n;j++) {//循环嵌套的顺序为保证转移正确
        for(ll i=0;i<(1<<n);i++) {
            if((i>>j)&1) {//寻找上述 s
                pre=i^(1<<j);//表示第 j 位取反，找到了 s
                if(c_[pre]>c[i]) {
                    c_[i]=c[i];c[i]=c_[pre];
                }
                else
                if(c_[pre]>c_[i]) c_[i]=c_[pre];
                if(c[pre]>c[i]) {
                    c_[i]=c[i];c[i]=c[pre];
                }
                else
                if(c[pre]>c_[i]) c_[i]=c[pre];//以上比较皆为状态转移
            }
        }
    }

    for(ll i=1;i<(1<<n);i++) {
        ans=max(ans,c[i]+c_[i]);
        write(ans);putchar('\n');
    }

    return 0;
}