J 模拟 T3 TLE 90 求助

复赛CSP-J/S模拟赛讨论
21

@金杭东 @陶荣杰1 大佬能教下 T4 的思路吗？题解看不懂 :roll_eyes:

1 个赞
22

我的思路和题解的不太一样。
先预处理一数组表示这个人反馈的是同意还是不同意（dfs解决）。
再预处理两个数组表示让这个人的反馈变成1和变成0要多少代价（dfs解决）。
最后计算代价，我们发现目标是让他的所有儿子意见为1和0数量相同那么（dfs解决）。
核心是三个dfs

void dfs_com(int x)
{
	int a0=0,a1=0;
	for(auto i:v[x])
	{
		dfs_com(i);
		if(com[i]) a1++;
		else a0++;
	}
	if(a1>a0) com[x]=1;
	if(a0>a1) com[x]=0;
	if(a1==a0) com[x]=a[x];
}
void price_01(int x)
{
	int a0=0,a1=0;
	for(auto i:v[x])
	{
		price_01(i);
		if(com[i]) a1++;
		else a0++;
	}
	if(a0==0&&a1==0)
	{
		if(a[x]) p1[x]=0,p0[x]=b[x];
		else p0[x]=0,p1[x]=b[x];
		return;
	}
	vector<int>tmp;
	if(com[x])
	{
		p1[x]=0;
		tmp.push_back(a[x]?b[x]:0);
		for(auto i:v[x])
		if(com[i]) tmp.push_back(p0[i]);
		sort(tmp.begin(),tmp.end());
		for(int i=0;i<=(a1+a0)/2-a0;++i) p0[x]+=tmp[i];
	}
	else
	{
		p0[x]=0;
		tmp.push_back(a[x]?0:b[x]);
		for(auto i:v[x])
		if(!com[i]) tmp.push_back(p1[i]);
		sort(tmp.begin(),tmp.end());
		for(int i=0;i<=(a1+a0)/2-a1;++i) p1[x]+=tmp[i];
	}
}
void dfs(int x)
{
	int a0=0,a1=0;
	for(auto i:v[x])
	{
		dfs(i);
		if(com[i]) a1++;
		else a0++;
	}
	if(a0!=a1)
	{
		vector<int>tmp;
		if(a0<a1)
		{
			for(auto i:v[x])
			if(com[i]) tmp.push_back(p0[i]);
			sort(tmp.begin(),tmp.end());
			for(int i=0;i<(a1+a0)/2-a0;++i) price[x]+=tmp[i];
		}
		if(a1<a0)
		{
			for(auto i:v[x])
			if(!com[i]) tmp.push_back(p1[i]);
			sort(tmp.begin(),tmp.end());
			for(int i=0;i<(a1+a0)/2-a1;++i) price[x]+=tmp[i];
		}
	}
	else price[x]=0;
}
1 个赞
23

震惊！！！

image
image1920×943 122 KB

24

S 组开始了，你们报名了吗，我闲得慌报名了，要扣积分了

25

我也这么想的，就是不会写 :grinning:

26

我 T1 69 行，一道普通的模拟题给整出大模拟的感觉。

1 个赞