P16540 [EGOI 2026] 披萨大师 / Ovenmasters 題解

· · 题解

先思考一下加入披薩的過程怎麼刻畫，你把所有當前“上桌披薩”編號放在一個數軸上面，那麼加入披薩就是刪除我這個位置的上一個“上桌披薩”，然後加入我這個披薩。

那麼那些無法取代任何人的披薩呢？顯然他們就是不存在上一個“上桌披薩”的披薩，大概就是在數軸的最左邊，我們先不管他們。

我們有一個很有意思的觀察：根據上面的過程，每個桌子的披薩編號大小關係是不變的。

於是我們刻畫出每個桌子可以按照題目給出的披薩順序向後推進的條件：我下一個披薩的編號不大於數軸上我後面的“上桌披薩”的編號。

我們只需要交替推進所有的數組就可以求得解。而且推進這個事情，我們不會因為某一次推進就從有解就變成無解（非常顯然），所以我們只需要找最小的可以推進的數組就行。

然後我們發現所有沒能上桌的披薩可以刻畫成一個新的桌子，初始位置在 -1，然後也按上面的流程慢慢推進即可。

不斷 Check 可以得到一個 \mathcal O(nm) 的做法，但這顯然過不了。

那咋辦？

有個敏銳的觀察，如果一個數組由於後面數組當前的位置推進到不能再推進了，那下一次能推進顯然要在後面數組推進一次之後。

於是我們發現推進的過程可以理解為一個“連鎖反應”：

這樣就是 \mathcal O(n+m) 的了。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,Hav[N],Len[N],T[N];
vector<int>V[N],Ans;
void Dfs(int x)
{
    while(T[x]!=Len[x]-1)
    {
        if(x!=m&&V[x][T[x]+1]>V[x+1][T[x+1]])return;
        T[x]++;
        Ans.push_back(V[x][T[x]]);
        if(x!=0)Dfs(x-1);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1,L;i<=m;i++)
    {
        cin>>Len[i];
        V[i].resize(Len[i]);
        for(int j=0;j<Len[i];j++)
        {
            cin>>V[i][j];
            Hav[V[i][j]]=1;
            if(j)if(V[i][j-1]>V[i][j])return cout<<"NO"<<endl,0;
        }
    }
    V[0].push_back(-1);
    for(int i=0;i<n;i++)if(!Hav[i])V[0].push_back(i);
    for(int i=1;i<=m;i++)Ans.push_back(V[i][0]);
    sort(V+1,V+m+1,[](const vector<int>&A,const vector<int>&B){
        return A[0]<B[0];   
    });
    for(int i=0;i<=m;i++)Len[i]=V[i].size();
    for(int i=0;i<=m;i++)Dfs(i);
    for(int i=0;i<=m;i++)if(T[i]!=Len[i]-1)return cout<<"NO"<<endl,0;
    cout<<"YES"<<endl;
    for(int i:Ans)cout<<i<<' ';
}