1392 G. Omkar and Pies

题意:
给定:

1. 长度为\(k(1\le k\le20)\)的字符串\(s\)和\(t\);
2. \(n\)个操作\(\{(a_i,b_i)\}_{i=1}^n(1\le a_i,b_i\le k)\),第\(i\)个操作表示交换第\(a_i\)个字符和第\(b_i\)个字符;
3. 常数\(m(1\le m\le n)\).

求区间\([l,r]\),使得:

1. \(1\le l\le r\le n,r-l+1\ge m\);
2. 对\(s\)依次进行\((a_l,a_l),\cdots,(a_r,b_r)\)的操作后,\(s\)和\(t\)字符相同的位置个数尽可能多.

任意给出一种方案.

题解:
定义\(dist(s,t)=s\)和\(t\)字符不相同的位置个数.
记第\(i\)个操作为\(p_i\),那么就是要最小化\(dist(p_r\cdots p_ls,t)\).
注意到\(dist(s,t)=dist(ps,pt)\),以及\(p_i^2=1\),于是

如果记\(s_i=p_1\cdots p_is,t_i=p_1\cdots p_it\),就相当于要求\(l,r\)使得在\(r-l+1\ge 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)\).
代码

1392 G. Omkar and Pies

原文：https://www.cnblogs.com/Heltion/p/13516957.html