题解：CF1392G Omkar and Pies

缪凌锴_Mathew · 2025-02-09 15:30:47 · 题解

cnblogs

前言

这篇题解复杂度不对，不是正解（大力数据结构）。

解法

称 A_{i,j} 为 A 经过 i\sim j 的操作后的值。

那么 s_{i,j}\oplus t=s_{i,n}\oplus t_{j+1,n}

预处理 S_i=s_{i,n},T_i=t_{i,n}。

枚举 s 的开头 i，相当于求出 \min\limits_{j=i+m}^{n+1} \operatorname{popcount}(S_i\oplus T_j)。

扫描线 i，动态加点查询异或 \operatorname{popcount} 最大值，似乎很难。

rpxleqxq 里面的那个 trie 似乎就可以。

开一棵 1024 叉的 trie（共 2 层），即开一个 1024\times 1024 的数组 tr。

加点 v 的时候修改底层的答案：tr_{\f v,i}\gets\min\Big(tr_{\f v,i},\operatorname{popcount}((\g v)\oplus i)\Big)。

查询 v 的时候遍历顶层：\min_{i=0}^{1023}\Big(tr_{i,\g v}+\operatorname{popcount}(\df v\oplus i)\Big)。

记得再记一个数组记录最大位置（因为要 r-l 最大）

时间复杂度 O(n 2^{\frac k 2}) 了。

算了一下，大概 10^9 左右，但是常数小！！！

加上一些剪枝，相同的 S_i 取最前的，相同的 T_i 取最后的。

修改比查询快，改为 512\times2048 的 trie。

然后就过了？

代码

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=(1<<20)+10;
const int N=1e6;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,m,k,s,t;
int ans=INF,ansl,ansr;
int a[MAXN],b[MAXN];
int p[25];
int S[MAXN],T[MAXN];
int cnt[2048];
int res[512][2048],pos[512][2048];
bool vis[MAXN];
int L,R;
inline void add(int p,int v){
    if(vis[v]){
        return ;
    }
    vis[v]=true;
    int x=v>>11,y=v&(R-1);
    for(int i=0;i<R;i++)
    {
        if(res[x][i]>cnt[i^y]){
            res[x][i]=cnt[i^y];
            pos[x][i]=p;
        }
    }
}
inline int qry(int v){
    int x=v>>11,y=v&(R-1),rsv=INF,rsp=n+1;
    for(int i=0;i<L;i++)
    {
        int val=cnt[x^i]+res[i][y];
        if(rsv>val){
            rsv=val;
            rsp=pos[i][y];
        }
        else if(rsv==val){
            rsp=max(rsp,pos[i][y]);
        }
    }
    return rsp;
}
int fir[MAXN];
inline void solve(){
    scanf("%d%d%d",&n,&m,&k);
    auto read=[&](){
        static char str[MAXN];
        scanf("%s",str);
        int res=0;
        for(int i=0;i<k;i++)
        {
            if(str[i]^'0'){
                res|=1<<i;
            }
        }
        return res;
    };
    s=read();
    t=read();
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        a[i]--;
        b[i]--;
    }
    iota(p,p+k,0);
    S[n+1]=s;
    T[n+1]=t;
    for(int i=n;i;i--)
    {
        swap(p[a[i]],p[b[i]]);
        for(int j=0;j<k;j++)
        {
            if(s&(1<<j)){
                S[i]|=1<<p[j];
            }
            if(t&(1<<j)){
                T[i]|=1<<p[j];
            }
        }
    }
    memset(res,0x3f,sizeof(res));
    L=1<<max(0,k-11);
    R=min(2048,1<<k);
    for(int i=0;i<R;i++)
    {
        cnt[i]=__builtin_popcount(i);
    }
    for(int i=n;i;i--)
    {
        fir[S[i]]=i;
    }
    for(int i=n-m+1;i;i--)
    {
        #define val(j) __builtin_popcount(S[i]^T[j])
        add(i+m,T[i+m]);
        if(fir[S[i]]^i){
            continue;
        }
        int p=qry(S[i]);
        if(val(p)<ans){
            ans=val(p);
            ansl=i;
            ansr=p-1;
        }
        else if(val(p)==ans&&p-i>=ansr-ansl+1){
            ansl=i;
            ansr=p-1;
        }
    }
    printf("%d\n%d %d\n",k-ans,ansl,ansr);
}
signed main(){
    #ifdef LOCAL
    atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
    #endif
    solve();
    return 0;
}