BZOJ 3835 Supercomputer

VictorWonder posted @ 2015年2月12日 06:43 in BZOJ with tags 解题报告 斜率优化 推导证明 , 1277 阅读
好久没有发题解了,主要是期末考的缘故,一直没有时间做题,然后最近又来了WC,也几乎没有时间做题,今天,正好有一道题目会做了一半(主要是一个结论的证明),就先发上来了,在考试前攒一下RP。
 
这道题目是Claris推荐给我的,那个时候,google突然能够上了,Claris就搜到了一个波兰人的blog,里面有关于这道题目的结论,结论是:[tex]ans=\max(i+\lceil\frac{sum[i]}{k} \rceil)[/tex],其中,i是指第i层(深度为i),sum[i]是指深度大于i的结点的个数。
那个波兰人的blog里面有证明,不过证明是图片格式的,学校网速差不能看,后来google上不去了,就更不能看了。Claris自己没有办法证明,但还是根据这个规律AC了这道题目。这一次WC,和我同寝室的zhw大神正好也AC了这道题目,然后Claris就怂恿我去问zhw大神这道题,zhw大神的做法是一样的,不过他给出了简略证明,其中有一句话极其重要:“当第i层之后,每一次都能取k个结点,那么这个式子就成立了。而符合这样要求的一层肯定是存在的。”
因为BZOJ挂了,这道题目暂时看不到,不过可以去Main上看英文版本的,题目大意就是,有一棵一百万结点的树,每一次可以查询k个结点,一个结点可以被查询,当且仅当其父结点被查询了,那么第一次只能查询根结点。现在,询问对于一个k,最少需要查询对少次才能将所有结点都查询一遍。
我们首先里证明后面半句:这样的一层必然是存在的。首先,如果总层数为h,每一层的结点都小于k,那么我们就需要查询h次,符合要求的那一层(我将其命名为关键层)就是h层。
那如果有一层(假设为第x层)的结点个数大于k,我们该怎么做?首先,当然是查询这一层的k个结点,至于剩下的结点,我们就不用管它,我们下一次查询的时候,继续查询下一层,如果下一层的结点个数大于k,我们也只查询其中的k个结点,否则,我们查询了这一层的t个结点之后,在第x层找到x-t个未被查询的结点查询,接下来就只有两种情况:1、每次都可以查询一层,且从某一层(比如说上面说的x层)将不足的结点查询完,那么x-1层就是关键层,我们的公式自然成立。2、从第y+1层开始,多余的结点查询完了,每一层的节点个数再次不足k个,很明显,这个时候我们就正好查询了y次,x和y都不是关键层,但是没有关系,如果接下来都是这样的话,第h层就是关键层。
实际情况自然要更加复杂,但是都离不开这两种情况。所以,我们必然能够找到一个关键层使得我们找到的结论成立。
那么,为什么要求max且对每一层都用这个公式求一下?我们发现,如果一层并不是关键层,但是我们把其当作关键层来看,也就是说,接下来每一次都可以查询k个结点,但实际上,我们接下来不可能每次都查询k个结点,这样的话,理论的查询次数小于等于实际的查询次数,所以,必然小于最后的答案,至于max,这是显然的。因为我们可以发现,关键层有且仅有一层,其他层用这个公式求出来的答案必然小于关键层求出的答案。
以上就是关于这个结论的证明,剩下的就是程序实现了。
但是在程序实现的过程中还是有一些问题,因为这题需要进行一百万次查询,如果每次我们都查询这么多层的话,肯定是会超时的,毕竟深度最多可能有一百万。但是,我们先忽略向上取整和k的值,整个式子就可以转化成斜率的式子了,用队列存下可能成为解的情况,之后再从小到大依次枚举k,最多枚举到n,因为k可能是很大的数,而且,当k>n之后,答案就是整棵树的深度了。这样做的复杂度明显是O(1)的。
//ans=max(i+sum[i]/k)
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1000100;
int n,m,p[N];
int fa[N],f[N],d[N],ans[N];
int st[N],L,R,deep=1;
bool ok(int i,int j,int k) { return (ll)(f[k]-f[j])*(i-j)>=(ll)(f[j]-f[i])*(j-k);}
void read(int &a) {
    char ch; while (!((ch=getchar())>='0'&&ch<='9'));
    a=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') (a*=10)+=ch-'0';
}
int main() {
    int i,j;
    read(n); read(m); f[d[1]=0]=deep=1;
    for (i=1;i<=m;i++) read(p[i]);
    for (i=2;i<=n;i++) {
        read(fa[i]);
        d[i]=d[fa[i]]+1; f[d[i]]++;
        if (d[i]>=deep) deep=d[i]+1;
    }
    for (i=deep;~i;i--) f[i]=f[i]+f[i+1];
    for (i=deep;~i;i--) {
        while (R>1&&ok(st[R-1],st[R],i)) R--;
        st[++R]=i;
    }
    for (L=1,i=n;i;i--) {
        while (L<R&&(ll)i*(st[L]-st[L+1])<=f[st[L+1]]-f[st[L]]) L++;
        if (f[st[L]]%i==0) ans[i]=st[L]+f[st[L]]/i;
        else ans[i]=st[L]+f[st[L]]/i+1;
    }
    for (i=1;i<m;i++) if (p[i]>n) printf("%d ",deep);
    else printf("%d ",ans[p[i]]);
    if (p[i]>n) printf("%d\n",deep);
    else printf("%d\n",ans[p[i]]);
    return 0;
}

 


登录 *


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