题解：P16683 盆栽

See_you_soon · 2026-05-31 15:22:23 · 题解

题目传送门

题目大意

给定一个长度为 n 的序列 a，对于每一个给定的 k，你可以选择一段区间（也可以不选），对于区间内的每一个 a_{i} 变成 a_{i}\oplus k，问序列和最小和最大是多少。

Solution

优先把原序列 a 的总和统计起来，然后对于每一个 k 我们令序列变为 a_{i}\oplus k-a_{i}，然后问题就变成了在序列上找出最小子段和与最大子段和，之间从前往后依次处理就好了。最后如果最小子段和大于 0，为了保证其最小，我们不选择区别进行 k 操作，即答案就是一开始统计的总和，同理，最大子段和如果小于 0，我们也是直接输出最初的总和。

:::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(c>='0' && c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n=read(),m=read(),a[N],b[N],sum;
signed main(){
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum+=a[i];//统计最初总和 
    }
    for(int i=1;i<=m;i++){
        int k=read();
        for(int i=1;i<=n;i++) b[i]=(a[i]^k)-a[i];
        int cur1=b[1],mn=b[1],cur2=b[1],mx=b[1];
        for(int i=2;i<=n;i++){//找出最小子段和与最大子段和 
            cur1=min(b[i],cur1+b[i]);
            mn=min(mn,cur1);
            cur2=max(b[i],cur2+b[i]);
            mx=max(mx,cur2);
        }
        printf("%lld %lld\n",sum+min(0ll,mn),sum+max(0ll,mx));
    }
    return 0;
}

:::