首页 > 其他分享 >CF1967D Long Way to be Non-decreasing 题解

CF1967D Long Way to be Non-decreasing 题解

时间：2024-05-12 20:41:21浏览次数：19  
标签：Non return get int 题解 head Long siz define

CF1967D Long Way to be Non-decreasing 题解

知识点

二分答案，基环树。

题意分析

给定一个包含 \(n\) 个元素的数组 \(\{ a_i \}\) 和一个 \(m\) 个元素的数组 \(\{ b_i \}\)。

定义每次操作为：在 \(\{ a_i \}\) 中选择任意个数，假设某个选的数为 \(a_i\)，那么将其变为 \(b_{a_i}\)。

问使 \(\{ a_i \}\) 变为单调不降的最少操作次数。

思路分析

看到“最少”这个词语就应该考虑二分答案，再看性质，它明显满足单调性，那就是二分答案无疑了。

那么考虑二分的检验过程：

设现在二分的次数为 \(x\)，一开始的 \(mx=m\)。

我们可以从最后一个开始检验，如果不能到 \(mx\) 或到 \(mx\) 的距离大于 \(x\)，就将 \(mx\) 减一，再继续重复，做一个尺取操作，如果 \(mx\) 有降到 \(0\) 及以下，就说明不合法。

我们现在再考虑如何求距离。

明显，如果我们建图，生成 \(m\) 个点，再往第 \(i\) 个点上连一条向 \(b_i\) 的边，那么就生成了一个内向基环森林，在这里，有两种求距离的方式：

  1. 把环上的每一个点都作为一棵子树的根，将距离分为环上距离与树上距离；
  2. 把环上某个点连向父节点的边砍掉，重新建树，就可以转换为新树上的距离。

至此，思路已经结束。

CODE

下面分别给出两种基环树（森林）上求距离的方法代码。

  1. 把环上的每一个点都作为一棵子树的根，将距离分为环上距离与树上距离；

    #include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e6+10;
int T,n,m,idx;
int a[N],b[N],dl[N],dr[N],dep[N],head[N];
struct CFS{
	int tot,h[N],v[N],nxt[N];
	void Clear(int n){
		tot=0,RCL(h,0,int,n+5);
	}
	void att(int U,int V){
		v[++tot]=V,nxt[tot]=h[U],h[U]=tot;
	}
}g;
struct DSU{
	int fa[N],siz[N];
	int operator [](int i){
		return get(i);
	}
	void Init(int n){
		FOR(i,1,n)fa[i]=i,siz[i]=1;
	}
	int get(int x){
		return fa[x]^x?fa[x]=get(fa[x]):x;
	}
	bool Check(int u,int v){
		return get(u)==get(v);
	}
	bool Merge(int u,int v){
		int x=get(u),y=get(v);
		if(x==y)return 0;
		if(siz[x]>siz[y])swap(x,y);
		return fa[y]=x,siz[x]+=siz[y],head[x]|=head[y],1;
	}
}D;
void Build(int u){
	dl[u]=++idx;
	EDGE(g,i,u,v)dep[v]=dep[u]+1,Build(v);
	dr[u]=idx;
}
bool Rela(int u,int v){
	return dl[v]<=dl[u]&&dl[u]<=dr[v];
}
int Dis(int u,int v){
	if(!D.Check(u,v))return INF;
	if(Rela(u,v))return dep[u]-dep[v];
	return Rela(b[head[D[u]]],v)?dep[u]+1+(dep[b[head[D[u]]]]-dep[v]):INF;
}
bool Check(int x){
	int tim=m;
	DOR(i,n,1){
		while(tim&&Dis(a[i],tim)>x)--tim;
		if(!tim)return 0;
	}return 1;
}
signed Cmain(){
	cin>>n>>m,idx=0,D.Init(m),g.Clear(m),RCL(head,0,int,m+5);
	FOR(i,1,n)cin>>a[i];
	FOR(i,1,m)cin>>b[i];
	FOR(i,1,m){
		if(D.Merge(i,b[i]))g.att(b[i],i);
		else head[D[i]]=i;
	}
	FOR(i,1,m)if(D[i]==i)dep[head[i]]=0,Build(head[i]);
	int ans=-1;
	for(int l=0,r=m,mid=l+r>>1;l<=r;mid=l+r>>1)Check(mid)?ans=mid,r=mid-1:l=mid+1;
	cout<<ans<<endl;
	return 0;
}
signed main(){
	for(cin>>T;T;--T)Cmain();
	return 0;
}

  2. 把环上某个点连向父节点的边砍掉，重新建树，就可以转换为新树上的距离。

    #include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e6+10;
