题解：P13296 [GCJ 2013 #2] Erdős–Szekeres

dyc2022 · 2025-11-23 08:28:26 · 题解

更好的阅读体验

Update on 2025/11/28：添加了 O(n \log n) 的做法。

注意到，

• 对于 j < i, A_j \ge A_i，则有 X_j > X_i。因为如果 X_j < X_i, A_i \ge A_j + 1，矛盾。
• 对于 j > i, B_j \ge B_i，则有 X_j > X_i。因为如果 X_j < X_i, B_i \ge B_j + 1，矛盾。
• - 由于对于 $j_1 < j_2 < \cdots < j_k, A_{j_1} = A_{j_2} = \cdots = A_{j_k}$，有 $X_{j_1} > X_{j_2} > \cdots > X_{j_k}$，所以记 $lst_i$ 表示最大的 $j$ 使 $A_j = A_i - 1, j < i$，则 $X_i > X_{lst_i}$。
• - 由于对于 $j_1 < j_2 < \cdots < j_k, B_{j_1} = B_{j_2} = \cdots = B_{j_k}$，有 $X_{j_1} < X_{j_2} < \cdots < X_{j_k}$，所以记 $nxt_i$ 表示最小的 $j$ 使 $B_j = B_i - 1, j > i$，则 $X_i > X_{nxt_i}$。

从上面我们可以得到足量的关于 X 的大小关系。

接下来为了找到字典序最小的排列，我们从第一个位置开始填数。假设 sz_i 表示至少有多少个数字比 i 小。则我们就看一下当前没有被选过的第 sz_i 小的数字，填进去即可。

至于怎么求 sz，可以由上面的不等关系建有向边，从大的往小的连边，看一个点可以到达多少个点。

实际上实现的时候可以用把边反着连，然后用 bitset 维护有多少个点可以到达当前点。

然后这道题就做完了。复杂度 O(T n^2)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
int n,num,a[N],b[N],in[N],vis[N],fl[N],getans[N];
vector<int> G[N];
bitset<N> bt[N];
void solve(int Case)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),G[i].clear(),
        in[i]=vis[i]=getans[i]=0,bt[i].reset(),bt[i].set(i);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i]>=a[j])G[j].push_back(i),in[i]++;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(b[i]<=b[j])G[i].push_back(j),in[j]++;
    for(int i=1;i<=n;i++)
        for(int j=i-1;j;j--)
            if(a[j]==a[i]-1){G[j].push_back(i),in[i]++;break;}
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(b[j]==b[i]-1){G[j].push_back(i),in[i]++;break;}
    queue<int> q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    while(q.size())
    {
        int u=q.front(); q.pop();
        for(int v:G[u]){bt[v]|=bt[u];if(!--in[v])q.push(v);}
    }
    printf("Case #%d: ",Case);
    for(int i=1;i<=n;i++)
    {
        int sz=0;
        for(int j=1;j<=n;j++)
            if(bt[i][j]&&!getans[j])sz++;
        int j=0,cnt=0;
        while(cnt<sz)cnt+=!vis[++j];
        printf("%d%c",j," \n"[i==n]),vis[j]=getans[i]=1;
    }
}
main()
{
    int T,_=0; scanf("%lld",&T);
    while(T--)solve(++_); return 0;
}

到这里你可能会说，哥们你这个平方做法还是太菜了！别急，其实可以优化到 O(n \log n)。感谢 @STUDENT0 同学的帮助。

首先第一个瓶颈在于边数。我们把上面的四种情况从上往下标号为 1 \sim 4。显然第 3, 4 种边直接用一个桶就能记录。但其实我们发现，1, 2 种边可以削掉。

首先假如 j < i, A_j = A_i，那么 j 和 i 之间的边我们肯定要留住。但是由于有向边具有传递性，所以我们只需要向比 i 小且离得最近的 j 连边就可以了。

我们还要连 j < i, A_j > A_i 的边。由于我们有 3, 4 类边，也就是我们在相差为 1 的点对之间有连边。由于传递性，我们同样可以构造出任意两个差值之间的边。

所以对于 1, 2 类边，我们只需要找到最靠近的一个相等的位置连边。

第二个瓶颈在于求 DAG 上一个点可以到达的点数目。这个东西看起来不能低于 O(\frac{n^2}{\omega})，所以我们决定另辟蹊径。

我们考虑贪心，把大的数往后放是优的。所以我们可以看一下哪些数现在没有限制，然后取编号最大的，赋予最大的值。

所以我们可以由大的数向小的数连边，然后进行拓扑排序。取目前入度为 0 的点，扔到一个大根堆里面，然后取堆顶，将堆顶的位置赋为 n，然后把这个点删掉，下一个数赋值为 n-1，以此类推。

然后这道题就做完了，复杂度 O(T n \log n)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
int n,num,a[N],b[N],t[N],in[N],ans[N];
vector<int> G[N];
void solve(int Case)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),G[i].clear(),in[i]=t[i]=0;
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;t[a[i]]=i,i++)
        if(t[a[i]])G[t[a[i]]].push_back(i),in[i]++;
    for(int i=1;i<=n;i++)t[i]=0;
    for(int i=n;i;t[b[i]]=i,i--)
        if(t[b[i]])G[t[b[i]]].push_back(i),in[i]++;
    for(int i=1;i<=n;i++)t[i]=0;
    for(int i=1;i<=n;t[a[i]]=i,i++)
        if(t[a[i]-1])G[i].push_back(t[a[i]-1]),in[t[a[i]-1]]++;
    for(int i=1;i<=n;i++)t[i]=0;
    for(int i=n;i;t[b[i]]=i,i--)
        if(t[b[i]-1])G[i].push_back(t[b[i]-1]),in[t[b[i]-1]]++;
    priority_queue<int> q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    int now=n;
    while(q.size())
    {
        int u=q.top(); q.pop(),ans[u]=now--;
        for(int v:G[u])if(!--in[v])q.push(v);
    }
    printf("Case #%d: ",Case);
    for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]);
}
main()
{
    int T,_=0; scanf("%d",&T);
    while(T--)solve(++_);
    return 0;
}