CF1148F

Aryper · 2021-10-03 10:26:43 · 个人记录

Foo Fighters

首先肯定是要按位考虑的。

然后发现这个后效性十分烦人。

然后我们发现可以从最高位开始考虑，如果说最高位以前的数都决定好了，之后的数如何就对此没有影响了。

又因为我们只是要求符号取反，所以说对于最高位是该位的数来说，要么全部取反，要么全部不取反，也就是说，一定会有一负一正两种贡献。

那么我们一定选择与原符号相反的贡献，而且只要选择了，再把这个结果丢给高位就不会有影响了。

细节上，如果说该位为最高位的贡献为 0，我们尽量不给这一位赋 1，防止溢出。

时间复杂度 O(n\log s)。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=3e5;

ll n,sum;

unsigned ll s;

ll val[N+5];

unsigned ll mask[N+5];

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(unsigned ll x) {
    static char buf[22];static ll len=-1;
    do{buf[++len]=x%10+48;x/=10;}while(x);
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        val[i]=read();mask[i]=read();
        sum+=val[i];
    }

    for(ll i=0;i<62;i++) {
        ll tmp=0;
        for(ll j=1;j<=n;j++) {
            if(mask[j]>=(1ull<<i)&&mask[j]<(1ull<<(i+1))) tmp+=val[j];
        }
        if(tmp&&(tmp>0)==(sum>0)) {
            s|=1ull<<i;
            for(ll j=1;j<=n;j++) {
                if((mask[j]>>i)&1) val[j]=-val[j];
            }
        }
    }

    write(s);

    return 0;
}