int T,n,m,idx,cnt;
int a[N],b[N],d[N],dl[N],dr[N],id[N],num[N],rt[N],siz[N],dep[N],head[N];
queue<int> q;
struct CFS{
	int tot,h[N],v[N],nxt[N];
	void Clear(int n){
		tot=0,RCL(h,0,int,n+5);
	}
	void att(int U,int V){
		v[++tot]=V,nxt[tot]=h[U],h[U]=tot;
	}
}g;
struct DSU{
	int fa[N],siz[N];
	int operator [](int i){
		return get(i);
	}
	void Init(int n){
		FOR(i,1,n)fa[i]=i,siz[i]=1,head[i]=0;
	}
	int get(int x){
		return fa[x]^x?fa[x]=get(fa[x]):x;
	}
	bool Check(int u,int v){
		return get(u)==get(v);
	}
	bool Merge(int u,int v){
		int x=get(u),y=get(v);
		if(x==y)return 0;
		if(siz[x]>siz[y])swap(x,y);
		return fa[y]=x,siz[x]+=siz[y],head[x]|=head[y],1;
	}
}D;
void Build(int u){
	dl[u]=++idx;
	EDGE(g,i,u,v)if(!d[v])rt[v]=rt[u],dep[v]=dep[u]+1,Build(v);
	dr[u]=idx;
}
void Circle(int u){
	id[u]=cnt,++siz[cnt];
	if(!id[b[u]])num[b[u]]=num[u]+1,Circle(b[u]);
}
bool Rela(int u,int v){
	return dl[v]<=dl[u]&&dl[u]<=dr[v];
}
int Dis(int u,int v){
	if(!D.Check(u,v))return INF;
	if(Rela(u,v))return dep[u]-dep[v];
	return rt[v]!=v?INF:num[v]-num[rt[u]]+(num[v]>=num[rt[u]]?0:siz[id[rt[u]]])+dep[u]-dep[rt[u]];
}
bool Check(int x){
	int tim=m;
	DOR(i,n,1){
		while(tim&&Dis(a[i],tim)>x)--tim;
		if(!tim)return 0;
	}return 1;
}
signed Cmain(){
	cin>>n>>m,idx=0,cnt=0,D.Init(m),g.Clear(m),RCL(d,0,int,m+5),RCL(id,0,int,m+5);
	FOR(i,1,n)cin>>a[i];
	FOR(i,1,m)cin>>b[i],++d[b[i]];
	FOR(i,1,m){
		g.att(b[i],i);
		if(!D.Merge(i,b[i]))head[D[i]]=i;
	}
	FOR(i,1,m)if(!d[i])q.push(i);
	while(!q.empty()){
		int u=q.front();q.pop();
		if(!(--d[b[u]]))q.push(b[u]);
	}
	FOR(i,1,m)if(d[i])rt[i]=i,Build(i);
	FOR(i,1,m)if(D[i]==i)dep[head[i]]=0,Build(head[i]);
	FOR(i,1,m)if(D[i]==i)siz[++cnt]=0,num[head[i]]=1,Circle(head[i]);
	int ans=-1;
	for(int l=0,r=m,mid=l+r>>1;l<=r;mid=l+r>>1)Check(mid)?ans=mid,r=mid-1:l=mid+1;
	cout<<ans<<endl;
	return 0;
}
signed main(){
	for(cin>>T;T;--T)Cmain();
	return 0;
}

总结

这题最难的部分在于二分答案的检验过程与基环森林的构建，攻克后就十分简单，十分适合练手。

标签：Non,return,get,int,题解,head,Long,siz,define
From： https://www.cnblogs.com/Cat-litter/p/18188152

