经典区间dp+预处理
不难设计状态 \(f_{l,r}\) 表示 \([l,r]\) 能否变为一个数,转移也简单,枚举三个区间,满足 \(f_{i,a}=f_{b,c}=f_{d,r}=1\) 且异或和为 \(0\)。复杂度为 \(O(n^6)\)。
设异或和为 \(s_{l,r}\)。
考虑优化,瓶颈在于转移需要枚举三个区间。假如只枚举一个右区间 \([d,r]\),那么我们只需要判断 \([l,d-1]\) 中是否存在两个区间能缩成一个数且两区间异或和为 \(s_{d,r}\) 就可以转移。
直接设 \(h_{i,j}\) 表示满足 \(i\le a\le b\le c\) 且 \(s_{i,a}\oplus s_{b,c}=j\) 的最小 \(c\) 值。但发现还是不好预处理出来,不好找到 \([b,c]\) 区间。再设 \(g_{i,j}\) 表示满足 \(i\le a\le b\) 且 \(s_{a,b}=j\) 且 \(f_{a,b}=1\) 的最小 \(c\) 值,\(g\) 容易转移,而 \(h\) 只需要枚举 \(a\) 即可,\(h_{i,s_{i,a}\oplus j}=\min g_{a+1,j}\ (f_{i,a}=1)\)。
\(f\) 转移变为存在 \(l\le d\le r\),满足 \(h_{i,s_{d,r}}<d\) 。单次复杂度为 \(O(n^2A)\),注意当前 \(f_{l,r}\) 为 \(1\) 后可以直接 break。
\(h\) 数组和 \(g\) 数组的转移在区间 dp 时更新即可。值得注意的是,在这题中,区间 dp 的顺序只能是左端点 \(l\) 从右向左枚举,右端点 \(r\) 从 \(l\) 向 \(n\) 枚举,因为 \(h\) 数组和 \(g\) 数组的更新需要之前所有长度的 \(f_{l,r}\),如果只按长度更新会出现错误,如枚举 \(l=a=1\) 时,若按长度枚举,无法转移到 \(g_{a+1,j}\) 长度大于 \(1\) 时的区间。
对于输出方案,除了记录每个区间的前继,还需要记录 \(h\) 和 \(g\) 数组转移时的其中一个合法方案,对于编号的改变,这个体现在 dfs 中。这个输出方案还是比较重要的。
void print(int l, int r, int id) {
if(l == r || l == 0) return;
int d = pre[l][r], a = hl[l][sum[r] ^ sum[d - 1]];
int now = sum[a] ^ sum[l - 1] ^ sum[r] ^ sum[d - 1];
int b = gl[a + 1][now], c = g[a + 1][now];
print(d, r, id + (d - l)), print(b, c, id + (b - l)), print(l, a, id);
ans.push_back({id, id + (b - l) - (a - l), id + (d - l) - (a - l) - (c - b)});
}
对于 \(h\) 和 \(g\) 出现的动机还是挺明确的,一个是优化需要,一个注意到 \(a_i\) 的大小,就知道可以把它放进状态里了。转移需要注意。
标签:le,06,int,sum,KDOI,枚举,P9746,区间,id From: https://www.cnblogs.com/FireRaku/p/18091652