广告设计网站排行榜前十名,做网站的语言有哪些,wordpress超级留言板,做家常菜的网站哪个好题意#xff1a;给一个长度为nnn的序列aaa#xff0c;将其分成kkk段#xff0c;不能为空#xff0c;求所有段的异或和之和的最小值。 n≤6104,ai216,k≤8n\leq 6\times 10^4,a_i 2^{16},k\leq 8n≤6104,ai216,k≤8
先求个前缀异或和#xff0c;显然有个 dp…题意给一个长度为nnn的序列aaa将其分成kkk段不能为空求所有段的异或和之和的最小值。
n≤6×104,ai216,k≤8n\leq 6\times 10^4,a_i 2^{16},k\leq 8n≤6×104,ai216,k≤8
先求个前缀异或和显然有个 dp
f(n,k)minik−1n−1{f(i,k−1)(an⊕ai)}f(n,k)\min_{ik-1}^{n-1}\{f(i,k-1)(a_n\oplus a_i)\}f(n,k)ik−1minn−1{f(i,k−1)(an⊕ai)}
发现值域很小可以在跑的时候顺便维护前面的每个aiva_ivaiv的iii中f(i,k−1)f(i,k-1)f(i,k−1)的最小值复杂度O(nVk)O(nVk)O(nVk)就能拿到 60 分的好成绩。
考虑优化。这个算法是询问O(V)O(V)O(V)修改O(1)O(1)O(1)的在修改的时候暴力预处理所有最小值可以做到询问O(1)O(1)O(1)修改O(V)O(V)O(V)不难想到根号分治。
修改的时候暴力后888位查询的时候暴力前888位就可以做到O(V)O(\sqrt V)O(V)
总复杂度O(knV)O(kn\sqrt V)O(knV)
我好菜啊……
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN (116)5
#define MAXM (18)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 i1;in;i) scanf(%d,a[i]),a[i]^a[i-1];memset(mn,0x3f,sizeof(mn));memset(f,0x3f,sizeof(f));for (int i0;i(18);i) mn[0][0][i]i;for (int T1;Tk;T)for (int i0;in;i){if (iT)for (int S0;S(18);S) f[T][i]min(f[T][i],mn[T-1][S][a[i]255](((a[i]8)^S)8));for (int S0;S(18);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 ik;in;i) printf(%d ,f[k][i]);return 0;
}
