P3571 [POI2014]SUP-Supercomputer

*X. P3571 [POI2014]SUP-Supercomputer

题意简述:一棵以 \(1\) 为根的树。\(q\) 次询问,每次给出 \(k\),求至少要多少次同时访问不超过 \(k\) 次父节点已经被访问过的节点,才能访问完整棵树。根节点无限制。

\(n,q\leq 10^6\)。

节选自 DP 优化方法大杂烩 7. 斜率优化例题 X。

sweet tea.

主要讲一下怎么用斜率优化,取 \(\max\) 的正确性别的题解说明得已经很好了。

对于每一个 \(k\),一定存在 \(i\) 使得深度不大于 \(i\) 的节点用 \(i\) 次访问,且深度大于 \(i\) 的节点每次都能访问 \(k\) 个(除了最后一次)。记 \(s_i\) 表示深度不小于 \(i\) 的节点个数,答案即为 \(\max_{i=1}^d\left(i+\lceil\dfrac{s_{i+1}}k\rceil\right)\),其中 \(d\) 是最大深度。

若 \(i\) 是最优决策,那么对于任意一个 \(j\neq i\),有 \(i+\lceil\dfrac{s_{i+1}}k\rceil\geq j+ \lceil\dfrac{s_{j+1}}k\rceil\)。略作变形得到 \(i-j \geq \lceil\dfrac{s_{j+1}-s_{i+1}}k\rceil\)。令横坐标为深度,纵坐标为 \(s_{x+1}\),再写成斜率的形式,即当 \(j<i\) 时,\(\dfrac{s_{i+1}-s_{j+1}}{i-j}\geq -k\),当 \(j>i\) 时,\(\dfrac{s_{i+1}-s_{j+1}}{i-j}\leq -k\)。不难看出这是一个上凸包的形式,即斜率递减

具体地,我们对 \((i,s_i)\) 建出上凸包,然后当 \(k\) 递增时,\(-k\) 递减,顶点会向横坐标大的方向移动,用指针维护即可。时间复杂度 \(\mathcal{O}(n)\)。

经过卡常拿到了最优解。

const int N=1e6+5;

int n,q,mxd,mxq,dep[N],f[N],qu[N];
int d[N],hd=1,tl;
ll s[N];

int main(){
	cin>>n>>q,dep[1]=s[1]=1;
	for(int i=1;i<=q;i++)mxq=max(mxq,qu[i]=read());
	for(int i=2,a;i<=n;i++)mxd=max(mxd,dep[i]=dep[read()]+1),s[dep[i]]++;
	for(int i=mxd-1;i;i--)s[i]+=s[i+1];
	for(int i=0;i<=mxd;i++){
		while(hd<tl&&(s[d[tl]+1]-s[d[tl-1]+1])*(i-d[tl])<=(s[i+1]-s[d[tl]+1])*(d[tl]-d[tl-1]))tl--;
		d[++tl]=i;
	}
	for(int i=1;i<=mxq;i++){
		while(hd<tl&&s[d[hd+1]+1]-s[d[hd]+1]>-i*(d[hd+1]-d[hd]))hd++;
		f[i]=d[hd]+(d[hd]==mxd?0:((s[d[hd]+1]-1)/i+1));
	}
	for(int i=1;i<=q;i++)print(f[qu[i]]),pc(' ');
	return flush(),0;
}
上一篇:質問力 D


下一篇:#2466. 「POI2014」卡片 Card