题目BZOJ3003.题目大意给定一个长度为n nn序列a i a_iai​与给定m mm种操作a i a_iai​初始全为0 00每种操作给定一个长度表示可以对这个长度的区间取反.现在要你用一定次数的操作把整个序列变成只有k kk个位置为1 11其余全为0 00求最少操作数.数据组数T ≤ 10 T\leq 10T≤101 ≤ n ≤ 1 0 4 , 1 ≤ m ≤ 100 , 1 ≤ k ≤ 10 1\leq n\leq 10^4,1\leq m\leq 100,1\leq k\leq 101≤n≤104,1≤m≤100,1≤k≤10.对于这种区间染色的题我们发现区间染色的操作非常麻烦所以考虑把操作和序列都进行异或差分现在操作变成相隔一定长度的两个位置取反同时最终的序列变成了最多2 k 2k2k个位置为1 11.之后考虑把问题变为从终态到初态的最少步数然后状压DP.设f [ S ] f[S]f[S]表示集合S SS中的位置为1 11其它位置为0 00需要的最少步数那么可以列出转移f [ S ] min ⁡ i , j ∉ S { f [ S ∪ { i , j } ] g ( i , j ) } f[S]\min_{i,j\notin S}\{f[S\cup\{i,j\}]g(i,j)\}f[S]i,j∈/​Smin​{f[S∪{i,j}]g(i,j)}其中g ( i , j ) g(i,j)g(i,j)表示把位置i ii和位置j jj同时消掉需要的最少步数但是这个东西并不好求.考虑若当前用长度为l e n 1 len_1len1​的操作消掉了位置i ii则位置i l e n 1 ilen_1ilen1​会变为1 11之后用长度为l e n 2 len_2len2​的操作消掉位置i l e n 1 ilen_1ilen1​则位置i l e n 1 ilen_1ilen1​会变为0 00且i l e n 1 l e n 2 ilen_1len_2ilen1​len2​变为1 11…我们会发现上述过程类似于一个最短路对于每一个位置i ii和每一个区间长度j jj则将位置i ii和i j , i − j ij,i-jij,i−j两个位置连接起来跑个最短路就完事了.一个小优化容易发现每次转移的时候位置( i , j ) (i,j)(i,j)中有一个位置是可以钦定而不枚举的这样就可以少O ( k ) O(k)O(k)的时间复杂度了.时间复杂度O ( T ( n m 2 2 k k ) ) O(T(nm2^{2k}k))O(T(nm22kk)).代码如下#includebits/stdc.husing namespace std;#defineAbigail inline voidtypedeflonglongLL;constintN10000,M100,K10,INF(130)-1;intnum[(1K*2)9];voidGet_num(){for(inti0;iK*2;i)num[1i]i;}intn,m,sk,a[N9],len[M9];intp[K*29],cp;voidGet_p(){cp0;for(inti1;in;i)if(a[i])p[cp]i;}structside{inty,next;}e[N*M*29];intlin[N9],cs;voidIns(intx,inty){e[cs].yy;e[cs].nextlin[x];lin[x]cs;}voidIns2(intx,inty){Ins(x,y);Ins(y,x);}voidGet_graph(){for(inti1;in;i)lin[i]0;cs0;for(inti1;im;i)for(intj1;jn;j){if(j-len[i]1)Ins(j,j-len[i]);if(jlen[i]n)Ins(j,jlen[i]);}}queueintq;intdis[K*29][N9],vis[N9];voidBfs_dis(intid,intst){for(inti1;in;i)dis[id][i]INF,vis[i]0;dis[id][st]0;vis[st]1;q.push(st);for(;!q.empty();){inttq.front();q.pop();for(intilin[t];i;ie[i].next)if(!vis[e[i].y]){dis[id][e[i].y]dis[id][t]1;vis[e[i].y]1;q.push(e[i].y);}}dis[id][st]INF;}intdp[(1K*2)9];voidGet_dp(){for(intg0;g1cp;g)dp[g]INF;dp[(1cp)-1]0;for(intg(1cp)-1;g0;--g){if(dp[g]INF)continue;intt0g-g;if(g-t00)continue;for(intig-t0;i;i-i-i){intt1i-i;dp[g^t0^t1]min(dp[g^t0^t1],dp[g]dis[num[t0]1][p[num[t1]1]]);}}}Abigailstart(){Get_num();}Abigailinto(){scanf(%d%d%d,n,sk,m);n;for(inti1;in;i)a[i]vis[i]0;for(inti1;isk;i){intx;scanf(%d,x);if(vis[x])continue;vis[x]1;a[x]^1,a[x1]^1;}for(inti1;im;i)scanf(%d,len[i]);}Abigailwork(){Get_p();Get_graph();for(inti1;icp;i)Bfs_dis(i,p[i]);Get_dp();}Abigailouto(){printf(%d\n,dp[0]INF?-1:dp[0]);}intmain(){intT;start();scanf(%d,T);while(T--){into();work();outo();}return0;}