Codeforces Global Round 10 G. Omkar and Pies（SOS DP，状压）

Omkar has a pie tray with 푘 (2≤푘≤20) spots. Each spot in the tray contains either a chocolate pie or a pumpkin pie. However, Omkar does not like the way that the pies are currently arranged, and has another ideal arrangement that he would prefer instead.

To assist Omkar, 푛 elves have gathered in a line to swap the pies in Omkar’s tray. The 푗-th elf from the left is able to swap the pies at positions 푎푗 and 푏푗 in the tray.

In order to get as close to his ideal arrangement as possible, Omkar may choose a contiguous subsegment of the elves and then pass his pie tray through the subsegment starting from the left. However, since the elves have gone to so much effort to gather in a line, they request that Omkar’s chosen segment contain at least 푚 (1≤푚≤푛) elves.

Formally, Omkar may choose two integers 푙 and 푟 satisfying 1≤푙≤푟≤푛 and 푟−푙+1≥푚 so that first the pies in positions 푎푙 and 푏푙 will be swapped, then the pies in positions 푎푙+1 and 푏푙+1 will be swapped, etc. until finally the pies in positions 푎푟 and 푏푟 are swapped.

Help Omkar choose a segment of elves such that the amount of positions in Omkar’s final arrangement that contain the same type of pie as in his ideal arrangement is the maximum possible. Note that since Omkar has a big imagination, it might be that the amounts of each type of pie in his original arrangement and in his ideal arrangement do not match.

Input
The first line contains three integers 푛, 푚, and 푘 (1≤푚≤푛≤106 and 2≤푘≤20) — the number of elves, the minimum subsegment length, and the number of spots in Omkar’s tray respectively.

The second and third lines each contain a string of length 푘 consisting of 0s and 1s that represent initial arrangement of pies and ideal arrangement of pies; the 푗-th character in each string is equal to 0 if the 푗-th spot in the arrangement contains a chocolate pie and is equal to 1 if the 푗-th spot in the arrangement contains a pumpkin pie. It is not guaranteed that the two strings have the same amount of 0s or the same amount of 1s.

푛 lines follow. The 푗-th of these lines contains two integers 푎푗 and 푏푗 (1≤푎푗,푏푗≤푘, 푎푗≠푏푗) which indicate that the 푗-th elf from the left can swap the pies at positions 푎푗 and 푏푗 in the tray.

Output
Output two lines.

The first line should contain a single integer 푠 (0≤푠≤푘) equal to the amount of positions that contain the same type of pie in Omkar’s final arrangement and in Omkar’s ideal arrangement; 푠 should be the maximum possible.

The second line should contain two integers 푙 and 푟 satisfying 1≤푙≤푟≤푛 and 푟−푙+1≥푚, indicating that Omkar should pass his tray through the subsegment 푙,푙+1,…,푟 to achieve a final arrangement with 푠 positions having the same type of pie as his ideal arrangement.

If there are multiple answers you may output any of them.

Examples
inputCopy
4 2 5
11000
00011
1 3
3 5
4 2
3 4
outputCopy
5
1 3
inputCopy
4 3 5
11000
00011
1 3
1 5
2 4
1 5
outputCopy
3
1 4
Note
In the first test case, the swaps will go like this:

Swap 1 and 3: 11000 becomes 01100
Swap 3 and 5: 01100 becomes 01001
Swap 4 and 2: 01001 becomes 00011
The final arrangement is the same as the ideal arrangement 00011, so there are 5 positions with the same type of pie, which is optimal.
In the second test case, the swaps will go like this:

Swap 1 and 3: 11000 becomes 01100
Swap 1 and 5: 01100 becomes 01100
Swap 4 and 2: 01100 becomes 00110
Swap 1 and 5: 00110 becomes 00110
The final arrangement has 3 positions with the same type of pie as the ideal arrangement 00011, those being positions 1, 2, and 4. In this case the subsegment of elves (푙,푟)=(2,3) is more optimal, but that subsegment is only length 2 and therefore does not satisfy the constraint that the subsegment be of length at least 푚=3.

参考题解

题意：
两个序列s,t。
然后一堆对s序列的交换操作。要求取连续且至少为m个的交换操作，使得s序列和t序列相同位置相同值个数最多。

思路：
通过本题学习了一下SOS DP，实际就是高效算二进制子集前缀和的算法。

本题需要找一段$(l,r)$交换操作，而我们只关心交换完了以后$s$序列和$t$序列的相似度。所以可以假设是将$s$序列按照$(1,l-1)$的操作进行交换，将$t$按照$(1,r)$的部分进行交换。这时候再算$s$和$t$的相似度，就等价于$s$按照$(l,r)$交换和$t$。

那么可以定义通过$(1,x)$操作$dp[0][i]$为将$s$序列交换成$s^{\prime }$，且$i\in s^{\prime }$的最小$x$。
通过$(1,y)$操作$dp[1][i]$为将$t$序列交换成$t^{\prime }$，且$i\in t^{\prime }$的最大$y$。

那么只要满足$dp[1][i]-dp[0][i]\ge m$，就说明这个序列可以被选择，且最后$s$和$t$的相似部分就是$i$，只要算出$i$中的1，就可以知道相似度大小，为$k-(o1+o2-num(i))$，$o1,o2$为$s,t$中1的个数。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 21;
const int INF = 0x3f3f3f3f;

int n,m,k;

int p[maxn],dp[2][1 << maxn];
char s[maxn],t[maxn];

void get(int &x,int &y) {
    x = y = 0;
    for(int i = 0;i < k;i++) {
        if(s[i] == '1') x |= 1 << p[i];
        if(t[i] == '1') y |= 1 << p[i];
    }
}

int num(int x) {
    int cnt = 0;
    while(x) {
        cnt++;
        x &= (x - 1);
    }
    return cnt;
}

int main() {
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",s,t);
    int o1 = 0,o2 = 0;
    for(int i = 0;i < k;i++) {
        p[i] = i;
        o1 += (s[i] == '1');
        o2 += (t[i] == '1');
    }
    
    memset(dp[0],INF,sizeof(dp[0]));
    memset(dp[1],0,sizeof(dp[1]));
    
    int x = 0,y = 0;
    get(x,y);
    dp[0][x] = 0;dp[1][y] = 0;
    
    for(int i = 1;i <= n;i++) {
        int a,b;scanf("%d%d",&a,&b);
        a--;b--;swap(p[a],p[b]);
        get(x,y);
        dp[0][x] = min(dp[0][x],i);
        dp[1][y] = max(dp[1][y],i);
    }
    
    int ans = 0,ansl = 1,ansr = 1;
    for(int i = (1 << k) - 1;i >= 0;i--) {
        int tmp = k - (o1 + o2 - 2 * num(i));
        if(dp[1][i] - dp[0][i] >= m) {
            if(ans < tmp) {
                ans = tmp;
                ansl = dp[0][i] + 1;
                ansr = dp[1][i];
            }
        }
        for(int j = 0;j < k;j++) {
            if((i >> j) & 1) {
                dp[0][i ^ (1 << j)] = min(dp[0][i ^ (1 << j)],dp[0][i]);
                dp[1][i ^ (1 << j)] = max(dp[1][i ^ (1 << j)],dp[1][i]);
            }
        }
    }
    
    printf("%d\n",ans);
    printf("%d %d\n",ansl,ansr);
    return 0;
}