自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 22:51:26，当前版本为作者最后更新于2023-10-18 15:01:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑区间 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;
}