2024.11.05 刷题训练

P7054 NWRRC2015 Graph

构造题，把拓扑序中的队列换成小根堆是最小字典序，此时设置一个大根堆，用于处理连边问题。

设 \(lst\) 是上一个拓扑序中的节点。

1. 小根堆堆顶大于大根堆，当前位置最优解，不耗费连边数量。
2. 小根堆堆顶小于大根堆，若 \(k\) 不为 \(0\) 加入到大根堆中并将 \(k--\)，选择大根堆中的数时，需要从上一个拓扑序中的节点 \(lst\) 连一条有向边到当前点。

证明显然，将序列中靠前的位置放置了可控制范围内最大的数字。

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fi first
#define se second

const int maxn=1e5+5;

int n,m,k;
int ind[maxn],ans[maxn];

vector<int>E[maxn];

vector<pii>edge;

priority_queue<int>q;
priority_queue<int,vector<int>,greater<int>>p;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        ind[v]++;
    }
    for(int i=1;i<=n;i++) if(!ind[i]) p.push(i);
    int lst=0;
    for(int i=1;i<=n;i++)
    {
        while(k&&!p.empty())
        {
            int tmp=-1;
            if(!q.empty()) tmp=q.top();
            if(p.top()>tmp&&p.size()==1) break;
            q.push(p.top());p.pop(),k--;
        }
        int now=0;
        if(!p.empty()) now=p.top(),p.pop();
        else now=q.top(),q.pop(),edge.push_back({lst,now});
        ans[i]=now;
        for(auto v:E[now]) if(!(--ind[v])) p.push(v);
        lst=now;
    }
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    putchar('\n');
    printf("%d\n",(int)edge.size());
    for(auto v:edge) printf("%d %d\n",v.fi,v.se);
}

P7124 Ynoi2008 stcm

又是构造，妙妙题。

把一棵子树的 \(dfn\) 始末看作一条线段，按照线段左端点排序，满足条件时整个序列中除了 \([l,r]\) 中的点都是加入集合的。

考虑分治，当前处理的区间为 \([l,r]\) 时区间 \([1,l-1]\cup [r+1,n]\) 中的点已经加入集合。

求出当前的区间中点 \(mid\)，将所有跨过（包括碰到）\(mid\) 的线段处理出来，由于 \(dfn\) 序良好的性质，先处理上述端点靠左的线段，发现后面处理的线段一定是前一个处理线段的子线段，不断增加集合的数即可实现上述处理。

然后递归至区间 \([l,mid]\) 和 \([mid+1,r]\)。

实现看代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

struct Edge
{
    int tot;
    int head[maxn];
    struct edgenode{int to,nxt;}edge[maxn*2];
    inline void add(int x,int y)
    {
        tot++;
        edge[tot].to=y;
        edge[tot].nxt=head[x];
        head[x]=tot;
    }
}T;

int n,cok;
int dfn[maxn],ed[maxn],fdfn[maxn];

vector<int>vec;

inline void clr()
{
    for(int i=1;i<=n;i++) T.head[i]=dfn[i]=ed[i]=fdfn[i]=0;
    T.tot=cok=0;
    vec.clear();
}
inline void dfs(int u)
{
    ed[u]=dfn[u]=++cok;fdfn[cok]=u;
    vec.push_back(dfn[u]);
    for(int i=T.head[u];i;i=T.edge[i].nxt)
    {
        int v=T.edge[i].to;
        dfs(v);
        ed[u]=ed[v];
    }
}
inline void solve(int l,int r)
{
    vector<int>lv,rv;
    int ld=l-1,rd=r+1,mid=(l+r)>>1,cnt=0;
    for(auto v:vec)
    {
        if(ed[fdfn[v]]<mid) lv.push_back(v);
        else if(v>mid) rv.push_back(v);
        else
        {
            while(ld<v-1) printf("+%d",fdfn[++ld]),cnt++;
            while(rd>ed[fdfn[v]]+1) printf("+%d",fdfn[--rd]),cnt++;
            printf("=%d",fdfn[v]);
        }
    }
    if(l==r) return ;
    for(int i=1;i<=cnt;i++) printf("-");
    if(l==r) return ;
    for(int i=l;i<=mid;i++) printf("+%d",fdfn[i]);
    swap(vec,rv);
    solve(mid+1,r);
    for(int i=l;i<=mid;i++) printf("-");
    for(int i=mid+1;i<=r;i++) printf("+%d",fdfn[i]);
    swap(vec,lv);
    solve(l,mid);
    for(int i=mid+1;i<=r;i++) printf("-");
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        clr();
        for(int i=1;i<n;i++)
        {
            int u;
            scanf("%d",&u);
            T.add(u,i+1);
        }
        dfs(1);
        sort(vec.begin(),vec.end());
        solve(1,n);
        printf("!\n");
    }
}