模拟赛题讲解[17]

来自 yukuai26 2022-08-08 noi.ac #2772

题目描述：

$\text{ysgh}$ 有一个长度为 $m$ 的，元素两两不同的序列。

$\text{emoairx}$ 想要知道这个序列里的元素及其顺序，她用一个神奇的望远镜可以看到序列里的一部分元素及其相对顺序。

他得到了很多组观测数据。

他想要知道这个序列应该是什么样的。

假如存在多组解，输出长度最小的解。

假如还是存在多组解，输出字典序最小的解。

数据保证有解。

输入格式：

第一行一个正整数 $n$，表示有多少组观测数据

接下来 $n$ 行，每行第一个正整数 $k_{i}$ 表示第 $i$ 次观测观测到了多少个数据。

这行接下来 $k_{i}$ 个数描述序列中的 $k_{i}$ 个元素，需要保证原序列中的这几个元素一定要按照该顺序出现

输出格式：

一行若干个正整数，描述长度最小前提下，字典序最小的合法的序列。

输入1：

输出1：

1 2 3 4 6 5

样例解释

诸如 2 1 3 4 6 5、1 2 3 4 6 5 7 也是合法的序列，但是它们长度和字典序不及 1 2 3 4 6 5 优

数据范围：

对于 $60\%$ 的数据，满足 $n\le 10$

另存在 $20\%$ 数据，满足 $k_{i}=2$

对于前 $90\%$ 数据，满足若$\sum k_{i}\le 3\times 10^3$

对于 $100\%$ 的数据，满足 $k_{i}\ge 1,\sum k_{i}\le 3\times 10^5$ 保证读入的元素大小 $\leq 10^6$ , 并且所有读入的数都是正整数

题解：

考虑建图，边 $u \to v$ 表示 $v$ 需要在 $u$ 后面

因为有解，所以图是个DAG

~~什么？DAG？直接topo！~~

因为要求一个字典序最小的拓扑序，因此用一个小根堆来维护

yukuai26： “有一位选手偏不这么干，他偏要倒过来，建反图求字典序最大的。”

yukuai26：“字典序是从前往后比的，不是从后往前比的。”

然后那位选手喜提10pts。~~不愧是我呐QAQ~~

因为字典序是从前往后比较的

所以「反图拓扑序字典序最大」和「原图拓扑序字典序最小」是不等价的！！！

~~结果老师在讲题时忘记了hack是什么~~

然后有一位叫 Gordonlu 的巨佬给出了如下hack Orz

显然答案应该是1 3 4 5 9 2

但是反过来会变成 1 9 2 3 4 5

我只能说，唉，我tcl

时间复杂度 $O(\sum k_i)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(3e5+15)
#define M (int)(1e6+15)

bitset<M> bi;
int n,pos=1,head[M],tmp[N],p[N],in[M],ans[N];
struct Edge{int u,v,next;} e[N];
priority_queue< int,vector<int>,greater<int> > q;
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos; ++in[v];
}
void topo()
{
    sort(p+1,p+1+n);
    for(int i=1; i<=n; i++)
        if(!in[p[i]]) q.push(p[i]);
    int cnt=0;
    while(!q.empty())
    {
        int u=q.top(); q.pop();
        ans[++cnt]=u;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(!(--in[v])) q.push(v);
        }
    }
    for(int i=1; i<=n; i++)
        write(ans[i]),pc(" \n"[i==n]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; read(Q);
    for(int i=1,t; i<=Q; i++)
    {
        read(t);
        for(int j=1; j<=t; j++)
        {
            read(tmp[j]);
            if(!bi[tmp[j]]) bi[tmp[j]]=1,p[++n]=tmp[j];
        }
        for(int j=2; j<=t; j++) addEdge(tmp[j-1],tmp[j]);
    }
    topo();
    return 0;
}