记录编号	612523	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3186.序列异或	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	3.761 s
提交时间	2026-02-13 16:49:52	内存使用	17.83 MiB

#include<bits/stdc++.h>
#define N 10005
#define K 25
#define INF 0x3f3f3f3f
using namespace std;

int n,k,l,m,S[K],a[105],d[N],pos[K],tot,dis[K][K],dp[1<<20];
int b[N],hd[N],nx[N*200],to[N*200],w[N*200],cnt;
void adde(int x,int y,int z){to[++cnt]=y;w[cnt]=z;nx[cnt]=hd[x];hd[x]=cnt;}

queue<int>q;
int vis[N],dist[N];
void bfs(int s,int id){
	memset(vis,0,sizeof(vis));
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;vis[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=hd[u];i;i=nx[i]){
			int v=to[i];
			if(!vis[v]){
				vis[v]=1;
				dist[v]=dist[u]+1;
				q.push(v);
			}
		}
	}
	for(int i=1;i<=tot;i++)dis[id][i]=dist[pos[i]];
}

int main(){
    freopen("z.in","r",stdin);
    freopen("z.out","w",stdout);
	scanf("%d%d%d",&n,&k,&l);
	for(int i=1;i<=k;i++)scanf("%d",&S[i]);
	for(int i=1;i<=l;i++)scanf("%d",&a[i]);
	for(int i=1;i<=k;i++)d[S[i]]^=1;
	for(int i=n+1;i>=1;i--)d[i]^=d[i-1];
	for(int i=1;i<=n+1;i++)if(d[i])pos[++tot]=i;
	if(tot&1){
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=l;i++){
		for(int j=1;j+a[i]<=n+1;j++){
			adde(j,j+a[i],1);
			adde(j+a[i],j,1);
		}
	}
	for(int i=1;i<=tot;i++) bfs(pos[i],i);
	for(int i=1;i<=tot;i++)
		for(int j=1;j<=tot;j++)
			if(dis[i][j]>INF)
                dis[i][j]=INF;
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	int full=(1<<tot)-1;
	for(int mask=0;mask<=full;mask++){
		if(dp[mask]>=INF) continue;
		int p1=-1;
		for(int i=0;i<tot;i++) if(!(mask>>i&1)) {p1=i;break;}
		if(p1==-1) continue;
		for(int p2=p1+1;p2<tot;p2++){
			if(!(mask>>p2&1)){
				int nm=mask|(1<<p1)|(1<<p2);
				int val=dp[mask]+dis[p1+1][p2+1];
				if(val<dp[nm])dp[nm]=val;
			}
		}
	}
	if(dp[full]>=INF)printf("-1\n");
	else printf("%d\n",dp[full]);
	return 0;
}