2024.11.05 刷题训练
P7054 NWRRC2015 Graph
构造题，把拓扑序中的队列换成小根堆是最小字典序，此时设置一个大根堆，用于处理连边问题。
设 \(lst\) 是上一个拓扑序中的节点。
- 小根堆堆顶大于大根堆，当前位置最优解，不耗费连边数量。
- 小根堆堆顶小于大根堆，若 \(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");
}
}