题解 P9746 「KDOI-06-S」合并序列

· · 题解

考虑区间 DP。设 f_{l,r} 满足区间 [l,r] 的数能不能被缩成一个。转移则是枚举四个点 l\le a<b\le c<d\le r，满足 f_{l,a}=f_{b,c}=f_{d,r}=1 且三个区间里面数的异或和为零。

这样是 O(n^6) 的，不一定不能过。 考虑优化：设 f'_{l,r,k} 表示 [l,r] 的所有子区间中是否有异或和等于 k 的合法区间。转移则是 f'_{l,r,k}=f'_{l,r-1,k}\operatorname{or} f'_{l+1,r,k}，以及如果 f_{l,r}=1 则有 f'_{l,r,\operatorname{xor}_{i=l}^r a_i}=1。

这样是 O(n^4) 的，有很大概率能过。 考虑优化：设 g_{l,k} 表示左端点 >l 的区间中，异或和等于 k 的合法区间最小的右端点；h_{l,k} 表示满足 f_{l,a}=f_{b,c}=1，l\le a<b\le c，且 [l,a],[b,c] 两个区间异或和等于 k 的三元组 (a,b,c) 中，最小的 c 值。

其实 g 的意义就是找到 f 中的第二个区间，h 的意义就是找到 f 中的前两个区间。g 的转移类似 f'，h 的转移类似 f。对于 f_{l,r} 的合法性判定，只需要枚举第三个区间的左端点 d，看是不是有 h_{l,\operatorname{xor}_{i=d}^r a_i}<d 即可。

整个转移过程是 O(n^3) 的。接下来是构造：设 F_{l,r} 为 f_{l,r} 一组合法解中的 d，G_{l,k} 为一组 g_{l,k} 最优解中的区间左端点，H_{l,k} 为一组 h_{l,k} 最优解中的 a。答案从 f_{1,n} 逆推过去就行了。

总时间复杂度 O(Tn^3)。注意转移和构造的顺序。

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=511;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(ch>'9' || ch<'0')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int T,n,a[Maxn+5],s[Maxn+5];
int f[Maxn+5][Maxn+5],g[Maxn+5][Maxn+5],h[Maxn+5][Maxn+5];
int fk[Maxn+5][Maxn+5],gk[Maxn+5][Maxn+5],hk[Maxn+5][Maxn+5];
vector<array<int,3>> ans;

inline void Solve(int l,int r,int id)
{
    if(l==r) return;
    int d=fk[l][r],a=hk[l][s[r]^s[d-1]];
    int w=s[r]^s[d-1]^s[a]^s[l-1],b=gk[a+1][w],c=g[a+1][w];
    if(l==0) exit(0);
    Solve(d,r,id+(d-l)),Solve(b,c,id+(b-l)),Solve(l,a,id);
    ans.push_back({id,id+(b-l)-(a-l),id+(d-l)-(a-l)-(c-b)});
}
inline void Solve()
{
    n=read(); For(i,1,n) a[i]=read(),s[i]=s[i-1]^a[i];
    memset(f,0,sizeof(f));
    For(i,1,n+1) For(j,0,Maxn) g[i][j]=h[i][j]=n+1;
    Rof(l,n,1)
    {
        memcpy(g[l],g[l+1],sizeof(g[l+1]));
        memcpy(gk[l],gk[l+1],sizeof(gk[l+1]));
        f[l][l]=1,g[l][a[l]]=l,gk[l][a[l]]=l;
        For(i,0,Maxn) if(g[l+1][i]<h[l][a[l]^i])
            h[l][a[l]^i]=g[l+1][i],hk[l][a[l]^i]=l;
        For(r,l+1,n)
        {
            For(k,l+1,r) if(f[k][r] && h[l][s[r]^s[k-1]]<k) {f[l][r]=1,fk[l][r]=k; break;}
            if(f[l][r])
            {
                int w=s[r]^s[l-1]; if(g[l][w]>r) g[l][w]=r,gk[l][w]=l;
                For(i,0,Maxn) if(g[r+1][i]<h[l][w^i])
                    h[l][w^i]=g[r+1][i],hk[l][w^i]=r;
            }
        }
    }
    if(!f[1][n]) {printf("Shuiniao\n"); return;}
    printf("Huoyu\n"),Solve(1,n,1);
    cout<<ans.size()<<endl;
    for(auto i:ans) printf("%d %d %d\n",i[0],i[1],i[2]);
    ans.clear();
}

int main()
{
    T=read();
    while(T--) Solve();
    return 0;
}