题解洛谷 P3571 【[POI2014]SUP-Supercomputer】

由数据范围可得出，不可能一次一次去进行回答询问，只能离线处理，然后\(O(1)\)解决。

考虑\(DP\)解决，先给出\(DP\)方程：

\(f_i=max(j+ \lceil \frac{s_{j+1}}{i} \rceil)\) (\(f_i\)表示为当前一次操作最多访问\(i\)个未访问的点的最小操作次数，\(s_i\)表示表示深度\(\geqslant i\)的节点个数)

式子右边的含义为前\(j\)次操作访问完前\(j\)层节点，后面每次都访问\(i\)个节点，可以发现这样的操作是最优的。若从贪心的角度来看，每次操作一定是尽量访问更多的点，若此时有额外的点可供选择，优先访问有儿子的节点，为以后操作保证最优性提供保障。

先感性地证明这个式子的正确性，也就是这个地方为什么取\(max\)。

① 若我们无法做到前\(j\)次操作访问完前\(j\)层节点，假设存在\(k\)，可以做到前\(k\)次操作访问完前\(k\)层节点。可以发现第\(k\)层在第\(j\)层上面，那么在\(k\)层到\(j\)层的节点，我们无法做到通过\(j-k\)次操作全部访问完，可以得出式子：

\(\lceil \frac{s_{k+1}-s_{j+1}}{i} \rceil>j-k\)

变形得：

\(k+\lceil \frac{s_{k+1}}{i} \rceil>j+\lceil \frac{s_{j+1}}{i} \rceil\)

发现合法状态\(k\)比不合法状态\(j\)操作次数要多，所以通过取\(max\)可以去除\(j\)这种不合法情况。

② 若我们无法做到前\(j\)次操作访问完前\(j\)层节点时后面每次都访问\(i\)个节点，假设存在\(k\)，可以做到前\(k\)次操作访问完前\(k\)层节点时后面每次都访问\(i\)个节点。可以发现第\(k\)层在第\(j\)层下面，那么可以做到每次都访问\(i\)个节点的层数会变小，所以合法状态\(k\)会比不合法状态\(j\)操作次数多。

由这两种情况，我们就可以得出，为了保证状态合法，转移时应取\(max\)。

设合法状态\(j,k\)，假设状态\(j\)比状态\(k\)更优。

即\(j+ \lceil \frac{s_{j+1}}{i} \rceil>k+ \lceil \frac{s_{k+1}}{i} \rceil\)

\(\lceil \frac{s_{j+1}-s_{k+1}}{i} \rceil>k-j\)

\(\frac{s_{j+1}-s_{k+1}}{j-k}<-i\)

发现我们可以用斜率优化来优化复杂度，这里\(x\)为\(j\)，\(y\)为\(s_{j+1}\)，斜率为\(-i\)。

其他的一些实现细节就看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 1000010

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag)x=-x;

}

int n,m,h,t;

ll deep_max,query_max;

ll f[maxn],s[maxn],q[maxn],query[maxn];

struct edge

{

    int to,nxt;

}e[maxn];

int head[maxn],edge_cnt;

void add(int from,int to)

{

    e[++edge_cnt]=(edge){to,head[from]};

    head[from]=edge_cnt;

}

double x(int i)

{

    return i;

}

double y(int i)

{

    return s[i+1];

}

double slope(int j,int k)

{

    return (y(j)-y(k))/(x(j)-x(k));

}

void dfs(int x,ll dep)

{

    s[dep]++;

    deep_max=max(deep_max,dep);

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        dfs(y,dep+1);

    }

}

int main()

{

    read(n),read(m);

    for(int i=1;i<=m;++i)

        read(query[i]),query_max=max(query_max,query[i]);

    for(int i=2;i<=n;++i)

    {

        int fath;

        read(fath),add(fath,i);

    }

    dfs(1,1);

    for(int i=deep_max;i;--i) s[i]+=s[i+1];

    for(int i=1;i<=deep_max;++i)

    {

        while(h<t&&slope(q[t],i)>slope(q[t],q[t-1])) t--;

        q[++t]=i;

    }

    for(int i=1;i<=query_max;++i)

    {

        while(h<t&&slope(q[h],q[h+1])>-i) h++;

        int j=q[h];

        f[i]=j+(s[j+1]+i-1)/i;

    }

    for(int i=1;i<=m;++i) printf("%lld ",f[query[i]]);

	return 0;

}

巴特西

题解洛谷 P3571 【[POI2014]SUP-Supercomputer】

最新文章

热门文章

巴特西

题解 洛谷 P3571 【[POI2014]SUP-Supercomputer】

最新文章

热门文章

题解洛谷 P3571 【[POI2014]SUP-Supercomputer】