[CF1392G] Omkar and Pies

· · 题解

还是记一下这个 trick 吧，虽然很简单但是我认为十分有趣！本质上是 Maximize the Difference 做法的扩展。（似乎有人称作 RainFestivalTree？？？）

这个题经过一些简单转化可以转化为这样一个问题：给定有二进制数序列 A,B，求 \max_{r-l\ge m} |A_l\oplus B_r|（|x| 即二进制位下一的个数，\oplus 是异或）。

由于这个题有特殊性质，即序列 A,B 中所有元素的 popcount 都相等，所以我们只关注 |A_l\cap B_r|，所以绝大多数题解给出了一个基于普通高维后缀和的 O(k2^k)。

但是假设序列 A,B 没有任何特殊性质，这个题仍然可以做！我们考虑到异或信息也是可以 FWT 的，我们给 FWT 数组再开一维记录 popcount，合并的时候更新一下，就扩展到了序列任意的情况。这也是环一周和叉老师在模拟赛场上的写法，复杂度为 O(2^kk^2)，空间复杂度 O(2^kk)。

那我场上又写了个啥抽象玩意呢？事实上，对于上面这个问题，我们可以做到在线维护！

这个做法的基本思想是对于一般的 FWT 问题，假设你要增量维护其结果，你可以暴力 dfs 子集/超集，遇到已经访问了的就回退，这样每个集合只会被增广一次。

那么对于此题中的多带了一维的异或 FWT，其也可以施加暴力 dfs 的技巧。具体地，我们增量维护一个集合 S，并记录 f 数组表示对于所有长为 k 数到 S 中数的最小汉明距离，即 f_x=\min_{y\in S} |x\oplus y|。

每次往 S 加入一个元素 x 时，我们暴力 dfs 这个元素的邻域，如果当前元素 y 到 x 的距离不小于 f_y 就直接返回。这样，对于每一个元素，其 f 只会至多被更新 O(k) 次，每次更新至多耗费 O(k) 的时间复杂度。总时间复杂度也是 O(2^kk^2)，但空间做到了 O(2^k) 且可以强制在线。

如果到当前元素汉明距离比当前答案还大的话还可以剪枝，数据基本不可能卡满而且除了一堆常数，所以事实上这个算法竟然能跑过一大堆 O(2^kk)。

#include <cstdio>
using namespace std;
int read(){
    char c=getchar();int x=0;
    while(c<48||c>57) c=getchar();
    do x=x*10+(c^48),c=getchar();
    while(c>=48&&c<=57);
    return x;
}
const int N=10000003,K=20,INF=0x3f3f3f3f;
int n,m,k,o;
int res=INF,ix=-1,iy=-1;
int f[1<<K],ps[1<<K];
bool vis[1<<K];
int px[N],py[N],p[N];
int A[N],B[N];
void dfs(int s,int d,int lim){
    if(d>=res||f[s]<=d) return;
    f[s]=d;
    if(ps[s]>=o+m) res=d,ix=o,iy=ps[s];
    for(int i=lim;i<k;++i) dfs(s^(1<<i),d+1,i+1);
}
int main(){
    n=read();m=read();k=read();
    char cc=getchar();
    while(cc!='0'&&cc!='1') cc=getchar();
    for(int i=0;i<k;++i){
        if(cc=='1') A[n+1]|=(1<<i);
        cc=getchar();
    }
    while(cc!='0'&&cc!='1') cc=getchar();
    for(int i=0;i<k;++i){
        if(cc=='1') B[n+1]|=(1<<i);
        cc=getchar();
    }
    for(int i=0;i<k;++i) p[i]=i;
    for(int i=1;i<=n;++i) px[i]=read()-1,py[i]=read()-1;
    for(int i=n;i;--i){
        int X=p[px[i]],Y=p[py[i]];
        p[px[i]]=Y;p[py[i]]=X;
        px[i]=X;py[i]=Y;
    }
    for(int i=n;i;--i){
        A[i]=A[i+1];B[i]=B[i+1];
        if(((A[i]>>px[i])^(A[i]>>py[i]))&1) A[i]^=(1<<px[i])^(1<<py[i]);
        if(((B[i]>>px[i])^(B[i]>>py[i]))&1) B[i]^=(1<<px[i])^(1<<py[i]);
    }
    for(int i=1;i<=n+1;++i) ps[B[i]]=i;
    for(int s=0;s<(1<<k);++s) f[s]=INF;
    for(o=1;o<=n+1;++o) dfs(A[o],0,0);
    printf("%d\n%d %d\n",k-res,ix,iy-1);
    return 0;
}