双栈排序

标签：||   min   continue   bool   std   地方   tin   efi   n+1   

感觉有一些地方没有梳理通，需要重新考虑一遍。

一开始的建图，是没有问题的。

对于任意三元组 \((x,y,z)\)，若满足 \(x 且 \(a_x 且 \(a_x>a_z\)，那么 \(x,y\) 之间便有一条之间相连的边。

关键在于我后面的使用非常的 Naive，才导致 WA 掉。

比如对于：

10
10 2 8 1 7 9 3 4 5 6

显然 \(7\) 和 \(9\) 是无法放在同一组的，但 \(8\) 与 \(9\) 也无法放在同一组，此时轮到 \(7\) 时应当塞进第二个栈。

但如何让代码去考虑这类事情？

再次理解一下连边的含义：

一条边 \(x\to y\) 代表的是当 \(y\) 考虑入栈的时候，\(x\) 必定在栈内（具体哪个不清楚），且 \(y\) 不能和 \(x\) 在同一个栈内。

但是间接相连的就没有 必定在栈内 这个性质。

这里是可以直接由 \(9\) 向前面的 \(8\) 和 \(7\) 各连了一条边推断出 \(7\) 和 \(8\) 在同一个栈内。

然后重新考虑一下前面建边的事情，其实是：

找到最右边一个小于自己的位置，然后在这左边的所有大于自己的点都连一条边。

那么考虑两条边 \(x\to y\) 和 \(x\to z(x，由前面的结论可得：若 \(a_y，则必定有边 \(y\to z\)。

\(\cdots\)

二分图染色。

艹，我是 sb。

#include 
#include 
#include 
#define LL long long
using namespace std;
const int N=1e3+3;
inline int min(int x,int y){return x‘9‘||c=‘0‘&&cto[N];
inline void add(int x,int y)
{
    to[x].push_back(y);
    to[y].push_back(x);
    return;
}

int dep[N];
bool vit[N];
bool if_true;
inline void dfs(int now,int fa)
{
    dep[now]=dep[fa]+1;
    vit[now]=true;
    for(int i=to[now].size()-1;i>=0;i--)
    {
        int nxt=to[now][i];
        if(nxt==fa)continue;
        if(dep[nxt])
        {
            if((dep[now]+1-dep[nxt])&1)if_true=true;
            continue;
        }
        dfs(nxt,now);
    }
    return;
}
inline bool cheak()
{
    if_true=false;
    for(int i=1;i=0;i--)
    {
        int nxt=to[now][i];
        if(col[nxt])continue;
        bw(nxt,3-c);
    }
    return;
}

int d_1[N];
int d_2[N];
int t_1,t_2;
int tail=0;
inline void work()
{
    t_1=t_2=0;
    for(int i=1;i=1;i--)s[i]=min(s[i+1],a[i]);
    for(i=1;i

双栈排序

标签：||   min   continue   bool   std   地方   tin   efi   n+1   

原文地址：https://www.cnblogs.com/zjjws/p/14133274.html