题解：CF2059E2 Stop Gaming (Hard Version)

CReatiQ · 2025-02-04 00:00:15 · 题解

先讲一下题意，赛时一直在写假题。

给你 n 行 m 列矩阵 a_{i,j} 与 b_{i,j}，b 内元素互异。你可以对 a 进行下面的操作：

• 选择某一行，在它的头部插入任意一个数，其它数后推一格，并删去最后一行最后一个数。

下面是一个例子（选择第 1 行，插入 10）：

求使 a \to b 的最小操作次数，并输出一个方案。

最小操作次数等于 n \cdot m 减去保留 a 中元素个数，所以我们要尽可能多地保留 a 中元素。

因为每次删数都是删去矩阵内最后一个数，所以留下的 a 中元素一定是 a 的一个前缀。

再看看 b，b 中的元素要么来自 a，要么来自插入。

如何判断 b 中的某个数能否来自插入？

如果 b 中某个数能来自插入，那它一定曾是 a 某行的开头。

假设它前面来自 a 的元素个数为 pre，它现在在 b 中位于第 x 列，至少应该满足：(x-1)-pre \geq (x-1)\bmod m，即：删去部分前面插入的数足够让它回到这一行的开头。

假如满足上面的条件，一直插入最靠后且满足条件的数就是一个方案，即这个数可以来自插入。发现这是个充要条件。

于是直接将 b 去跟 a 匹配，配上这个元素就来自 a，没配上就考虑能否来自插入，再不能就失配，E1 就做完了。

什么？你说复杂度不对？

别忘了，b 内元素互异。

E2 就是输出这个“一直插入最靠后且满足条件的数”的过程，预处理出每个数插入前提是前面插入多少个数，拍到线段树上模拟就好。

E1

void R()
{
    int n,m;
    cin>>n>>m;
    int N=n*m;
    vector<int> a(N),b(N),c;
    for (int &x:a) cin>>x;
    for (int &x:b) cin>>x;

    auto back=[&](auto &self,int x)->void
    {
        while (x-c.size()<x%m)
        {
            int t=c.back();
            c.pop_back();
            self(self,t);
        }
    };

    for (int i=0;i<N;i++)
    {
        if (b[i]==a[c.size()])
            c.push_back(i);
        else back(back,i);
    }

    cout<<N-c.size()<<'\n';
    return;
}

E2

略去了区间 \min 线段树板子。

void R()
{
    int n,m;
    cin>>n>>m;
    int N=n*m;
    vector<int> a(N),b(N),c,id(2*N+1),vis(2*N+1);
    SGT<Info,Tag> sgt(N);
    for (int i=0;i<N;i++)
    {
        cin>>a[i];
        id[a[i]]=i;
    }
    for (int &x:b) cin>>x;

    auto back=[&](auto &self,int x)->void
    {
        while (x-c.size()<x%m)
        {
            int t=c.back();
            c.pop_back();
            self(self,t);
        }
    };

    for (int i=0;i<N;i++)
    {
        if (b[i]==a[c.size()])
            c.push_back(i);
        else back(back,i);
    }
    for (int p:c) vis[b[p]]=1;
    for (int i=0;i<N;i++)
        if (!vis[b[i]])
        {
            int pre=lower_bound(c.begin(),c.end(),i)-c.begin();
            sgt.modify(i,{(m-pre%m)%m});
        }

    int ans=N-c.size();
    cout<<ans<<'\n';
    for (int i=0;i<ans;i++)
    {
        auto pred=[&](Info x)->bool
        {
            return x.x<=0;
        };

        int pb=sgt.findLast(0,N,pred);
        int pre=lower_bound(c.begin(),c.end(),pb)-c.begin();
        cout<<(pre+(m-pre%m)%m)/m+1<<' '<<b[pb]<<'\n';
        sgt.rangeApply(pb,N,{-1});
        sgt.modify(pb,{inf});
    }
    return;
}