[树上倍增][贪心][数据性质] codeforces 980E The Number Games

评论区大佬:嗯这个题贪心很明显啦然后nlogn方法也有很多种

http://codeforces.com/contest/980/problem/E

要使得去掉一些点之后剩下的仍然是一棵树,那么去掉的一定是叶子或者某条路上的缩点后相当于叶子的子图。。描述有点困难自行yy。。然后如何选择去掉的点?可以发现,如果i<j,那么去掉j一定不如去掉小于j的所有数,因为2^j=2^(j-1)+2^(j-2)+2^(j-3)+…..+2+1,所以贪心策略就是能不去掉大的就不去,所以要从n-1开始一个一个找(由于k<n所以节点n一定不会被去掉),怎么确定一个点是否能被保留下来,只要确定这个点到最近的保留下来的点的距离小到可以满足去掉k个的要求(想一下,如果这个点离最近的保留点太远了,远到了如果保留这个就没法保证能去掉k个点了,那就肯定不能留了),要保留这个点一定也要保留从这个点往上回溯所有的点,然后就会发现在以root为根的树上,这个01标志是连续的分布的,也就是说有一段1111然后一段000,这样的话就可以二分求分界点,而树上的二分就是lca里的倍增算法了,用倍增法查找就可以在logn时间内找到分界点,找到之后判断是否满足要求,如果满足则把分界点到当前点都标记上保留(话说这样logn不就退化了吗。。。)

wa点是距离的处理和树上倍增往前跳的时候把cur写成了i。。。

#include

using namespace std;
typedef long long LL;
const int maxn=1e6+5e4+5;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const int DG=21;
vector G[maxn];
int dep[maxn],fa[maxn][DG];

void BFS(int root)
{
    queueQ;
    Q.push(root);
    dep[root]=0;
    fa[root][0]=root;//
    int cur,nxt,len;
    while(!Q.empty())
    {
        cur=Q.front();Q.pop();
        for(int i=1;i0&&dis>0;i--)
    {
        if(sav[i])continue;
        cur=i;
        td=0;
        for(int m=DG-1;m>=0;m--)
        {
            if(sav[fa[cur][m]])//error!
                continue;
            cur=fa[cur][m],td+=pow2[m];
        }
        f=fa[cur][0],td++;
        if(td>dis)
            continue;

        dis-=td;
        cur=i;
        while(cur!=f)
        {
            sav[cur]=1;
            cur=fa[cur][0];
        }
    }
    for(int i=1;i<=n;i++)
        if(!sav[i])
        printf("%d ",i);
    return 0;
}
/*

*/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据