题解 P3943 【星空】

devout

2020-11-30 08:39:09

Solution

[题目链接](https://www.luogu.com.cn/problem/P3943) 因为区间取反不太好做,我们可以考虑把它差分一下,这样一次区间修改相当于转化成了两次单点修改。 因为原来的序列里最多只有 $k\leq 8$ 个 $0$,所以差分之后最多只会有 $16$ 个 $1$,而且显然有偶数个 $1$ 所以可以考虑状压 $dp$,用 $f[S]$ 表示现在已经消除掉的 $1$ 的集合为 $S$ 的最少操作次数。 $$f[S]=\min\limits_{popcount(S\ xor\ S^\prime)=2}\{f[S^\prime]+calc(S^\prime,S)\}$$ 考虑 $calc$ 的计算,我们可以以每一个差分后为 $1$ 的位置为起点做一次 spfa(其实是bfs),然后就可以快速得出 $calc$ 的值了 $\mathcal O(2^{2k}\times(2k)^2)$ ```cpp #include <bits/stdc++.h> using namespace std; # define Rep(i,a,b) for(int i=a;i<=b;i++) # define _Rep(i,a,b) for(int i=a;i>=b;i--) # define RepG(i,u) for(int i=head[u];~i;i=e[i].next) typedef long long ll; const int N=1e5+5; template<typename T> void read(T &x){ x=0;int f=1; char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0'; x*=f; } int n,k,m; int a[N],b[N],p[N],tot; int f[1<<20]; int dis[N][20]; bool inq[N]; void spfa(int s,int op){ queue<int> q; dis[s][op]=0; q.push(s); inq[s]=true; while(!q.empty()){ int u=q.front();q.pop(); inq[u]=false; Rep(i,1,m){ int v=u+b[i]; if(v>n+1)continue; if(dis[v][op]>dis[u][op]+1){ dis[v][op]=dis[u][op]+1; if(!inq[v])inq[v]=true,q.push(v); } } Rep(i,1,m){ int v=u-b[i]; if(v<1)continue; if(dis[v][op]>dis[u][op]+1){ dis[v][op]=dis[u][op]+1; if(!inq[v])inq[v]=true,q.push(v); } } } } int main() { memset(f,0x3f,sizeof(f)); memset(dis,0x3f,sizeof(dis)); read(n),read(k),read(m); Rep(i,1,k){ int x; read(x); a[x]=1; } Rep(i,1,m)read(b[i]); Rep(i,1,n+1)if(a[i]^a[i-1])p[tot++]=i; for(int i=0;i<tot;i++) spfa(p[i],i); f[0]=0; for(int S=0;S<1<<tot;S++) for(int i=0;i<tot;i++) if(S>>i&1^1) for(int j=0;j<tot;j++) if(i!=j&&S>>j&1^1) f[S|(1<<i)|(1<<j)]=min(f[S|(1<<i)|(1<<j)],f[S]+dis[p[j]][i]); printf("%d\n",f[(1<<tot)-1]); return 0; } ```