题解：AT_agc071_a [AGC071A] XOR Cross Over

· · 题解

半年前做过它，当时不会，由于在学文化也没学，今天晚自习自己做出来了。

首先设 b_i 表示第 i 个位置最后的结果。

容易发现，b_i=\text{xor}_{i} a_{i}，不妨打表看看 b_i 被哪些 a_i 影响。

打表代码：

#include <bits/stdc++.h>
using namespace std;
const int N=15;
bitset<N> a[N];
int n,v[N],p[N],fl[N];
void dfs(int x){
    if(x==n){
        for(int i=1;i<=n;i++) a[i]=0,a[i][i]=1;
        for(int i=1;i<=n;i++) fl[i]=0;
        fl[0]=fl[n]=1;
        for(int i=1;i<n;i++){
            bitset<N> al=0,ar=0;
            for(int j=p[i];!fl[j];j--) al^=a[j];
            for(int j=p[i]+1;;j++){ar^=a[j];if(fl[j]) break;}
            for(int j=p[i];!fl[j];j--) a[j]^=ar;
            for(int j=p[i]+1;;j++){a[j]^=al;if(fl[j]) break;}
            fl[p[i]]=1;
        }
        cout<<"dfs::\n";
        for(int i=1;i<n;i++) cout<<p[i]<<' '; cout<<'\n';
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++) cout<<a[i][j];
            cout<<'\n';
        }
        return ;
    }
    for(int j=1;j<n;j++) if(!v[j]){
        v[j]=1; p[x]=j;
        dfs(x+1);
        v[j]=0;
    }
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    n=8;
    dfs(1);
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}

下文称偶数区间是长度为偶数的区间，奇数区间是长度为奇数的区间。

我们可以发现很多事情：

1.对 i 有影响的数构成一个包含 i 的区间（下文称为影响区间）；

2.对于偶数的 n 来说，所有影响区间 都是 偶数区间；

这告诉我们做操作做到一个偶数区间时，我们不关心这个区间外面对里面的贡献，因为一个里面的位置都会把外面的贡献异或偶数次。

3.对于奇数的 n 来说，恰好 存在一个位置的影响区间长度是偶数。

我们设这个位置是 p，我们还能发现：

4.对于奇数的 n 来说，p 的影响区间是 [1,n]。

5.对于奇数的 n 来说，除了 p 的其他位置的影响区间 不包含 p。

6.对于奇数的 n 来说，p 把整个序列划分成两个偶数区间，换言之 p 是奇数。

根据发现的性质 4,5,6 我们猜测，答案就是 [1,p) 的答案 +(p,n] 的答案 +\text{xor}_{i=1}^n a_{i}。

这个时候我们再来看 n 是偶数的情况。

若下一次操作把他划分成两个偶数区间，由于我们已经推导出了“偶数区间不关心外面对里面的贡献”这件事，所以可以直接划分成两个独立的子问题。

若下一次操作把他划分成两个奇数区间，根据性质 3，我们只关心贡献对 p 的影响。通过打表观察或者直接分析能发现两个区间的 p 的影响区间为 [1,n]，所以还是能划分成两个独立的子问题。

然后我们就可以 dp 了：设 f_{l,r} 表示在 不考虑 区间外的影响，能操作到的 \min\sum b_i (即就把区间 [l,r] 抠出来作为序列的答案)。根据上述结论转移是容易的。

时间复杂度 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=505;
const LL linf=1e16+10;
int n;
LL a[N],f[N][N],g[N][N];
void read(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
}
void dp(){
    for(int i=1;i<=n;i++) for(int l=1;l+i-1<=n;l++){
        int r=l+i-1;
        f[l][r]=linf;
        if(i&1){
            for(int k=l;k<=r;k+=2){
                f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+(a[r]^a[l-1]));
            }
        }else{
            for(int k=l+1;k<r;k+=2){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
            }
            for(int k=l;k<=r;k+=2){
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]-(a[k]^a[l-1])-(a[r]^a[k])+(a[r]^a[l-1])*2);
            }
        }
    }
    cout<<f[1][n]<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    read();
    dp();
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}

半年前那个还在迷茫徘徊的少年，我替你做出这道题了，你还满意吗？