【Codeforces】 CF79D Password

题目链接

CF方向
Luogu方向

题目解法

看到区间异或，一个经典的套路是做差分，我们即在 $l$ 处异或一次，在 $r+1$ 处异或一次，然后前缀和起来
于是我们可以将问题转化成：有一个序列初始全 $0$，每次可以把相隔 $a_i$ 的数都 $\oplus 1$，求最少将其变成一个状态的步数
考虑 $k$ 的范围很小，所以为 $1$ 的地方一共只有 $2k$ 个
这里有一个非常重要的 $trick$：在异或操作中，如果需要把 $x,y$ 同时异或 $1$，其他不变，每次可以同时修改相隔 $a_i$ 的位置的异或值，那么这个问题等价于建出图来从 $x$ 到 $y$ 的最短路
然后发现直接状压跑最短路即可，时间复杂度 $O(2^k{k}^2)$
不难优化成 $O(2^{k}k)$，但我直接 $998ms$ 用 $O(2^k{k}^2)$ 的做法艹过去了，就懒得改了
$O(2^k{k}^2)$ 的代码：

#include <bits/stdc++.h>
using namespace std;
const int N=10100,M=2000100;
int n,m,k,a[110],x[30],dis[N];
int f[(1<<20)+100],D[30][30];
int e[M],ne[M],h[N],idx;
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
queue<int> que;
void bfs(int S){memset(dis,0x3f,sizeof(dis));que.push(S),dis[S]=0;while(!que.empty()){int u=que.front();que.pop();for(int i=h[u];~i;i=ne[i]) if(dis[u]+1<dis[e[i]])dis[e[i]]=dis[u]+1,que.push(e[i]);}
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
int main(){n=read(),k=read(),m=read();for(int i=0;i<k;i++) x[i]=read();for(int i=1;i<=m;i++) a[i]=read();for(int i=0;i<k;i++) x[i+k]=x[i]+1;memset(h,-1,sizeof(h));for(int i=1;i<=m;i++)for(int j=1;j<=n-a[i]+1;j++)add(j,j+a[i]),add(j+a[i],j);for(int i=0;i<k<<1;i++){bfs(x[i]);for(int j=0;j<k<<1;j++) D[i][j]=dis[x[j]];}memset(f,0x3f,sizeof(f));f[0]=0;for(int S=0;S<1<<(k<<1);S++)for(int i=0;i<k<<1;i++) if(S>>i&1)for(int j=0;j<k<<1;j++) if(S>>j&1) if(i!=j)f[S]=min(f[S],f[S^(1<<i)^(1<<j)]+D[i][j]);printf("%d\n",f[(1<<(k<<1))-1]>1e9?-1:f[(1<<(k<<1))-1]);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}