题目
点这里看题目。
分析
这种题目显然需要转化。
考虑我们该怎么枚举区间。由于操作顺序是从前到后的，因此可以想到将一段操作区间拆分成两段操作的后缀。
那么，如何实现操作的 " 减法 " 呢？也就是说，我们应如何消去另一后缀的影响？
注意到，如果我们同时对 (s) 和 (t) 执行操作的话，我们就相当于没操作。因此，如果我们要执行 ([L,R]) 的操作，我们可以对 (s) 执行 ([L,n]) 的操作，对 (t) 执行 ([R+1,n]) 操作。这样 ([R+1,n]) 的操作就相当于被 " 抵消 " 了。
于是，现在可以将问题修改为：
有序列 (a) 和 (b) ，其中 (a_i) 为对 (s) 施加了 ([i,n]) 的操作后的串； (b_i) 为对 (t) 施加了 ([i,n]) 的操作后的串。令 (w(S,T)) 为两串中相同位置的数量。
求出 (max{w(a_i,b_j)|1le i,jle n,|i-j|ge m}) 。
(a) 和 (b) 两个序列都可以 (O(nk)) 预处理出来。
考虑 (a) 和 (b) 相同数位如何计算。设 (p) 为 (a) 中 1 的个数， (q) 为 (b) 中 1 的个数， (r) 为 (a,b) 共同的 1 的个数，那么相同数位的数量就是 ((k-p-q+r)+r=2r+k-p-q) 。由于 (k,p,q) 在一开始就确定了，所以我们只需要最大化 (r) 就好了。
因此我们可以直接枚举最终的 (a_i) 和 (b_j) 的公共的 1 的状态，并求出此时在 (a) 中的最小位置和 (b) 中的最大位置。可以利用 DP ：
其中的 (Asubset B) 表示 (A) 的所有的 1 在 (B) 中都有。这个 DP 可以 (O(2^k imes k)) 地转移出来：
最后我们只需要枚举 (S) ，并且检查 (f(1,S)-f(0,S)) 是否 (ge m) 。如果可以就更新答案。
时间复杂度是 (O(nk+2^k imes k)) 。
小结：
- 利用对两个串同时进行同样操作的方法以 " 抵消 " 操作。
- 将原本复杂、且与两个量相关的答案拆分成只与一个量相关，就可以开始 DP 了。
代码
#include <cstdio>
#define Count __builtin_popcount
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 5, MAXK = 25, MAXS = ( 1 << 20 ) + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &x, _T &y )
{
_T t = x; x = y, y = t;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
int N, M, K;
typedef struct Permutation
{
int p[MAXK] = {};
Permutation()
{
for( int i = 1 ; i <= K ; i ++ )
p[i] = i;
}
int& operator [] ( const int indx ) { return p[indx]; }
}Per;
int f[2][MAXS];
Per suf[MAXN], s, t;
Per operator + ( Per a, Per p )
{
Per ret;
for( int i = 1 ; i <= K ; i ++ )
ret[i] = a[p[i]];
return ret;
}
int Transform( Per num )
{
int ret = 0;
for( int i = 1 ; i <= K ; i ++ )
ret = ret << 1 | num[i];
return ret;
}
int main()
{
read( N ), read( M ), read( K );
for( int i = 1 ; i <= K ; i ++ ) scanf( "%1d", &s[i] );
for( int i = 1 ; i <= K ; i ++ ) scanf( "%1d", &t[i] );
for( int i = 1, a, b ; i <= N ; i ++ )
read( a ), read( b ), suf[i] = Permutation(),
swapp( suf[i][a], suf[i][b] );
suf[N + 1] = Permutation();
for( int i = N ; i ; i -- )
suf[i] = suf[i] + suf[i + 1];
int upper = 1 << K;
for( int S = 0 ; S < upper ; S ++ )
f[0][S] = INF, f[1][S] = -INF;
for( int i = N + 1 ; i ; i -- )
{
int val = Transform( s + suf[i] );
f[0][val] = MIN( f[0][val], i );
val = Transform( t + suf[i] );
f[1][val] = MAX( f[1][val], i );
}
int a = Count( Transform( s ) ),
b = Count( Transform( t ) ),
c, ans = -INF, L, R, val;
for( int S = upper - 1 ; ~ S ; S -- )
{
for( int i = 0 ; i < K ; i ++ )
if( ! ( S >> i & 1 ) )
f[0][S] = MIN( f[0][S], f[0][S | ( 1 << i )] ),
f[1][S] = MAX( f[1][S], f[1][S | ( 1 << i )] );
if( f[1][S] - f[0][S] >= M )
{
c = Count( S );
val = 2 * c - a - b + K;
if( val > ans ) L = f[0][S], R = f[1][S] - 1, ans = val;
}
}
write( ans ), putchar( '
' );
write( L ), putchar( ' ' ), write( R ), putchar( '
' );
return 0;
}