社区讨论
蒟蒻代码求调,不求满分,只求90分(样例过了,评测全WA)
学术版参与者 4已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @lo22am9e
- 此快照首次捕获于
- 2023/10/23 06:50 2 年前
- 此快照最后确认于
- 2023/11/03 07:11 2 年前
CPP
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define in long long //本来只开int,但是发现小了,手懒#define int long long 编译过不了,所以就删了个t
using namespace std;
const int N=1000005;
in n,m,u=0;
struct Node
{
in son[6],numb,r1=0,r2=0;
bool flag=false;
}f[N];
bool pd[N];
in father[11],grandson[N];
void put_in()//输入
{
memset(pd,false,sizeof(pd));
cin>>n>>m;
for(in i=1; i<=n; i++)
{
in num;
cin>>num;
f[i].numb=num;//多少个儿子
if(num==0)
{
u++;//找到最后的点
f[i].flag=true;//存为真,为以后退出做准备
grandson[u]=i;//存
continue;//既然你没有儿子那你就别继续走了
}
for(in j=1; j<=num; j++){
cin>>f[i].son[j];//谁当过儿子,就不是最大的了
pd[f[i].son[j]]=true;
}
}
}
void find()//找祖宗
{
in y=0;
for(in i=1; i<=n; i++)
{
if(!pd[i]){
y++;
father[y]=i;
}
if(y==m) break;
}
}
in find2(in m2,in n2)
{
in r=m2%n2;
while(r!=0){
m2=n2;
n2=r;
r=m2%n2;
//if(r==0) break;
}
return n2;
}
void sum(in a,in b,in c,in d,in g)//通分求值
{
in k;
k=find2(a,b);
in t,fson,p,fmother;//f表示分,分母,分子
fmother=(a/k)*b;
t=(fmother/a)*c;
p=(fmother/b)*d;
fson=p+t;
in q=find2(fson,fmother);
fson/=q;
fmother/=q;//化为最简
f[g].r1=fson;//存下,g表示流入的点
f[g].r2=fmother;
}
void bfs(in now)
{
if(f[now].flag) return;//如果你是孙子中的孙子,那就玩完了
in o=f[now].r2*f[now].numb;//例如1/2分遗产,分母乘个2
for(in j=1; j<=f[now].numb; j++)
{
if(f[f[now].son[j]].r1!=0 && f[f[now].son[j]].r2!=0) sum(f[f[now].son[j]].r2,o,f[f[now].son[j]].r1,f[now].r1,f[now].son[j]);//求和,分类是为了避免/0
else{
f[f[now].son[j]].r1=f[now].r1;
f[f[now].son[j]].r2=o;
in op=find2(f[j].r1,f[f[now].son[j]].r2);
f[f[now].son[j]].r1/=op;
f[f[now].son[j]].r2/=op;
}
bfs(f[now].son[j]);//暴搜儿子浏览记录
}
}
void solve()
{
for(in i=1; i<=m; i++)
{
f[father[i]].r1=1;//初值
f[father[i]].r2=1;
bfs(father[i]);//从自己搜
}
}
void put_out()
{
for(in i=1; i<=u; i++)
cout<<f[grandson[i]].r1<<" "<<f[grandson[i]].r2<<endl;
}
int main()
{
//freopen("water.in","r",stdin);
//freopen("water.out","w",stdout);
put_in();
find();
solve();
put_out();
return 0;
}
蒟蒻改了一下午,下不了数据。。。。虽然学过树,但忘记咋建;bfs(我不知道我的正不正宗,考场临场发挥,蒟蒻也忘了)
回复
共 9 条回复,欢迎继续交流。
正在加载回复...