竞赛讨论区 > 多校(第四场)J题 list打法
头像
Aerix
编辑于 2018-07-29 20:49
+ 关注

多校(第四场)J题 list打法

题解给出了用线段树优化建图的方法,这个方法适用于每个点都与一个连续范围内的点相连这一种情况下的建图。

除了上面这一点,本题所要构造的有向图比较特殊,对于一个点 u, 指向它的点的编号都是从 a[u]%n 开始,到 (u+n-1)%n 结束。换句话说一个点要么入度为 0,要么一定会被它前面一个点指向。
还有,构图的目的只是为了拓扑排序。

我们可以用一个环状链表来维护这一过程,链表中的元素会在它被推送到最终输出队列时被删除,那么,只有在删除了从 a[u]%n 到 (u+n-1)%n 的点之后,才可以删除节点 u。为了使拓扑序的字典序最小,我们需要对现在可以删除的节点用小根堆进行维护。

考虑链表和堆的维护,总体时间复杂度是 O(n log n).

至于具体实现,手写双向环状链表自然最快,也可以用 STL 的 list, 由于是环状的,别忘了特殊处理处于 begin() 和 end() 的情况,实测效率会比手写的慢 50% 左右,但也能通过此题 (938ms) ;也可以设 fa[u] 表示如果 u 已经被删除,它右边最近的一个仍然存在的节点是哪一个,然后用并查集去做,这些都是 O(n) 的维护,最慢的自然是 O(n log n) 的线段树做法。

最后贴上用 list 过的代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <cassert>
using namespace std;

#define aut(a,x) __typeof(x) a=(x)
#define rep(i,o,e) for(int i=(o); i<(e); ++i)
typedef long long LL;

const int N=2e5+5;
struct C{int key; int idx; bool ins;};
list<C> c;
list<C>::iterator s[N];
int ans[N];
int n;

bool hlss(list<C>::iterator p, list<C>::iterator q){
    return p->key > q->key;
}

void xmain(){
    int tac; scanf("%d",&tac);
    rep(tic,0,tac){
        scanf("%d",&n);
        c.clear();
        int zs=0, zlast=0;
        rep(i,0,n){
            C t; scanf("%d",&t.key); t.idx = i; t.ins = false;
            aut(ite, c.insert(c.end(),t));
            if(~t.key){
                ++zlast;
                if(t.key%n==i){
                    s[zs++] = ite;
                    ite->ins = true;
                }
            }
        }
        int zz=0;
        make_heap(s,s+zs,hlss);
        while(zs && zlast){ aut(ite, s[0]); pop_heap(s,s+zs,hlss); --zs;
            ans[zz++] = ite->key; --zlast;
            ite = c.erase(ite);
            if(c.empty())continue;
            if(ite == c.end() || ite == c.begin()){
                if(!c.front().ins && ~c.front().key){
                    int pos = c.front().key%n;
                    if(c.back().idx < pos || pos <= c.front().idx){
                        s[zs++] = c.begin(); c.front().ins = true; push_heap(s,s+zs,hlss);
                    }
                }
            }else{
                if(!ite->ins && ~ite->key){
                    int pos = ite->key%n;
                    aut(pre, ite); --pre;
                    if(pre->idx < pos && pos <= ite->idx){
                        s[zs++] = ite; ite->ins = true; push_heap(s,s+zs,hlss);
                    }
                }
            }
        }
        if(zlast){
            puts("-1");
        }else{
            rep(i,0,zz){
                printf("%d",ans[i]);
                if(i<zz-1)putchar(' ');
            }
            puts("");
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif // LOCAL
    xmain();
    exit(0);
}


全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