UOJ549 序列妙妙值

题意

给出一个长度为 (n) 的序列 (a) ，将序列每个前缀分为非空的 (k) 段，使得每一段的异或和最小，输出 (n-k+1) 个值表示对应前缀的最小值。

$ 1 le k le n le 60000,k le 8,0 le a_i <2^{16}$

传送门

思路

某一段的异或和即为两个前缀异或值异或，令 (a_i) 为前缀异或值

(dp[i]=min{dp[j]+a[i] oplus a[j]})

当 (a_i) 较小时，则我们可以记录前缀异或和为 (a_i) 的最优解，枚举转移。

当 (a_i) 变大时，查询时要枚举 (maxa) 复杂度过大。考虑在修改时先处理出。

考虑当前位置 (j) 对后面位置 (i) 的贡献，令 (b[x][y]) 表示 (a[j]) 的前 (8) 位为 (x) 的数，若 (a[i]) 的后 (8) 位为 (y) 时(dp[j]+a[i] oplus a[j](的后八位)) 的最小值，转移时枚举 (x)，加上前八位的代价即可。

时间复杂度 (O(nk sqrt v))

#include <bits/stdc++.h>
const int N=60005,M=1<<8;
int dp[9][N],b[M][M],n,m,a[N];
int pre(int x){
	return x>>8;
}
int suf(int x){
	return x&((1<<8)-1);
}
int Min(int &x,int y){
	if (y<x) x=y;
}
int main(){
	scanf("%d%d",&n,&m);
	memset(dp,0x3f,sizeof(dp));
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]^=a[i-1],dp[1][i]=a[i];
	} 
	for (int k=2;k<=m;k++){
		int *now=dp[k],*lst=dp[k-1];
		memset(b,0x3f,sizeof(b));
		for (int i=k;i<=n;i++){
			int t1=pre(a[i-1]),t2=suf(a[i-1]);
			for (int j=0;j<1<<8;j++)
				Min(b[t1][j],lst[i-1]+(t2^j));
			int t=pre(a[i])<<8,tt=suf(a[i]);
			for (int j=0;j<1<<8;j++)
				Min(now[i],b[j][tt]+(t^(j<<8)));
		}
	}
	for (int i=m;i<=n;i++) printf("%d ",dp[m][i]);
}

后记

考试的时候，还不知道有分块处理这种东西，于是写了个trie+乱搞，好像也能过掉前十个点拿到97的好成绩。