題意：給一個長度為$n$的序列$a$，將其分成$k$段，不能為空，求所有段的異或和之和的最小值。

$n\le 6\times 10^4,a_i<2^{16},k\le 8$

先求個前綴異或和，顯然有個 dp：

$$f(n,k)=\underset{i=k?1}{\overset{n?1}{\min }}\{f(i,k?1)+(a_n\oplus a_i)\}$$

發(fā)現(xiàn)值域很小，可以在跑的時候順便維護前面的每個$a_i=v$的$i$中$f(i,k?1)$的最小值，復雜度$O(nVk)$，就能拿到 60 分的好成績。

考慮優(yōu)化。這個算法是詢問$O(V)$，修改$O(1)$的，在修改的時候暴力預處理所有最小值可以做到詢問$O(1)$，修改$O(V)$，不難想到根號分治。

修改的時候暴力后$8$位，查詢的時候暴力前$8$位，就可以做到$O(\sqrt{V})$

總復雜度$O(kn\sqrt{V})$

我好菜啊……

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN (1<<16)+5 #define MAXM (1<<8)+5 using namespace std; int a[MAXN],f[10][MAXN]; int mn[10][MAXM][MAXM]; int main() {int n,k;scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]^=a[i-1];memset(mn,0x3f,sizeof(mn));memset(f,0x3f,sizeof(f));for (int i=0;i<(1<<8);i++) mn[0][0][i]=i;for (int T=1;T<=k;T++)for (int i=0;i<=n;i++){if (i>=T)for (int S=0;S<(1<<8);S++) f[T][i]=min(f[T][i],mn[T-1][S][a[i]&255]+(((a[i]>>8)^S)<<8));for (int S=0;S<(1<<8);S++)mn[T-1][a[i]>>8][S]=min(mn[T-1][a[i]>>8][S],f[T-1][i]+((a[i]&255)^S));} for (int i=k;i<=n;i++) printf("%d ",f[k][i]);return 0; }

總結

以上是生活随笔為你收集整理的【UOJ549】序列妙妙值【异或】【根号分治】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。