题解：AT_agc071_a [AGC071A] XOR Cross Over

· · 题解

\text{Solution}

很好的推性质题，虽然场切了但是有点慢（差点掉大分）。

原题意显然没有入手点，那么我们考虑先从操作上找性质。容易发现的是自一次划分过后，每个数都会异或上另一边的异或和，那么这个异或的值的传递性会与序列的奇偶性密切相关。

具体看图：

由此可得，当分裂出一个长度为偶数段时，可以将其看作一个独立的子问题忽略之前的异或值。

证明：由上图之，一个长度为偶数的字符串分裂成两个为奇数的序列，两者都会抵消掉之前的贡献；而分裂成两个偶数的序列又变成两个子问题。由于最终状态为若干个长度为 1 的序列，所以中途一定会出现一个长度为偶数的序列分裂为两个长度为奇数的序列的情况。

接着我们考虑奇数段，奇数的性质是一定会拆分成一奇一偶，而偶数段成为可以忽略掉前面的变化，奇数段会继承前面的变化，因为一定会又一个奇数段，所以最后一定会有一个值为当前奇数段所有元素异或和的长度为 1 的序列。而且手玩一下不难发现最终变成异或和的这个位置一定是当前序列的奇数位。

由此我们考虑区间 DP，我们记 f_{i,j} 表示 [i,j] 这一段区间能变成的最小和。

那么对于奇数段显然有：

f_{i,j}=\min\limits_{(i\leq k\leq j) \land (k-i+1\bmod2=1)}f_{i,k-1}+\oplus_{l=i}^{j}a_l+f_{k+1,j}

接着考虑偶数，若分为两个偶数，则可以直接左右相加转移，即

f_{i,j}=\min\limits_{(i\leq k\leq j) \land (k-i+1\bmod2=0)}f_{i,k}+f_{k+1,j}

若分为两个奇数，则会发现，所分成的奇数段中不会在出现这个奇数段的数的异或和，而是会再次基础上异或上另一段奇数段的异或和，即原本那个偶数序列的全局异或和。容易发现一个定值的替换不会影响到取到最小值的位置，所以有：

f_{i,j}=\min\limits_{(i\leq k\leq j) \land (k-i+1\bmod2=1)}f_{i,k-1}-\oplus_{l=i}^{k-1}a_l+f_{k,j}-\oplus_{l=k}^{j}a_l+2\oplus_{l=i}^{j}a_l

以上就是转移过程，注意一些细节：

  1. 初始化要将 f_{i,i} 设为 a_i；
  2. 初始化要将 f_{i,i-1} 设为 0；
  3. 本人代码的实现中并未使用前缀异或和而是新拿了一个数组 g，g_{i,j}=f_{i,j}-\oplus_{l=i}^{j}a_l，则 g_{i,i} 要设为 0。
/*
    Luogu name: Symbolize
    Luogu uid: 672793
*/
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define rep1(i,l,r) for(register int i=l;i<=r;++i)
#define rep2(i,l,r) for(register int i=l;i>=r;--i)
#define rep3(i,x,y,z) for(register int i=x[y];~i;i=z[i])
#define rep4(i,x) for(auto i:x)
#define debug() puts("----------")
const int N=1e3+10;
const int inf=0x3f3f3f3f3f3f3f3f;
using namespace std;
int n,a[N],f[N][N],g[N][N];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return f*x;
}
signed main()
{
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    n=read();
    rep1(i,1,n) a[i]=read();
    memset(f,inf,sizeof f);
    memset(g,inf,sizeof g);
    rep1(i,1,n) f[i][i]=a[i],g[i][i]=0;
    rep1(i,1,n+1) f[i][i-1]=0;
    rep1(len,2,n)
    {
        rep1(i,1,n-len+1)
        {
            int j=i+len-1,now=0;
            rep1(k,i,j) now^=a[k];
            if(len&1)
            {
                for(int k=i;k<=j;k+=2)
                {
                    f[i][j]=min(f[i][j],f[i][k-1]+now+f[k+1][j]);
                    g[i][j]=min(g[i][j],f[i][k-1]+f[k+1][j]);
                }
            }
            else
            {
                for(int k=i;k<=j;k+=2)
                {
                    f[i][j]=min(f[i][j],g[i][k]+g[k+1][j]+2*now);
                }
                for(int k=i+1;k<=j;k+=2)
                {
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
                }
            }
        }
    }
    cout<<f[1][n]<<"\n";
    return 0;
}