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://cdkjz.cn/article/gdpes.html
