题解：P16787 [蓝桥杯 2026 国 A] 生态廊道

ADay · 2026-06-08 23:37:04 · 题解

Solution

考虑选择一个区间对答案的增量。

如果选择的两个长度为 3 的区间不连续，那么它们对答案的增量是独立的可以分别计算，然后统计两个不连续区间增量之和的最大值。

如果选择的是连续的 6 个数，那么中间两个数的异或值是受这两个区间重排结果影响的，那就枚举这两个区间的所有 6\times 6=36 种情况，一起计算增量即可。

#include<bits/stdc++.h>
using namespace std;
namespace io{快读}using namespace io;
const int N=2e5+5,p[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
#define ll long long
int n;ll a[N];
ll gt(int x,int a0,int a1,int a2){
    ll res=(a0^a1)+(a1^a2);
    if(x>3)res+=(a[x-3]^a0);
    if(x<n)res+=(a2^a[x+1]);
    return res;
}
#define b1(k) a[x-p[i][k]]
#define b2(k) a[x-3-p[j][k]]
ll calc3(int x){//长度为3的区间的增量
    ll mxres=0,res=gt(x,a[x-2],a[x-1],a[x]);
    for(int i=0;i<6;i++){
        mxres=max(mxres,gt(x,b1(2),b1(1),b1(0)));
    }return mxres-res;
}
ll calc6(int x){//长度为6的区间的增量
    ll mxres=0,res=0;
    for(int i=0;i<6;i++){
        for(int j=0;j<6;j++){
            ll now=(b2(2)^b2(1))+(b2(1)^b2(0))+(b2(0)^b1(2))+(b1(2)^b1(1))+(b1(1)^b1(0));
            if(x>6)now+=(a[x-6]^b2(2));
            if(x<n)now+=(b1(0)^a[x+1]);
            mxres=max(mxres,now);
            if(!i&&!j)res=now;
        }
    }return mxres-res;
}
ll mx[N];
int main(){
    read(n);
    ll sum=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(i>1)sum+=(a[i-1]^a[i]);
    }ll ans=0;
    for(int i=3;i<=n;i++){
        ll c=calc3(i);
        mx[i]=max(mx[i-1],c);
        if(i>=7)ans=max(ans,c+mx[i-4]);
    }
    for(int i=6;i<=n;i++)
        ans=max(ans,calc6(i));
    printf("%lld",sum+ans);
    return 0;
}