相关文章

  • P10227 [COCI 2023/2024 #3] Slučajna Cesta 题解
    P10227[COCI2023/2024#3]SlučajnaCesta题解知识点期望DP，树形（换根）DP，组合数学。题意分析一棵树，每个点都有点权，每一条边的方向分布都是等概率的，问从每个点出发，有路走就一直走的情况下，所途径的点的权值总和的期望值。思路分析这明显是一个树形DP，且需要变成换根DP......
  • [ABC261E] Many Operations 题解
    [ABC261E]ManyOperations题解思路解析首先可以发现，如果直接跑肯定会炸，于是考虑优化。首先发现操作有很多重复的，所以可以考虑把每一个数经过所有操作后的值都预处理下来，但这样显然空间也会炸。然后我们又想到可以不需要求下每个数经过操作后的值，可以把每一位二进制上在开始前......
  • ABC353C Sigma Problem 题解
    ABC353CSigmaProblem题解题目链接：AT题目中的两个求和符号\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\)实际上是在枚举所有的有序数对\((i,j)\)。而有序数对的个数\(N(N-1)/2=O(N^{2})\)，真的去枚举所有数对肯定会T。这时应该考虑去拆贡献，求出每个\(A_i\)对答案的贡献。......
  • 2024江苏省大学生程序设计大赛（JSCPC）热身赛题解（B）
    题目大意：求区间\([l,r]\)中有多少正整数满足\(\phi(\phi(n))=\phi(n)-1\)，其中\(\phi\)为欧拉函数。解：设\(y=\phi(n)\)，则上式变为\(\phi(y)=y-1\)，易证\(y\)为质数（注意\(\phi(1)=1\)，\(1\)与任何正整数都互质）。故原问题转化为求\([l,r]\)中有多少个正整数v满足\(\phi......
  • mysql使用group by查询报错SELECT list is not in GROUP BY clause and contains nona
    官方解释：ONLY_FULL_GROUP_BY是MySQL数据库提供的一个sql_mode,通过这个sql_mode来保证,SQL语句“分组求最值”合法性的检查.这种模式采用了与Oracle、DB2等数据库的处理方式。即不允许selecttargetlist中出现语义不明确的列.对于用到GROUPBY的select语句,查出......
  • set 容器详解 附大根堆题解
    声明本文中题解部分内容大部分转载自@sonnety的这篇博客中，本文为为方便复习而写的结论类文章，读者可自行跳转至原文处阅读。PART1set什么是set——来源cppreference简言之，它就是一种存进去就可以自动按升序排列的特殊容器，通常的set还具有自动去重的功能。定义方......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决：  一，方便的页面监控     前几天早上，负责的kettle抽取数据表的任务又报错了，早上看手机有4个未接报警电话，一看是人员表，原来昨天报表系统有个大的查询一直未查询完成，导致truncate这个人员表，无法活动meta的锁，后续执行抽取和计算的都报错......
  • U423621 [HDK - NRC] Sqen Paradox 题解
    题目描述及\(O(n^2)\)做法见这个设\(a_i\)表示以\(i\)为左端点，无重复元素的最长区间的左端点，这个直接拿双指针做就行。处理出来后，分类讨论，找\(\max(i-l+1,i-a_i+1)\)，找\(i-l+1\)拿个桶维护一下左端点为\(i\)的右端点有那些就行，剩下的位置找最值即可，这个是RMQ。时间......
  • 工作疑难问题解决4例
      记录一下工作上疑难问题解决：  一，方便的页面监控     前几天早上，负责的kettle抽取数据表的任务又报错了，早上看手机有4个未接报警电话，一看是人员表，原来昨天报表系统有个大的查询一直未查询完成，导致truncate这个人员表，无法活动meta的锁，后续执行抽取和计算的都报错......
  • 第六届·2024 MindSpore 量子计算黑客松热身赛赛题解读
    第六届·2024MindSpore量子计算黑客松火热进行中。本次大赛由量子信息网络产业联盟主办，昇思MindSporeQuantum社区承办，多所高校和单位联合举办。开发者将全面体验全新一代通用量子计算框架MindSporeQuantum。热身赛为量子计算基础学习和编程演练。完成热身赛的前100名选手将有......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99