2021-4-1 【天梯赛】【PTA】

每日三百行代码 第二十七天

在这里插入代码片
#include<iostream>
#include<math.h>
#include<string.h>
using namespace std;

const int maxn = 100005;
const double eps = 0.05;
double ep1[maxn],ep2[maxn],ep3[maxn];
int main()
{
   
	memset(ep1,0,sizeof(ep1));
	memset(ep2,0,sizeof(ep2));
	memset(ep3,0,sizeof(ep3));
	int max1 = 0,max2 = 0;
	int n,m;int a;double b;
	cin>>n;
	for(int i=0;i<n;i++)
	{
   
		
		scanf("%d %lf",&a,&b);
		ep1[a] = b;
		if(a > max1)  max1 = a;   
		 //多项式A的最高次幂 
	}
	cin>>m;
	for(int i=0;i<m;i++)
	{
   
		scanf("%d %lf",&a,&b);
		ep2[a] = b;
		if(a > max2)  max2 = a; 
		  //多项式B的最高次幂
	}
	if(max1 < max2)              
	 //如果A的最高次幂小于B的最高次幂，就相当于3/5，除数为0，余数为3本身 ，这样就是除数为0，余数为A本身 
	{
   
		printf("0 0 0.0\n");
		printf("%d",n);
		for(int i=max1;i>=0;i--)
		{
   
			if(fabs(ep1[i]) >= eps)
			printf(" %d %.1lf",i,ep1[i]);
		}
	}
	else                        
	      //多项式除法的运算法测，不会的可以结合百度，B站自己学习 
	{
   
		int t = max1;
		while(max1 >= max2)
		{
   
			double y = ep1[max1]/ep2[max2];
			ep3[max1 - max2] = y;
			for(int i=max2;i>=0;i--)
			{
   
				if(fabs(ep2[i]) >= eps)
				ep1[max1+i-max2]-=y*ep2[i];
			}
			int pos=0;                         
			for(int i=max1;i>=0;i--)
			{
   
				if(fabs(ep1[i]) >= eps)
				{
   
					pos = i;              
					break;
				}
			}
			max1 = pos;
		}
		int n1=0,n2=0;
		for(int i=t;i>=0;i--)
		if(fabs(ep1[i]) >= eps)
		n1++;
		for(int i=t;i>=0;i--)
		if(fabs(ep3[i]) >= eps)
		n2++;
		if(n2 == 0)
		{
   
			printf("0 0 0.0\n");
		}
		else
		{
   
			printf("%d",n2);
			for(int i=t;i>=0;i--)
			if(fabs(ep3[i]) >= eps)
			printf(" %d %.1lf",i,ep3[i]);
            cout<<endl;
		}
		
		if(n1 == 0)
		{
   
			printf("0 0 0.0\n");
		}
		else
		{
   
			printf("%d",n1);
			for(int i=t;i>=0;i--)
			if(fabs(ep1[i]) >= eps)
			printf(" %d %.1lf",i,ep1[i]);
		}
	} 
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
   
    int n,m;
    double sum=0;
    cin>>n;
    map<string,int> v1,v2;
    map<string,int> ::iterator it;
    for(int i=0;i<n;i++){
   
        string temp;
        cin>>temp;
        v1[temp]=1;
    }
    cin>>m;
    for(int i=0;i<m;i++){
   
        string s;
        int num;
        cin>>s>>num;
        sum+=num;
        v2[s]=num;
    }
    sum=sum*1.0/m;
    bool flag=false;
    for(it=v2.begin();it!=v2.end();it++){
   
        if(it->second>sum && v1[it->first]!=1){
   
            cout<<it->first<<endl;
            flag=true;
        }
    }
    if(flag==false){
   
        cout<<"Bing Mei You"<<endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> v[maxn];
int dd[maxn]={
   0};
double ddz=0;
void dfs(int r,double cur, double c){
   
	
	if(dd[r] !=0 ){
   
		ddz += cur*dd[r];
		cur = cur*dd[r];
	}else{
   
		cur = cur * (1 - c/100.0); 
	}
	for(int i=0;i<v[r].size();i++){
   
		int j = v[r][i];
		dfs(j,cur,c);
	}
}
int main(){
   
	int n,k,num,tmp;
	double total,count;
	cin>>n>>total>>count;
	for(int i=0;i<n;i++){
   
		cin>>k;
		if(k==0){
   
			cin>>dd[i];
		}else{
   
			for(int j=0;j<k;j++){
   
				cin>>tmp;
				v[i].push_back(tmp);
			}
		}
	}
	dfs(0,total,count);
	printf("%d\n",int(ddz));
	return 0;
} 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct NODE {
   
	string name;
	int sum;
	int num;
	double ave;
	/*bool friend operator < (NODE a, NODE b) { if (a.sum != b.sum) return a.sum > b.sum; else return a.ave < b.ave; }*/
}ren[1010];
bool book[10000010];
bool cmp(NODE a,NODE b)
{
   
    if (a.sum != b.sum) return a.sum > b.sum;
	else return a.ave < b.ave;
}
int main() {
   
	int n, m;
    cin>>n;
	for (int i = 0; i < n; i++) {
   
		cin >> ren[i].name >> ren[i].num;
		memset(book, 0, sizeof(book));//每一次循环初始化
		for (int j = 0; j < ren[i].num; j++) {
   
			int k;
			scanf("%d", &k);
			if (book[k] == 0) 
                ren[i].sum++;/*类似桶排序一样，标记一个人点赞不同的标号就几种， 我还想的用set或者标记上再循环遍历一下求，这样就方便多了*/
			book[k] = 1;
		}
		ren[i].ave = ren[i].num * 1.0 / ren[i].sum;//计算标签出现次数平均值，没理解让求啥
	}
	sort(ren, ren + n,cmp);
	for (int i = 0; i < 3; i++) {
   
		if (i != 0) cout << " ";
		if (n < i + 1) cout << "-";
		else cout << ren[i].name;
	}
	return 0;
} 

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
using namespace std;
struct T{
   //定义结构体用来存储 姓名 点赞总量 输出标签出现次数平均值 
	string name;
	int Sum;
	double avg;
};
auto cmp=[](T &e1,T &e2){
   
	if(e1.Sum!=e2.Sum)
		return e1.Sum>e2.Sum;
	else
		return e1.avg<e2.avg;
};
int main(){
   
	int N;
	cin>>N;
	vector<T>res;
	while(N--){
   
		string str;
		int num;
		set<int>s;//用来统计每个用户点赞不同的人数 set去除重复数据元素的特性 
		cin>>str;
		cin>>num;
		for(int i=0;i<num;i++){
   
			int val;
			cin>>val;
			s.insert(val);
		}//将得到的数据依次放入容器中 
		res.push_back({
   str,s.size(),(num*1.0)/s.size()});
	}
	sort(res.begin(),res.end(),cmp);//进行排序 
	if(res.size()>=3)//存在前三名 
		cout<<res[0].name<<" "<<res[1].name<<" "<<res[2].name;
	if(res.size()==2)//只存在两个 
		cout<<res[0].name<<" "<<res[1].name<<" "<<"-";
	if(res.size()==1)//只存在一个 
		cout<<res[0].name<<" "<<"-"<<" "<<"-";
	return 0;
}

#include<iostream>
#include<stdio.h>
#include<vector>
#include<map>
#include<deque>
#include<string.h>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
vector<int> ans;
deque<int> dq;

int head,n,x;

struct node{
   
    int address,key,next;
}a[100001];


int main()
{
   
    cin>>head>>n;
    for(int i=0;i<n;i++)
    {
   
        cin>>x;
        cin>>a[x].key>>a[x].next;
        a[x].address=x;
    }

    while(head!=-1)
    {
   
        dq.push_back(a[head].address);
        head=a[head].next;
    }

    while(!dq.empty())
    {
   
        ans.push_back(dq.back());
        dq.pop_back();
        if(dq.empty()) break;
        ans.push_back(dq.front());
        dq.pop_front();
    }
    int size=ans.size();
    for(int i=0;i<size;i++)
    {
   
        if(i!=size-1) printf("%05d %d %05d\n",ans[i],a[ans[i]].key,ans[i+1]);
        else printf("%05d %d -1\n",ans[i],a[ans[i]].key);
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int head,n,co,num1[N],num2[N];
struct node{
   
	int ad;
	int data;
	int next;
}List[N];
int main()
{
   
	scanf("%d%d",&head,&n);
	int a,d,ne;
	for(int i=0;i<n;i++)
	{
   
		scanf("%d%d%d",&a,&d,&ne);
		List[a].ad=a;
		List[a].data=d;
		List[a].next=ne;	
	}
	int k=0; //使用k来对有效节点进行计数，将多余节点排除在外
	while(head!=-1)	//没有到-1就一直对有效节点进行查询并用数组num1[]记录
	{
   
		num1[k++]=head;
		head=List[head].next;
	}
    n=k;    //用新的k来更新n，去除多余节点
	int l=0,r=n-1;
	while(l<=r)
	{
   
		if(l==r)
		{
   
			num2[co]=num1[l++];	
		}
		else{
   
			num2[co++]=num1[r--];
			num2[co++]=num1[l++];	
		}
	}
	for(int i=0;i<n-1;i++)
	{
   
		printf("%05d %d %05d\n",num2[i],List[num2[i]].data,num2[i+1]);
	}
	printf("%05d %d -1",num2[n-1],List[num2[n-1]].data);
	return 0;
}