重庆分公司,新征程启航

为企业提供网站建设、域名注册、服务器等服务

PTA天梯赛day2-创新互联

Day2
  • 2-1 L1-009 N个数求和
    • 题目描述
    • 解题思路
  • 2-2 L1-011 A-B
    • 题目描述
    • 解题思路
  • 2-3 L2-005 集合相似度
    • 题目描述
    • 解题思路
  • 2-4 L2-006 树的遍历
    • 题目描述
    • 解题思路
  • 2-5 L2-007 家庭房产
    • 题目描述
    • 解题思路

创新互联公司是一家网站设计公司,集创意、互联网应用、软件技术为一体的创意网站建设服务商,主营产品:成都响应式网站建设公司成都品牌网站建设营销型网站。我们专注企业品牌在网站中的整体树立,网络互动的体验,以及在手机等移动端的优质呈现。成都做网站、成都网站制作、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案,我们深知市场的竞争激烈,认真对待每位客户,为客户提供赏析悦目的作品,网站的价值服务。2-1 L1-009 N个数求和 题目描述

在这里插入图片描述
在这里插入图片描述

解题思路

对于两个数,先通分分母,再将分子乘上相应的倍数。
可通过__gcd(a,b)求出a与b的大公因数,再用a*b/__gcd(a,b)求出a与b的最小公倍数。

注意: 每两个数运算完后,就要立刻化简,否则过程数会超long long;存在数字为0的情况,注意这时候的读入和处理方式。

