BZOJ 3835 Supercomputer

VictorWonder posted @ 2015年2月12日 06:43 in BZOJ with tags 解题报告 斜率优化 推导证明 , 2174 阅读
好久没有发题解了,主要是期末考的缘故,一直没有时间做题,然后最近又来了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;
}

 

CGBSE 12th Question 说:
2022年9月05日 20:07

CG Board Model Paper 2023 Class 12 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. CGBSE 12th Question Paper New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Emma 说:
2023年1月22日 22:07

It's great to see you've been active in the WC community again! I'm sure you're feeling relieved to have finished your final exams and have a bit of extra time to work on some of the questions you've been wanting best online engagement rings store to tackle! I'm especially impressed that you managed to solve BZOJ 3835 Supercomputer and post it before your exams. It seems like Claris was a great help, finding a Polish blog that gave a conclusion about this topic. It's always beneficial to have a partner in crime to help us out when we're in a tough spot. Congratulations on your hard work and success!


登录 *


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