专栏文章

题解：P3542 [POI 2012] PEN-Salaries

hhuangenning
P3542题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3mgwy
此快照首次捕获于
2025/12/02 12:49
3 个月前
此快照最后确认于
2025/12/02 12:49
3 个月前
查看原文

题目思路

自己造几棵树后可发现，每个结点都有最大可能权值。这个最大可能权值取决于其父亲的权值以及其它点是否占用某些权值。设第 ii 个点的最大可能权值为 r[i]r[i]。可以决定每个点的权值是否唯一只需要看最大权值在 r[i]r[i] 以内的结点个数是否刚好等于 nn（如果 ≠n≠n 即表示有滑动空间）以及最大权值等于 r[i]r[i] 的个数是否等于 11（若 ≠1≠1 则有两数可互换位置）即可。
有了这个思路后，我们可以先做一次从根部开始的 dfs 求所有 r[i]r[i], 对于每个点，如果其已有 z[i]z[i]，则 r[i]=z[i]r[i]=z[i]；否则应为其父节点最大权值-1（即 r[i]=r[p[i]]−1r[i]=r[p[i]]-1）, 接着如果现在的 r[i]r[i] 已经有某个 zz 占了，r[i]r[i] 应该一直减，直到未被任何 zz 占领。然后用 s[i]s[i] 求出最大权值 ≤i≤i 的点数量。对于每个点，若 s[r[i]]−s[r[i]−1]=1s[r[i]]-s[r[i]-1]=1 且 s[r[i]]=r[i]s[r[i]]=r[i] 即可确定其唯一权值为 r[i]r[i]，否则无法确定。

丑陋代码

CPP
#include<iostream>
#include<cstdio>
using namespace std;
const int NR=1000001;
bool f[NR];
int cnt,p[NR],z[NR],r[NR],s[NR],hed[NR],nxt[2*NR],to[2*NR];
void ad(int u,int v)
{
	cnt++;
	to[cnt]=v;
	nxt[cnt]=hed[u];
	hed[u]=cnt;
	return;
}
void dfs(int x)
{
	if(z[x]) r[x]=z[x];
	else
	{
		r[x]=r[p[x]]-1; 
		while(f[r[x]]) r[x]--;
	}
	s[r[x]]++;
	int i;
	for(i=hed[x];i;i=nxt[i]) dfs(to[i]);
	return;
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int n,i,fa;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>p[i]>>z[i];
		if(p[i]==i)
		{
			z[i]=n;
			fa=i;
		}
		else ad(p[i],i);
		f[z[i]]=true;
	}
	dfs(fa);
	for(i=1;i<=n;i++) s[i]+=s[i-1];
	for(i=1;i<=n;i++)
		if(!z[i] && s[r[i]]-s[r[i]-1]==1 && s[r[i]]==r[i]) z[i]=r[i];
	for(i=1;i<=n;i++) cout<<z[i]<<endl;
	return 0;
}

注意事项

1、题目未说明，所以可能存在所有点输入的 z[i]z[i] 都等于 00 的情况，此时需对根节点进行 z[i]z[i] = nn, 否则会 RTE。
2、输入量较大，若不进行输入优化，会 TLE 掉一个测试点。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...