#includeusing namespace std;
typedef long long ll;
ll a[105],b[105];
int main(){int n;
	cin>>n;
	char c;
	ll k=1;
	ll sum=0;
	cin>>a[1];
	if (a[1]) cin>>c>>b[1];
	else b[1]=1;
	for (int i=2; i<=n; i++){cin>>a[i];
		if (a[i]) cin>>c>>b[i];
		else b[i]=1;
		k=b[i]*b[i-1]/__gcd(b[i],b[i-1]);
		ll r1=k/b[i-1];
		a[i-1]*=r1;
		ll r2=k/b[i];
		a[i]*=r2;
		a[i]=a[i]+a[i-1];
		b[i]=k;

		ll gcd=-1;
		while (gcd!=1){	gcd=__gcd(a[i],b[i]);
			a[i]/=gcd;
			b[i]/=gcd;
		}
	}


	sum=a[n];
	k=b[n];
	if (sum==0){cout<<0;
		return 0;
	}

	if (sum%k==0){cout<gcd=__gcd(xiao,k);
		xiao/=gcd;
		k/=gcd;
	}
	cout<

由于PTA会卡空格,如果没有if (sum%k==0)的特殊输出处理,则执行if (zheng) cout<时会产生多余的一个空格,导致格式错误。

2-2 L1-011 A-B 题目描述

在这里插入图片描述

解题思路

可定义c数组,记录s2中某一个字符是否出现过即可。

#includeusing namespace std;
int c[100005];
int main(){string a,b,d;
	getline(cin,a);
	getline(cin,b);
	int l=b.size();
	for (int i=0; iif (!c[int(a[i])]){	d+=a[i];
		}
	}
	cout<
2-3 L2-005 集合相似度 题目描述

在这里插入图片描述
在这里插入图片描述

解题思路

set是一个内部自动有序且不含重复元素的容器,方便处理此题。对于两个集合,可通过a集合中元素数量、b集合中元素数量和ab中交集元素数量,可直接求出ab的并集元素数量。

#includeusing namespace std;

const int maxn=55,maxm=1e4+5;

seta[maxm];
int n,m,k;

int main(){cin>>n;
    for (int i=1; i<=n; i++){cin>>m;
        for (int j=1; j<=m; j++){int tmp;
            scanf("%d",&tmp);
            a[i].insert(tmp);
        }
    }
    cin>>k;
    for (int l=1; l<=k; l++){int q,p;
        scanf("%d%d",&q,&p);
        int s=0,s1=a[q].size(),s2=a[p].size();
        for (auto i=a[q].begin(); i!=a[q].end(); i++){if (a[p].find(*i)!=a[p].end()){s++;
            }
        }
        printf("%.2lf%\n",double(s*100)/(s1+s2-s));
    }
    return 0;
}

set用法
参考题解

2-4 L2-006 树的遍历 题目描述

在这里插入图片描述

解题思路

在这里插入图片描述
b为中序遍历数组,c为后序遍历数组。
对于每一次递归,参数 l1,l2,r1,r2 分别表示中序遍历的左右端点和后序遍历的左右端点。显然,每次后序遍历中,c[r2]即为该区间中的父节点,我们同时在b数组中找到父结点的下标,就可以通过b数组种 l1 和父节点坐标的差值算出左子树中结点个数 lnum,同理可以得到右子树中节点个数。这样就可以将当前大区间拆分成左右子树两个区间了。
doit(l1,l1+lnum-1,l2,l2+lnum-1);
doit(l1+lnum+1,r1,l2+lnum);
如果求先序遍历,则在拆分区间前,将父节点push到a中。
如果求层序遍历,则定义a为优先队列,每次父节点push时,同时把该层的层数也push进即可。因为有些结点的层数会相等,我们同时再去定义nu去记录该节点是当前层数的第几个。重载优先队列运算符:return (a.w

#includeusing namespace std;

int n;
vectorb,c;

struct node{int v,w,nu;
    bool operator<(const node a) const {return (a.wa;

void doit(int l1,int r1,int l2,int r2,int flo,int nu){if (l1>r1 || l2>r2) return;

    a.push({c[r2],flo,nu});

    // vector::iterator mid=find(b.begin(),b.end(),c[r]);
    
    int lnum=find(b.begin(),b.end(),c[r2])-find(b.begin(),b.end(),b[l1]);
    Floor[flo+1]++;
    doit(l1,l1+lnum-1,l2,l2+lnum-1,flo+1,Floor[flo+1]);
    Floor[flo+1]++;
    doit(l1+lnum+1,r1,l2+lnum,r2-1,flo+1,Floor[flo+1]);

}

int main(){cin>>n;
    for (int i=0; iint tmp;
        scanf("%d",&tmp);
        c.push_back(tmp);
    }
    for (int i=0; iint tmp;
        scanf("%d",&tmp);
        b.push_back(tmp);
    }
    Floor[1]=1;
    doit(0,n-1,0,n-1,1,1);
    while (!a.empty()){if (a.size()!=1) cout<

vector中如何查找元素的下标
查找vector元素下标
vector的find

2-5 L2-007 家庭房产 题目描述

在这里插入图片描述
在这里插入图片描述

解题思路

并查集,每个人所记录的父节点是当前集合中最小的编号数。用book数组记录当前的人,是否统计到了集合的总人数中,并且每次将所含的房子数和面积数累加到父节点中。

#includeusing namespace std;

const int maxn=1e4+1;

struct node{int a; //父节点编号
    int f[3];
    int s[6];
    int s_num;
    int num; //家庭人数
    double cnt; //家庭房子数
    double sum; //家庭房子面积
};

int n;

node a[maxn];

node ans[maxn],trans[maxn];
bool cmp(node i,node j){return ((i.sum/i.num)>(j.sum/j.num) || (i.sum/i.num==j.sum/j.num && i.aif (k==f[k]) return k;
    return f[k]=find(f[k]);
}

void doit(int ID,int id){int f1,f2;
    f1=find(ID);
    f2=find(id);
    if (f1==f2) return;
    else if (f1>f2) f[f1]=f2;
    else f[f2]=f1;
}

int main(){for (int i=1; i<=maxn; i++) f[i]=i;
    
    cin>>n;
    for (int i=1; i<=n; i++){int id;
        cin>>id;
        int ID;
        for (int j=1; j<=2; j++){cin>>ID;
            a[i].f[j]=ID;
            if (ID==-1) continue;
            doit(ID,id);
        }
        int k;
        cin>>k;
        a[i].s_num=k;
        for (int j=1; j<=k; j++){cin>>ID;
            a[i].s[j]=ID;
            doit(ID,id);
        }
        
        a[i].a=id;
        cin>>a[i].cnt>>a[i].sum;
    }

    for (int i=1; i<=n; i++){int fa=find(a[i].a);
        
        int to;
        to=a[i].a;
        if (!book[to]){ans[fa].num++;
            book[to]=1;

        }
        for (int j=1; j<=2; j++){to=a[i].f[j];
            if (!book[to] && to!=-1){ans[fa].num++;
                book[to]=1;

            }            
        }
        for (int j=1; j<=a[i].s_num; j++){to=a[i].s[j];
            if (!book[to]){ans[fa].num++;
                book[to]=1;

            }            
        }
        ans[fa].cnt+=a[i].cnt;
        ans[fa].sum+=a[i].sum;       


    }

    for (int i=0; i<=9999; i++)
        ans[i].a=i;
    int cntt=0;
    for (int i=0; i<=9999; i++){if (ans[i].num) cntt++,trans[cntt]=ans[i];
    }
    cout<printf("%04d",trans[i].a);
            cout<<" "<

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


网站题目:PTA天梯赛day2-创新互联
新闻来源:http://cqcxhl.cn/article/gdpes.html