题意:
给定:
- 长度为(k(1le kle20))的字符串(s)和(t);
- (n)个操作({(a_i,b_i)}_{i=1}^n(1le a_i,b_ile k)),第(i)个操作表示交换第(a_i)个字符和第(b_i)个字符;
- 常数(m(1le mle n)).
求区间([l,r]),使得:
- (1le lle rle n,r-l+1ge m);
- 对(s)依次进行((a_l,a_l),cdots,(a_r,b_r))的操作后,(s)和(t)字符相同的位置个数尽可能多.
任意给出一种方案.
题解:
定义(dist(s,t)=s)和(t)字符不相同的位置个数.
记第(i)个操作为(p_i),那么就是要最小化(dist(p_rcdots p_ls,t)).
注意到(dist(s,t)=dist(ps,pt)),以及(p_i^2=1),于是
[dist(p_rcdots p_ls,t)
\=dist(p_lcdots p_rp_rcdots p_ls,p_lcdots p_rt)
\=dist(s,p_lcdots p_rt)
\=dist(p_1cdots p_{l-1}s,p_1cdots p_rt).]
如果记(s_i=p_1cdots p_is,t_i=p_1cdots p_it),就相当于要求(l,r)使得在(r-l+1ge m)的条件下(dist(s_{l-1},t_{r}))最小.
计算所有(s_i,t_i)的复杂度是(O(nk)).
构建无向图(G={V,E},V={0,cdots,2^k-1},E={(u,v):u)和(v)二进制有一位不相同(}).
枚举(i)从(0)到(n-m),进行如下操作:每次标记顶点(s_i),求(t_{i+m})到图中已标记点最短距离.
每次以(s_i)为起点做BFS,由于每个顶点最短距离只会被更新(O(k))次,因此复杂度不超过(O(k^22^k))(仅为粗略估计,也有可能是(O(k2^k))).
因此总的复杂度为(O(nk+k^22^k)),空间复杂度为(O(nk+2^k)).
代码