原文链接https://www.cnblogs.com/zhouzhendong/p/9074226.html

题目传送门 - Codeforces 980E

题意

　　$\rm Codeforces$ 真是个令人伤心的地方。

　　伤心的 $zzd$ 给你一个有 $n$ 个节点的树，编号为 $i$ 的节点权值为 $2^i$。

　　让你砍掉其中 $k$ 个节点，使得剩余的所有节点都连通，并最大化剩余节点的权值和。输出方案。

　　$n\leq 10^6$

题解

　　伤心的 $zzd$ 再一次来到了令人伤心的 $\rm Codeforces$，并开心的 $9$ 分钟敲完并 $AC$ 了此题，并再一次伤心地发现这是在 $vp$ 结束后的第 $4$ 分钟。

　　我们考虑选择一颗子树，使得剩余节点的权值和最大。

　　显然我们可以贪心编号从大到小选择，能选就选。

　　考虑当前选出的子树状态为 $S$，下一个决策为节点 $i$ ，那么，新增的节点数就是节点 $i$ 到 $S$ 的距离。

　　只要新增之后不超出限制就可以了。

　　这个东西可以预处理倍增表来快速搞定。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1000005;

struct gragh{

	int cnt,y[N*2],nxt[N*2],fst[N];

	void clear(){

		cnt=0;

		memset(fst,0,sizeof fst);

	}

	void add(int a,int b){

		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;

	}

}g;

int n,lim,depth[N],fa[N],anst[N][21];

int vis[N],tot=0,ans[N];

void dfs(int x,int pre){

	fa[x]=anst[x][0]=pre;

	depth[x]=depth[pre]+1;

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

		anst[x][i]=anst[anst[x][i-1]][i-1];

	for (int i=g.fst[x];i;i=g.nxt[i])

		if (g.y[i]!=pre)

			dfs(g.y[i],x);

}

int main(){

	scanf("%d%d",&n,&lim);

	lim=n-lim;

	g.clear();

	for (int i=1,a,b;i<n;i++){

		scanf("%d%d",&a,&b);

		g.add(a,b),g.add(b,a);

	}

	dfs(n,0);

	memset(vis,0,sizeof vis);

	vis[n]=tot=1;

	vis[0]=1;

	for (int i=n-1;i>=1;i--){

		if (vis[i])

			continue;

		int j=i;

		for (int k=20;k>=0;k--)

			if (!vis[anst[j][k]])

				j=anst[j][k];

		if (tot+depth[i]-depth[j]+1>lim)

			continue;

		tot+=depth[i]-depth[j]+1;

		vis[j]=1;

		for (int k=i;k!=j;k=fa[k])

			vis[k]=1;

	}

	tot=0;

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

		if (!vis[i])

			ans[++tot]=i;

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

		printf("%d ",ans[i]);

	return 0;

}

巴特西

Codeforces 980E The Number Games 贪心倍增表

题目传送门 - Codeforces 980E

题意

题解

代码

最新文章

热门文章

巴特西

Codeforces 980E The Number Games 贪心 倍增表

题目传送门 - Codeforces 980E

题意

题解

代码

最新文章

热门文章

Codeforces 980E The Number Games 贪心倍增表