挺巧妙的题

看起来无从下手

k很小，先不管

把最终需要亮的看做1，不需要的看做0

要把全0序列，变成有至多10个1的01序列

不妨考虑把01序列变回全0序列（这样容易思考）

区间取反？

差分变成两个单点取反！

特殊加入n+1位置，这样便于取反

 

首先，两个0取反一定不优，可以用01取反和11取反来得到相同的效果

01取反，等价于1走到0,11取反，等价于两个1消掉。

不断两个位置进行取反，一定是为了最后把两个1消掉！

也就是，其实是两个1的匹配！

 

1一共只有20个

最短路建图，f[i][j]表示i和j匹配的最小代价，也即最短路

一个问题是：不会影响其他位置的值吗？

发现这个最短路的边，除了起点终点，都恰好xor两次（虽然这样并不优）！不会影响其他的位置的值！

BFS求最短路

然后Dp即可

枚举和S的lowbit进行匹配的点

O(20*2^20)

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=10000+5;const int M=105;const int K=22;const int inf=0x3f3f3f3f;int n,k,m;int pos[K],dis[N],cnt;int f[K][K];int a[N],b[N];int dp[(1<<20)+23];int q[N],l,r;void bfs(int st){ memset(dis,0x3f,sizeof dis); dis[pos[st]]=0; l=1,r=0; q[++r]=pos[st]; while(l<=r){ int x=q[l++]; for(reg i=1;i<=m;++i){ int to=x+b[i]; if(to<=n+1&&dis[to]>dis[x]+1){ dis[to]=dis[x]+1; q[++r]=to; } to=x-b[i]; if(to>0&&dis[to]>dis[x]+1){ dis[to]=dis[x]+1; q[++r]=to; } } } for(reg i=1;i<=cnt;++i){ f[st][i]=dis[pos[i]]; }}int num(int p){ int sz=__builtin_ctz(p); return sz+1;}int main(){ rd(n);rd(k);rd(m); for(reg i=1;i<=k;++i){ int x;rd(x); a[x]=1; } for(reg i=1;i<=m;++i){ rd(b[i]); } for(reg i=n+1;i>=1;--i){ a[i]^=a[i-1]; if(a[i]==1) pos[++cnt]=i; } // prt(a,1,n+1); // prt(pos,1,cnt); for(reg i=1;i<=cnt;++i){ // cout<<" bfs i------------ "<
           <