HauntedProgrammer's Blog

A said strange person

[BZOJ 3835][Poi2014]Supercomputer

HauntedProgrammer posted @ 2015年1月07日 21:00 in 未分类 , 827 阅读

这饼图被我搞得太可怕了。

鸣谢xyz111提供主要想法。 orz xyz111

首先求出每一层有多少个节点。如果一层中的个数[tex]num[i] \leq k[/tex],那么这一层可以直接一次运行完毕。如果[tex]num[i]>k[/tex],那么就开始一段,直到这一段的平均数小于等于[tex]k[/tex],对答案的贡献是[tex]\lceil\frac{sum}{k}\rceil[/tex](sum是这一段的和)。证明Under Construction,好了以后会写上来的。

然后就是求出[tex]k=1 \rightarrow n[/tex]的答案。注意到对于一个[tex]k[/tex],最多只有[tex]\frac{n}{k}[/tex]个段起始点,所有的段长度的和也最多只有[tex]\frac{n}{k}[/tex],所以使用链表维护段起始点可以做到[tex]O(nlog(n))[/tex]的时间复杂度。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#define MAXN 1000010
int n,ki[MAXN],nums[MAXN],fa[MAXN],q,dep[MAXN],maxd=0,ans[MAXN];
std::vector<int> depn[MAXN];
int nex[MAXN],prv[MAXN],head=0;
inline void rm(int x){head=(head==x)?nex[x]:head,nex[prv[x]]=nex[x],prv[nex[x]]=prv[x];}
inline int ceildv(int x,int y){return x/y+(x%y!=0);}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=0;i<q;i++) scanf("%d",&ki[i]);
	for(int i=2;i<=n;i++) scanf("%d",&fa[i]);
	dep[1]=head=1;
	for(int i=2;i<=n;i++) dep[i]=dep[fa[i]]+1,maxd=std::max(maxd,dep[i]);
	for(int i=1;i<=n;i++) nums[dep[i]]++;
	for(int i=1;i<=maxd;i++) depn[nums[i]].push_back(i);
	for(int i=1;i<=maxd;i++) nex[i]=i+1,prv[i]=i-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0,len=depn[i].size();j<len;j++) rm(depn[i][j]);
		int cur=0,elaps=0,last=0,tot=0;
		for(int j=head;j&&j<=maxd;j=nex[j]) if(j>last)
		{
			for(int k=j;k<=maxd;k++)
			{
				cur+=nums[k],elaps++;
				if(cur<=elaps*i){ans[i]+=ceildv(cur,i),tot+=elaps,elaps=cur=0,last=k;break;}
			}
			if(elaps) ans[i]+=ceildv(cur,i),tot+=elaps,last=maxd;
		}
		ans[i]+=(maxd-tot);
	}
	printf("%d",ki[0]>n?maxd:ans[ki[0]]);
	for(int i=1;i<q;i++) printf(" %d",ki[i]>n?maxd:ans[ki[i]]);
	printf("\n");
	return 0;
}


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter