重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
对于两个数,先通分分母,再将分子乘上相应的倍数。
可通过__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<
可定义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用法
参考题解
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
并查集,每个人所记录的父节点是当前集合中最小的编号数。用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元起,快前往官网查看详情吧