• 【天梯赛 - L2习题集】啃题（6 / 44）

    目录

    ！L2-001 城市间紧急救援 - Dijkstra运用

    ！L2-002 链表去重 - 链表模拟

    ！L2-003 月饼 - 结构体+重载运算符+排序

    ！L2-004 这是二叉搜索树吗？- 建二叉树模板题

    L2-005 集合相似度 - set容器去重应用

    L2-006 树的遍历 - 中后序遍历构建树+层序遍历

    ！L2-007 家庭房产 - 并查集+结构体+排

    ！L2-008 最长对称子串 - 字符串+暴力+双指

    getline和cin区别

    L2-009 抢红包 - 模拟+排序

    L2-010 排座位

    L2-011 玩转二叉树 - 前中序遍历构建树+层序遍历

    ✓L2-012 关于堆的判断 - 优先队列+哈希表

    ！L2-001 城市间紧急救援 - Dijkstra运用

    思路：

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int N=510;
    7. int n,m,s,d;
    8. int g[N][N];
    9. int dist[N],w[N],sumw[N],road[N],pre[N];
    10. int prt[N],cnt=0;
    11. bool st[N];
    12.  
    13. void dijkstra()
    14. {
    15. 	memset(dist,0x3f,sizeof dist);
    16. 	dist[s]=0;
    17. 	sumw[s]=w[s]; //救援队数目
    18. 	road[s]=1; //最短路径的条数 
    19. 	
    20. 	for(int i=0;i
    21. 	{
    22. 		int t=-1;
    23. 		for(int j=0;j
    24. 			if(!st[j]&&(t==-1||dist[j]
    25. 				t=j;
    26. 		st[t]=true;
    27. 		
    28. 		for(int j=0;j
    29. 		{
    30. 			if(dist[j]>dist[t]+g[t][j]) //选最短路径
    31. 			{
    32. 				dist[j]=dist[t]+g[t][j];
    33. 				road[j]=road[t]; //不理解
    34. 				sumw[j]=sumw[t]+w[j];
    35. 				pre[j]=t;
    36. 			}
    37. 			else if(dist[j]==dist[t]+g[t][j])
    38. 			{
    39. 				road[j]+=road[t]; //不理解
    40. 				if(sumw[j]
    41. 				{
    42. 					sumw[j]=sumw[t]+w[j];
    43. 					pre[j]=t;
    44. 				}
    45. 			}
    46. 		} 
    47. 	}
    48. 	cout<' '<
    49. 	//把经过的点倒序输出 
    50. 	cout<
    51.     for(int i=d;i!=s;i=pre[i])
    52.     	prt[cnt++]=i;
    53.     reverse(prt,prt+cnt);
    54.     for(int i=0;i
    55.     	cout<<' '<
    56. }
    57.  
    58.  
    59. int main()
    60. {
    61. 	cin>>n>>m>>s>>d;
    62. 	for(int i=0;i>w[i];
    63. 	memset(g,0x3f,sizeof g);
    64. 	while(m--)
    65. 	{
    66. 		int a,b,c;
    67. 		cin>>a>>b>>c;
    68. 		g[a][b]=g[b][a]=c;
    69. 	}
    70. 	dijkstra();
    71. 	return 0;
    72. }

    ！L2-002 链表去重 - 链表模拟

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include  
    7. using namespace std;
    8.  
    9. const int N=1e5+10;
    10. int head,n;
    11. int e[N],ne[N];
    12. bool st[N];
    13.  
    14. int main()
    15. {
    16. 	cin>>head>>n;
    17. 	while(n--)
    18. 	{
    19. 		int idx,w,next;
    20. 		cin>>idx>>w>>next;
    21. 		e[idx]=w,ne[idx]=next;
    22. 	}
    23. 	
    24. 	vector<int>re,unre; //re存重复元素 unre存不重复元素 
    25. 	for(int i=head;i!=-1;i=ne[i])
    26. 	{
    27. 		int x=abs(e[i]);
    28. 		if(!st[x])
    29. 		{
    30. 			st[x]=true;
    31. 			unre.push_back(i);
    32. 		}else re.push_back(i);
    33. 	}
    34. 	//输出去重的链表 
    35. 	for(int i=0;isize();i++)
    36. 	{
    37. 		printf("%05d %d",unre[i],e[unre[i]]);
    38. 		if(i==unre.size()-1) puts(" -1");
    39. 		else printf(" %05d\n",unre[i+1]);
    40. 	} 
    41. 	//输出删去的链表 
    42. 	for(int i=0;isize();i++)
    43. 	{
    44. 		printf("%05d %d",re[i],e[re[i]]);
    45. 		if(i==re.size()-1) puts(" -1");
    46. 		else printf(" %05d\n",re[i+1]);
    47. 	} 
    48. 	return 0;
    49. }

      

    ！L2-003 月饼 - 结构体+重载运算符+排序

    思路:

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include  
    7. using namespace std;
    8.  
    9. const int N=1010;
    10. int n;
    11. double d,res=0;
    12. struct node
    13. {
    14. 	double w,p;
    15. 	bool operator<(const node &t)const //按照单价由大到小排序
    16. 	{
    17. 		return p/w>t.p/t.w; 
    18. 	} 
    19. }a[N];
    20.  
    21. int main()
    22. {
    23. 	cin>>n>>d;
    24. 	for(int i=0;i>a[i].w;
    25. 	for(int i=0;i>a[i].p;
    26. 	sort(a,a+n);
    27. 	for(int i=0;i0;i++)
    28. 	{
    29. 		if(a[i].w<=d)
    30. 		{
    31. 			d-=a[i].w;
    32. 			res+=a[i].p;
    33. 		}else
    34. 		{
    35. 			res+=a[i].p/a[i].w*d;
    36. 			break;
    37. 		}
    38.         //这个办法很妙↓
    39.         /*double r=min(d,a[i].w);
    40. 		d-=r;
    41. 		res+=a[i].p/a[i].w*r;*/
    42. 	}
    43. 	printf("%.2f\n",res);
    44. 	return 0;
    45. }

    ！L2-004 这是二叉搜索树吗？- 建二叉树模板题

    思路：

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int N=1010;
    6. int n,a[N];
    7. int p1[N],p2[N];
    8. int cnt1=0,cnt2=0; 
    9. bool flag;
    10.  
    11. typedef struct node
    12. {
    13. 	int data;
    14. 	node *l,*r;
    15. }node,*tree;
    16.  
    17. tree create1(tree T,int x)
    18. {
    19. 	if(!T) 
    20. 	{
    21. 		T=(tree)malloc(sizeof(node));
    22. 		T->l=nullptr,T->r=nullptr;
    23. 		T->data=x;
    24. 	}
    25. 	else
    26. 	{
    27. 		if(T->data>x) T->l=create1(T->l,x);
    28. 		else if(T->data<=x) T->r=create1(T->r,x);
    29. 	}
    30. 	return T;
    31. }
    32.  
    33. tree create2(tree T,int x)
    34. {
    35. 	if(!T) 
    36. 	{
    37. 		T=(tree)malloc(sizeof(node));
    38. 		T->l=nullptr,T->r=nullptr;
    39. 		T->data=x;
    40. 	}
    41. 	else
    42. 	{
    43. 		if(T->data<=x) T->l=create2(T->l,x);
    44. 		else if(T->data>x) T->r=create2(T->r,x);
    45. 	}
    46. 	return T;
    47. }
    48.  
    49. void pre1(tree T)
    50. {
    51. 	if(!T) return;
    52. 	p1[cnt1++]=T->data;
    53. 	pre1(T->l);
    54. 	pre1(T->r);
    55. } 
    56.  
    57. void pre2(tree T)
    58. {
    59. 	if(!T) return;
    60. 	p2[cnt2++]=T->data;
    61. 	pre2(T->l);
    62. 	pre2(T->r);
    63. } 
    64.  
    65. void post(tree T)
    66. {
    67. 	if(!T) return;
    68. 	post(T->l);
    69. 	post(T->r);
    70. 	if(flag) cout<<' ';
    71. 	flag=true;
    72. 	cout<data;
    73. }
    74.  
    75. int main()
    76. {
    77. 	cin>>n;
    78. 	for(int i=0;i>a[i];
    79. 	//创建二叉搜索树 
    80. 	tree T1=nullptr;
    81. 	for(int i=0;icreate1(T1,a[i]);
    82. 	//创建镜像二叉搜索树
    83. 	tree T2=nullptr;
    84. 	for(int i=0;icreate2(T2,a[i]);
    85. 	//分非镜像和镜像进行前序遍历  和原序列进行比较  
    86. 	pre1(T1),pre2(T2);
    87. 	bool f1=false,f2=false;
    88. 	for(int i=0;iif(p1[i]!=a[i]) f1=true;
    89. 	for(int i=0;iif(p2[i]!=a[i]) f2=true;
    90. 	
    91. 	if(f1&&f2) cout<<"NO";
    92. 	else if(!f1&&f2) puts("YES"),post(T1);
    93. 	else if(f1&&!f2) puts("YES"),post(T2);
    94. 	else if(!f1&&!f2) puts("YES"),post(T1);
    95. 	
    96. 	return 0;
    97. }

    L2-005 集合相似度 - set容器去重应用

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int N=1e4+10;
    6. int n,m,k;
    7.  
    8. int main()
    9. {
    10. 	set<int>s[N];
    11. 	cin>>n;
    12. 	for(int i=1;i<=n;i++)
    13. 	{
    14. 		cin>>m;
    15. 		while(m--)
    16. 		{
    17. 			int x;
    18. 			cin>>x;
    19. 			s[i].insert(x);
    20. 		}
    21. 	}
    22. 	cin>>k;
    23. 	while(k--)
    24. 	{
    25. 		int a,b,cnt=0;
    26. 		cin>>a>>b;
    27. 		for(auto x:s[a]) if(s[b].count(x)) cnt++;
    28. 		printf("%.2f%%\n",cnt*1.0/(s[a].size()+s[b].size()-cnt)*100);
    29. 	}
    30. 	return 0;
    31. }

    L2-006 树的遍历 - 中后序遍历构建树+层序遍历

    思路： 这题思路跟L2-011 玩转二叉树一模一样啊 就是板子题

    • 通过中后序构建树
    • 层序遍历
    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5.  
    6. const int N=35;
    7. int n;
    8. int po[N],mid[N];
    9.  
    10. typedef struct node
    11. {
    12. 	int data;
    13. 	node *l,*r;
    14. }node,*tree;
    15.  
    16. tree reback(int len,int *po,int *mid) //通过中序和后序遍历还原前序遍历
    17. {
    18. 	if(len<=0) return NULL;
    19. 	tree T=(tree)malloc(sizeof(node));
    20. 	T->l=T->r=NULL;
    21. 	T->data=po[len-1]; //后序遍历的最后一个点为前序遍历根节点
    22.  
    23. 	int i=0; 
    24. 	for(i=0;i
    25. 		if(T->data==mid[i]) break; //在中序遍历里找到树根 记录i 
    26.  
    27. 	T->l=reback(i,po,mid);
    28. 	T->r=reback(len-1-i,po+i,mid+i+1);
    29. 	return T;
    30. }
    31.  
    32. void bfs(tree T)
    33. {
    34. 	bool flag=false;
    35. 	queueq;
    36. 	q.push(T);
    37. 	while(q.size())
    38. 	{
    39. 		auto t=q.front();
    40. 		q.pop();
    41.  
    42. 		if(flag) cout<<' ';
    43. 		flag=true;
    44.  
    45. 		cout<data;
    46. 		if(t->l)q.push(t->l);
    47. 		if(t->r)q.push(t->r);
    48. 	}
    49. }
    50.  
    51. int main()
    52. {
    53. 	cin>>n;
    54. 	for(int i=0;i>po[i];
    55. 	for(int i=0;i>mid[i];
    56. 	tree T=reback(n,po,mid);
    57. 	bfs(T);
    58. 	return 0;
    59. }

    ！L2-007 家庭房产 - 并查集+结构体+排

    1. #include 
    2. using namespace std;
    3.  
    4. const int N=1e5+10;
    5. int n;
    6. int f[N];
    7. map<int,bool>st;
    8.  
    9. struct peo
    10. {
    11. 	int id;
    12. 	double cnt,area;
    13. }p[N];
    14.  
    15. struct family
    16. {
    17. 	int anc=-1,num;
    18. 	double cnt,area,avg_cnt,avg_area; 
    19. }fam[N];
    20.  
    21. int find(int x)
    22. {
    23. 	if(x!=f[x]) f[x]=find(f[x]);
    24. 	return f[x];
    25. }
    26.  
    27. void unite(int a,int b)
    28. {
    29. 	int x=find(a);
    30. 	int y=find(b);
    31. 	if(x!=y) f[x]=y;
    32. }
    33.  
    34. bool cmp(family a,family b) //家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
    35. {
    36. 	if(a.avg_area!=b.avg_area)
    37. 	return a.avg_area>b.avg_area;
    38. 	else return a.anc
    39. }
    40.  
    41. int main()
    42. {
    43. 	for(int i=0;i
    44. 	cin>>n;
    45. 	for(int i=0;i
    46. 	{
    47. 		int id,fa,ma;
    48. 		cin>>id>>fa>>ma;
    49. 		st[id]=true;
    50. 		if(fa!=-1) st[fa]=true,unite(id,fa);
    51. 		if(ma!=-1) st[ma]=true,unite(id,ma);
    52. 		int k;
    53. 		cin>>k;
    54. 		while(k--)
    55. 		{
    56. 			int x;
    57. 			cin>>x;
    58. 			unite(x,id);
    59. 			st[x]=true;
    60. 		}
    61. 		int cnt,area;
    62. 		cin>>cnt>>area;
    63. 		p[id].cnt=cnt,p[id].area=area;
    64. 	}
    65. 	for(auto x:st)
    66. 	{
    67. 		fam[find(x.first)].cnt+=p[x.first].cnt;
    68. 		fam[find(x.first)].area+=p[x.first].area;
    69. 		if(fam[find(x.first)].anc==-1) fam[find(x.first)].anc=x.first;
    70. 		fam[find(x.first)].num++;
    71. 	}
    72. 	for(int i=0;i
    73. 	{
    74. 		if(!st[i])continue;
    75. 		fam[find(i)].avg_cnt=fam[find(i)].cnt/fam[find(i)].num;
    76. 		fam[find(i)].avg_area=fam[find(i)].area/fam[find(i)].num;
    77. 	}
    78. 	int sum=0;
    79. 	for(int i=0;iif(fam[i].num) sum++;
    80. 	cout<
    81. 	sort(fam,fam+N,cmp);
    82. 	for(int i=0;i
    83. 	printf("%04d %d %.3f %.3f\n",fam[i].anc,fam[i].num,fam[i].avg_cnt,fam[i].avg_area);
    84. 	
    85. 	return 0;
    86. }

    ！L2-008 最长对称子串 - 字符串+暴力+双指

    getline和cin区别


    getline——按行读取, 一次读取多个字符，直到读满N个（不包括空白符)为止。
    形式：getline(字符指针,字符个数N,结束符);

    cin——遇到结束符（包括空白符）会终止，只读取空白符之前的部分。

    1. #include 
    2. using namespace std;
    3.  
    4. const int N=1e5+10;
    5.  
    6. int main()
    7. {
    8. 	int res=0;
    9. 	string s;
    10. 	getline(cin,s); //不能用cin cin遇到空格就截止
    11. 	for(int i=0;isize();i++)
    12. 		for(int j=s.size()-1;j>=i;j--)
    13. 		{
    14. 			int l=i,r=j;
    15. 			while(l<=r&&s[l++]==s[r--])
    16. 				if(l>r) res=max(res,j-i+1);
    17. 		}
    18. 	cout<
    19.     return 0;
    20. }
    1. #include 
    2. using namespace std;
    3. string s;
    4. int main()
    5. {
    6. 	getline(cin,s);
    7. 	for(int len=s.size();len>0;len--) //找最大长度 倒序找
    8. 		for(int l=0;l+len-1size();l++)
    9. 		{
    10. 			bool f=false;
    11. 			int i=l,j=l+len-1;
    12. 			while(i
    13. 			{
    14. 				if(s[i]!=s[j])
    15. 				{
    16. 					f=true;
    17. 					break;
    18. 				}
    19. 				i++,j--;
    20. 			}
    21. 			if(!f)
    22. 			{
    23. 				cout<
    24. 				return 0;
    25. 			}
    26. 		}
    27. }

    L2-009 抢红包 - 模拟+排序

    思路：

    1. #include 
    2. using namespace std;
    3.  
    4. const int N=1e4+10;
    5.  
    6. struct node
    7. {
    8.     int id;
    9.     double qiang_w,fa_w,res;
    10.     int qiang_count;
    11. }a[N];
    12.  
    13. bool cmp(node a,node b)
    14. {
    15.     if(a.res!=b.res) return a.res>b.res;
    16.     else if(a.qiang_count!=b.qiang_count) return a.qiang_count>b.qiang_count;
    17.     else return a.id
    18. }
    19.  
    20. int main()
    21. {
    22.     int n;
    23.     cin>>n;
    24.     for(int i=1;i<=n;i++) a[i].id=i;
    25.     for(int i=1;i<=n;i++)
    26.     {
    27.         int k;
    28.         cin>>k;
    29.         for(int j=1;j<=k;j++)
    30.         {
    31.             int id,w;
    32.             cin>>id>>w;
    33.             a[id].qiang_w+=w;
    34.             a[id].qiang_count++;
    35.             a[i].fa_w+=w;
    36.         }
    37.     }
    38.     for(int i=1;i<=n;i++) a[i].res=a[i].qiang_w-a[i].fa_w;
    39.     sort(a+1,a+n+1,cmp);
    40.     for(int i=1;i<=n;i++) printf("%d %.2f\n",a[i].id,a[i].res*1.0/100);
    41.     return 0;
    42. }

    L2-010 排座位

    思路：

    1. #include 
    2. using namespace std;
    3. const int N=110;
    4. int g[N][N];
    5. int n,m,k;
    6.  
    7. bool check(int a,int b)
    8. {
    9. 	for(int i=1;i<=n;i++)
    10. 	    if(g[a][i]==1&&g[b][i])
    11. 	        return true;
    12. 	return false;
    13. }
    14. int main()
    15. {
    16. 	cin>>n>>m>>k;
    17. 	while(m--)
    18. 	{
    19. 		int a,b,r;
    20. 		cin>>a>>b>>r;
    21. 		g[a][b]=g[b][a]=r;
    22. 	}
    23. 	while(k--)
    24. 	{
    25. 		int a,b;
    26. 		cin>>a>>b;
    27. 		if(g[a][b]==1) puts("No problem");
    28. 		else if(g[a][b]==0) puts("OK");
    29. 		else if(g[a][b]==-1&&check(a,b)) puts("OK but...");
    30. 		else puts("No way");
    31. 	}
    32. 	return 0;
    33. }

    L2-011 玩转二叉树 - 前中序遍历构建树+层序遍历

    思路： 和L2-006 树的遍历一模一样

    • 先通过中序遍历和前序遍历确定出树  因为题目要求左右子树对调 所以递归构建的时候反一下就可以了
    • 然后用队列进行层序遍历 根节点入队 然后根节点的左右结点入队 每次取队头输出然后扔掉
    1.  
    2. #include 
    3. using namespace std;
    4.  
    5. const int N=55;
    6. int mid[N],pre[N];
    7.  
    8. typedef struct node
    9. {
    10.     int data;
    11.     node *l,*r;
    12. }node,*tree;
    13.  
    14. tree create(int len,int *mid,int *pre)
    15. {
    16.     if(!len) return NULL;
    17.     tree T=NULL;
    18.     T=(tree)malloc(sizeof(struct node));
    19.     T->l=T->r=NULL;
    20.     T->data=pre[0]; //前序遍历的第一个是根节点
    21.     
    22.     int i=0;
    23.     for(i=0;i//让i指针定位到中序遍历的根节点位置 !这里注意不能int i=0 要不然记录不了i值
    24.         if(mid[i]==T->data) break;
    25.     //因为要镜面翻转：左右子树互换
    26.     T->r=create(i,mid,pre+1);
    27.     T->l=create(len-(i+1),mid+i+1,pre+i+1);
    28.     
    29.     return T;
    30. }
    31.  
    32. void bfs(tree T)
    33. {
    34.     queueq;
    35.     q.push(T);
    36.     bool f=false;
    37.     while(!q.empty())
    38.     {
    39.         auto t=q.front();
    40.         q.pop();
    41.         if(f) cout<<' ';
    42.         f=true;
    43.         
    44.         if(t->l) q.push(t->l);
    45.         if(t->r) q.push(t->r);
    46.         cout<data;
    47.     }
    48. }
    49.  
    50. int main()
    51. {
    52.     int n;
    53.     cin>>n;
    54.     for(int i=0;i>mid[i];
    55.     for(int i=0;i>pre[i];
    56.     tree T=create(n,mid,pre);
    57.     bfs(T);
    58.     
    59.     return 0;
    60. }

     

    ✓L2-012 关于堆的判断 - 优先队列+哈希表

    大顶堆：每个结点的值都大于或等于其左右孩子结点的值；

    小顶堆：每个结点的值都小于或等于其左右孩子结点的值。

     思路：

    • 用优先队列PriorityQueue来实现小顶堆
    • 把小顶堆转化为数组 并更改数组下标从1开始 这样idx/2就是父节点
    • 用map存 < 结点值，下标 >
    • 逐步实现四个查询步骤即可 详见代码
    1. import java.util.*;
    2.  
    3. public class Main{
    4.     public static void main(String[] args)
    5.     {
    6.         Scanner sc=new Scanner(System.in);
    7.         int n=sc.nextInt(),m=sc.nextInt();
    8.         
    9.         Queueq=new PriorityQueue<>();
    10.         Map mp=new HashMap<>();
    11.         String s;
    12.         for(int i=0;i
    13.             q.offer(sc.nextInt());
    14.         
    15.         //把优先队列(小顶堆)转化到数组
    16.         Integer[] t=q.toArray(new Integer[n]);
    17.         int[] a=new int[n+1]; //因为索引从1开始 所以是n+1
    18.         int cnt=1;
    19.         //修改数组索引从1开始 这样idx/2就是父结点
    20.         for(int i=0,j=1;i
    21.             a[j++]=t[i].intValue();
    22.         for(int i=1;i<=n;i++) 
    23.         {
    24.             mp.put(a[i],cnt);
    25.             cnt++;
    26.         }
    27.         
    28.         sc.nextLine(); //接收回车
    29.         while(m-->0)
    30.         {
    31.             boolean f=false;
    32.             s=sc.nextLine();
    33.             String[] str=s.split(" ");
    34.             
    35.             if(s.indexOf("root")!=-1)
    36.             {
    37.                 int root=Integer.parseInt(str[0]);
    38.                 if(mp.get(root)==1) f=true;
    39.             }else if(s.indexOf("siblings")!=-1)
    40.             {
    41.                 int l=Integer.parseInt(str[0]);
    42.                 int r=Integer.parseInt(str[2]);
    43.                 l=mp.get(l);
    44.                 r=mp.get(r);
    45.                 if(l/2==r/2) f=true;
    46.             }else if(s.indexOf("parent")!=-1)
    47.             {
    48.                 int parent=Integer.parseInt(str[0]);
    49.                 int child=Integer.parseInt(str[5]);
    50.                 if(mp.get(child)/2==mp.get(parent)) f=true;
    51.             }else{
    52.                 int child=Integer.parseInt(str[0]);
    53.                 int parent=Integer.parseInt(str[5]);
    54.                 if(mp.get(child)/2==mp.get(parent)) f=true;
    55.             }
    56.             if(f) System.out.println("T");
    57.             else System.out.println("F");
    58.         }
    59.        
    60.     }
    61. }

     

  • 相关阅读:
    【opencv】多版本安装
    华钜同创：亚马逊开店有哪些注意事项
    （附源码）springboot在线考试系统 毕业设计 160935
    milvus集合管理
    两天学会微服务网关Gateway-Gateway路由规则
    JSP+MySQL基于ssm的主题酒店管理系统
    特斯拉第三方应用开发指南（一）
    【Spring】Spring MVC 拦截器的使用
    一篇文章带你学懂Redis
    知识图谱从入门到应用——知识图谱推理：基础知识
  • 原文地址：https://blog.csdn.net/weixin_61639349/article/details/126463011