2019CSP-J模拟赛A
郁闷的记者题目描述输入输出题解（结构体）
最轻的天平题目描述输入输出题解
郁闷的记者
题目描述
你是一个体育报社的记者，你接受到一个艰难的任务：有N支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从1到N。 以下是给你的一些信息：
没有平局；不同的球队排名不能相同；a打败b,则a排在b的前面。 给你部分比赛结果，要求给出可能的排名，排名按照字典序，并且判断是否存在另一种排名方法满足给你的比赛结果。
输入
第一行输入N(1<=N<=5000),表示球队的数量，编号为1到N。第二行输入 M(1<=M<=100,000),表示给出的比赛场数，接下来M行，每行两个整数)X_i,Y_i,表示X_i打败Y_i。
输出
输出包含N+1行，前N行描述球队的排名，第i个数表示第i名的球队，第N+1行包含一 个整数，如果为0表示不存在其他的排名方法，否则为1表示还有其他的排名方法。
题解（结构体）
#include <bits/stdc++.h>
using namespace std;
struct p{
int score,id;
bool lost_by[10005]={0};
}kkk[10005];
int n,m,x,y;
bool can=false;
bool cmp(p a,p b){
if(a.score==b.score){
if(b.lost_by[a.id]) return true;
else if(a.lost_by[b.id]) return false;
else return a.id<b.id;
}
return a.score>b.score;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i) kkk[i].id=i;
for(int i=1;i<=m;++i){
cin>>x>>y;
kkk[y].lost_by[x]=true;
kkk[x].score++;
kkk[y].score--;
}
sort(kkk+1,kkk+n+1,cmp);
for(int i=1;i<=n;++i)
printf("%d\n",kkk[i].id);
for(int i=1;i<=n;++i){
if(kkk[i].score==kkk[i-1].score){
if(!kkk[i-1].lost_by[kkk[i].id] && !kkk[i].lost_by[kkk[i-1].id]) can=true;
}
}
cout<<can;
return 0;
}
最轻的天平
题目描述
天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情况和他们之间的连接关系，要求使得所有天平都能平衡所需物品的总重量最轻，一个天平平衡当且仅当’左端点的重量左端点到支点的距离=右端点的重量右端点到支点的距离.注意题目中的输入保证这些天平构成一个整体。
输入
第一行包含一个N(N<=100),表示天平的数量，天平编号为1到N,接下来包含N行描述天平 的情况，每行4个数据P,Q,R,B, P和Q表示横杆上支点到左边的长度与到右边的距离的比 例为P ：Q , R表示左边悬挂的情况，如果R=0表明悬挂的物品，否则表示左边悬挂的是 天平R 号; B表示右边的悬挂情况，如果B=0表示悬挂的是物品，否则右边悬挂着天平 B号。对于所有的输入，保证W*L<2^31,其中W为最轻的天平重量，而L为输入中描述左 右比例时岀现的最大值。
输出
输出一个整数使得所有天平都平衡所需的最轻的物品总重量。 数据范围：40%的数据 N<=5 100%的数据 N<=100
题解
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
ll p,q,r,b;
}a[111];
int n,root;
ll f[111];
bool p[111];
ll gcd(ll a,ll b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
ll dfs(int x){
int l=a[x].r,r=a[x].b;
ll lans=1,rans=1;
if(l) lans=dfs(l);
if(r) rans=dfs(r);
ll ans=lans*a[x].p*rans*a[x].q/gcd(lans*a[x].p,rans*a[x].q);
return ans/a[x].p+ans/a[x].q;
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i].p>>a[i].q>>a[i].r>>a[i].b;
p[a[i].r]=true;
p[a[i].b]=true;
}
for(int i=1;i<=n;++i){
if(!p[i]){
root=i;
break;
}
}
cout<<dfs(root);
return 0;
}
