团体程序设计天梯赛-练习集L2篇⑥

逃离我推掉我的手 2024-04-17 10:10 79阅读 0赞

> ?欢迎来到本文?  
> ?个人简介：Hello大家好呀，我是陈童学，一个与你一样正在慢慢前行的普通人。  
> ?个人主页：[@陈童学哦\`CSDN][CSDN]  
> ?所属专栏：[PTA][]  
> ?希望各位→点赞? + 收藏⭐️ + 留言?  
> ⛱️刷题的当下应是享受的！望与诸君共勉！?♂️

![在这里插入图片描述][70cc977fd4e242d1b2ded47c6c3938da.png]

> 下面是PTA的OJ平台

[**PTA的OJ平台（点击我直跳）**][PTA_OJ]

#### 题目汇总 ####

*  题解
 *   *  L2-020 功夫传人
     *  L2-021 点赞狂魔
     *  L2-022 重排链表
 *  写在最后

## 题解 ##

### L2-020 功夫传人 ###

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。

这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。

输入格式：  
输入在第一行给出3个正整数，分别是：N（≤10  
5  
）——整个师门的总人数（于是每个人从0到N−1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r ——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N行，第i行（i=0,⋯,N−1）描述编号为i的人所传的徒弟，格式为：

K  
i  
  
ID\[1\] ID\[2\] ⋯ ID\[K  
i  
  
\]

其中K  
i  
  
是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。K  
i  
  
为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。

输出格式：  
在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过10  
10  
。

输入样例：  
10 18.0 1.00  
3 2 3 5  
1 9  
1 4  
1 7  
0 7  
2 6 1  
1 8  
0 9  
0 4  
0 3  
输出样例：  
404

> AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int a[N];
    vector<int>v[N];
    int n;
    double z,r;
    double sum,ans;
    void dfs(double sum,int u)
    {
        
    	if(a[u]==1)
    	{
        
    		ans+=sum*v[u][0];
    		return ;
    	}
    	for(int i=0;i<v[u].size();i++)
    	{
        
    		dfs(sum*(1-r/100),v[u][i]);
    	}
    }
    
    int main()
    {
        
    	cin>>n>>z>>r;
    	for(int i=0;i<n;i++)
    	{
        
    		int k,x;
    		cin>>k;
    		if(k==0)
    		{
        
    			cin>>x;
    			a[i]=1;
    			v[i].push_back(x);
    		}
    		else
    		{
        
    			for(int j=0;j<k;j++)
    			{
        
    				cin>>x;
    				v[i].push_back(x);
    			}	
    		}
    	}
    	dfs(z,0);
    	printf("%0.lf",ans-0.5);
    }

### L2-021 点赞狂魔 ###

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：  
输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F  
1  
  
⋯F  
K  
  
”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，F  
i  
  
（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 10  
7  
编号。数字间以空格分隔。

输出格式：  
统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：  
5  
bob 11 101 102 103 104 105 106 107 108 108 107 107  
peter 8 1 2 3 4 3 2 5 1  
chris 12 1 2 3 4 5 6 7 8 9 1 2 3  
john 10 8 7 6 5 4 3 2 1 7 5  
jack 9 6 7 8 9 10 11 12 13 14  
输出样例：  
jack chris john

> AC代码：

#include<bits/stdc++.h>
    using namespace std;
    struct node{
        
    	string name;
    	int num;
    	int fact;
    };
    bool cmp(node a,node b)
    {
        
    	if(a.fact==b.fact)
    		return a.num<b.num;
    	return a.fact>b.fact;
    }
    
    int main()
    {
        
    	node q[101];
    	set<int>st;
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    	{
        
    		string s;
    		cin>>s;
    		q[i].name=s;
    		int x;
    		cin>>x;
    		q[i].num=x;
    		for(int j=0;j<x;j++)
    		{
        
    			int y;
    			cin>>y;
    			st.insert(y);
    		}
    		q[i].fact=st.size();
    		st.clear();
    	}
    	sort(q,q+n,cmp);
    	for(int i=0;i<3;i++)
    	{
        
    		if(i!=0)
    			cout<<" ";
    		if(i>n-1)
    			cout<<"-";
    		else
    			cout<<q[i].name;
    	}
    }

### L2-022 重排链表 ###

给定一个单链表 L  
1  
  
→L  
2  
  
→⋯→L  
n−1  
  
→L  
n  
  
，请编写程序将链表重新排列为 L  
n  
  
→L  
1  
  
→L  
n−1  
  
→L  
2  
  
→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：  
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤10  
5  
)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next  
其中Address是结点地址；Data是该结点保存的数据，为不超过10  
5  
的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：  
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：  
00100 6  
00000 4 99999  
00100 1 12309  
68237 6 -1  
33218 3 00000  
99999 5 68237  
12309 2 33218  
输出样例：  
68237 6 00100  
00100 1 99999  
99999 5 12309  
12309 2 00000  
00000 4 33218  
33218 3 -1

> AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    struct node
    {
        
    	int val;
    	int next;
    }a[N];
    
    int main()
    {
        
    	int head,n;
    	cin>>head>>n;
    	int address,data,nex;
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>address>>data>>nex;
    		a[address].val=data;
    		a[address].next=nex;
    	}
    	int cnt=0;
    	int res1[N],res2[N];
    	while(head!=-1)
    	{
        
    		res1[cnt++]=head;
    		head=a[head].next;
    	}
    	int left=0,right=cnt-1;
    	int cnt2=0;
    	while(left<=right)
    	{
        
    		if(left==right)
    			res2[cnt2++]=res1[right--];
    		else
    		{
        
    			res2[cnt2++]=res1[right--];
    			res2[cnt2++]=res1[left++];
    		}
    	}
    	for(int i=0;i<cnt-1;i++)
    	{
        
    		printf("%05d %d %05d\n",res2[i],a[res2[i]].val,res2[i+1]);
    	}
    	printf("%05d %d -1\n",res2[cnt-1],a[res2[cnt-1]].val);
    }

## 写在最后 ##

> `???不必偏执于未知的真实，身处的当下即是意义和真实，爱才是解题的答案，也是刻画人生色彩的笔尖，耐心的走下去，总会遇到你爱的人和爱你的人。`

???好啦，本文的内容就到此结束啦，我们下期再见哦！另外在祝各位小伙伴们要天天开心哦！  
???如果你觉得本文对你有帮助的话，还请不要吝惜您的三连哦！您的支持就是我创作的最大动力！！爱你们???  
![在这里插入图片描述][8089a73f942d4d32bd355d63c7696d74.jpeg_pic_center]

[CSDN]: https://blog.csdn.net/H1727548?type=lately
[PTA]: https://blog.csdn.net/h1727548/category_12186329.html?spm=1001.2014.3001.5482
[70cc977fd4e242d1b2ded47c6c3938da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/e07a743a8ce3465aa50cee6133794528.png
[PTA_OJ]: https://pintia.cn/problem-sets/dashboard
[8089a73f942d4d32bd355d63c7696d74.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/85ba10e6f27540dca3f4b46e4b007409.jpeg