P9746 合并序列 题解

First Post:

Last Update:

一道很好的区间 DP 题，如果能不那么卡常就更好了。/fn

下文设 表示区间 的异或和，并认为 和值域 同阶。

首先观察这个合并操作在干什么，发现每个时刻，序列中的数其实都对应着原序列的一段区间，这个数的值就是原序列上这段区间的异或和。而一次合并操作，相当于把相邻的若干个区间合并为一个区间。我们不妨建出一棵树，树上一个节点是一个区间，它的儿子是对它进行操作后合并起来的所有区间。树上的所有区间相互包含或不交，这启发我们使用区间 DP 刻画这棵树。

设 表示区间 能否被缩为一个数，转移则枚举 ，如果 都为真，那么 也为真。如何输出方案？我们考虑把那棵树建出来，即由区间 向 连边，输出方案时一边 DFS，一边维护每个原序列中的位置在当前序列中的位置。DFS 时先递归儿子，再做自己代表的操作即可。

上述做法的 DP 是 的。如何优化？

初步想法是设 表示是否存在 使得 为真且 。求 数组时就只需要枚举 和 了。求 数组时，只需让 从 和 转移，再看区间 是否能更新 即可。这样DP 可以做到 。已经能拿到比较可观的分数。

基于此还可以想到设 表示是否存在 满足 ，且 和 均为真。这样，虽然可以 求出 DP 数组，但是 数组本身的维护就是 的。

上述做法更大的问题是，空间复杂度是 的。

我们发现 和 只是在维护可行性而已， 和 的限制又不是很严，这启发我们不去记录对于某个 的可行性，而是直接记录使得 为真的最小的 ！

于是我们重新定义 数组和 数组。设 表示使得原来 为真的最小的 ， 同理。那么，假设我们此时知道一个区间 的 DP 值为真，如何更新 和 ? 我们只需枚举 ，将 与 取 即可。至于 数组，我们枚举 ，用 来更新 即可。

注意在这题中，区间 DP 的转移顺序应该是倒序枚举左端点，然后正序枚举右端点，而非像一般的区间 DP 一样先枚举区间长度。因为本题中 和 的转移依赖于在其右边的 和 ，跟区间长度没有什么关系，所以要用这种顺序保证转移正确。

于是本题就做完了，时间复杂度 ，空间复杂度 。

顺便吐糟一句：不知道出题人放 有什么意义，难道把 出小了还能把 放过去吗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> State;
typedef array<int,3> Ar3;
typedef pair<int,array<int,2> > St2;
typedef unsigned short u16;
#define FI first
#define SE second
#define mkp make_pair
const int N = 5e2 + 5,Sz = 512;
template<typename T> inline void ckmin(T &x,const T &y) { if(y.FI < x.FI) x = y;}
template<typename T> inline void ckmax(T &x,const T &y) { if(x.FI < y.FI) x = y;}
int n,a[N],m;
bool dp[N][N];
u16 rlen[N][N];
u16 xsum[N];
inline int Id(int i,int j) { return (i - 1) * n + j - 1;}
inline pii Revid(int x) { return mkp(x / n + 1,x % n + 1);}
inline u16 Qxor(const u16 &l,const u16 &r) { return xsum[r] ^ xsum[l - 1];}
vector<int> G[N * N];
u16 pos[N];
vector<tuple<u16,u16,u16> > Ans;
void dfs(int x) {
	int L,R;
	std::tie(L,R) = Revid(x);
	if(L == R) return;
	for(auto y : G[x]) dfs(y);
	Ans.emplace_back(pos[Revid(G[x][0]).FI],pos[Revid(G[x][1]).FI],pos[Revid(G[x][2]).FI]);
	for(int i = R + 1;i <= n;i++) pos[i] -= rlen[L][R];
}
pair<u16,u16> pk1[N][Sz];
pair<u16,u16> pk3[N][Sz];
vector<int> usd[N];
inline void Trans(u16 i,u16 j) {
	auto Giv = [&](const u16 &a,const u16 &b,const u16 &c,const u16 &d) {
			G[Id(i,j)].push_back(Id(i,a));
			G[Id(i,j)].push_back(Id(b,c));
			G[Id(i,j)].push_back(Id(d,j));
			rlen[i][j] = b - a - 1 + d - c - 1 + 2;
			dp[i][j] = true;usd[j].push_back(i);
	};
	// for(u16 d = i + 2;d <= j;d++) 
	for(auto d : usd[j])
		if(d >= i && dp[d][j] && pk3[i][Qxor(d,j)].FI < d) {
			u16 a = pk3[i][Qxor(d,j)].SE;
			u16 b,c;std::tie(c,b) = pk1[a+1][Qxor(d,j) ^ Qxor(i,a)];
			Giv(a,b,c,d);
			return;
		}
		
}
inline void Update(u16 st) {
	for(u16 len = 1;len + st - 1 <= n;len++) {
		u16 ed = st + len - 1;
		Trans(st,ed);
		if(dp[st][ed]) {
			u16 val = Qxor(st,ed);
			ckmin(pk1[st][val],mkp(ed,st));
			for(u16 i = 1;i <= st;i++) 
				ckmin(pk1[i][val],mkp(ed,st));
			if(ed < n)
			for(u16 v = 0;v <= m;v++)  
				ckmin(pk3[st][val ^ v],mkp(pk1[ed + 1][v].FI,ed));
			
		}
	}
}

inline void work() {
	cin >> n;m = 0;
	for(u16 i = 1;i <= n;i++) cin >> a[i],xsum[i] = xsum[i - 1] ^ a[i],m = max(m,a[i]);
	m = 1 << __lg(m) + 1;
	for(u16 i = 1;i <= n;i++) usd[i].clear();
	for(u16 i = 1;i <= n;i++) 
		for(u16 j = i;j <= n;j++) 
			dp[i][j] = 0,G[Id(i,j)].clear();
	for(u16 i = 1;i <= n;i++)
		for(u16 v = 0;v <= m;v++)
			pk1[i][v] = mkp(1e9,0),pk3[i][v] = mkp(1e9,0);

	for(u16 i = 1;i <= n;i++) dp[i][i] = 1,usd[i].push_back(i);
	for(u16 i = n;i >= 1;i--) Update(i);
	// cerr << "clock:" << 1.0 * clock() / CLOCKS_PER_SEC << endl;

	if(!dp[1][n]) return puts("Shuiniao"),void();
	puts("Huoyu");
	for(u16 i = 1;i <= n;i++) pos[i] = i;
	Ans.clear();
	dfs(Id(1,n));
	cout << Ans.size() << endl;
	// printf("%d\n",(int)Ans.size());
	for(auto [x,y,z] : Ans)
		cout << x << ' ' << y << ' ' << z << endl;
		// printf("%d %d %d\n",x,y,z);
	cerr << "clock:" << 1.0 * clock() / CLOCKS_PER_SEC << endl;

}
int main() {
	freopen("tmp.in","r",stdin);
	freopen("tmp.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0);cout.tie(0);
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
/*
1
5
68 33 188 32 100

Huoyu
1
1 4 5
*/
≡