社区讨论

蒟蒻代码求调,不求满分,只求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 条回复,欢迎继续交流。

正在加载回复...