CF 1039D You Are Given a Tree && CF1059E Split the Tree 的贪心解法[通俗易懂]

CF 1039D You Are Given a Tree && CF1059E Split the Tree 的贪心解法[通俗易懂]CF 1039D You Are Given a Tree && CF1059E Split the Tree 的贪心解法

大家好,又见面了,我是你们的朋友全栈君。

1039D 题意:

给你一棵树,要求对给定链长于 k = 1, 2, 3, …, n,求出最大的链剖分。

1059E 题意:

给你一棵带权树,要求对于一组给定的 L, W 求出最小完全竖链剖分满足每条链点数不超过 L,权值和不超过 W。

显然两题是有共同点的,就是让我们求满足一定条件的树的最值链剖分。

比较暴力的可以尝试用 DP 计数,但是我不想深入 DP,因为方程比较复杂,思考起来不太容易。

很巧的是,这两题可以用相似的贪心思想来做。

在思考具体细节之前,需要明确贪心的主要思想:在从下往上回溯的过程中,总是在合适条件下贪心地成链。

1039D 

如果对于给定的 k 值可以快速求解,就可以用分块的思想处理 k 不同时的情况。

怎样求解给定的 k 呢?

还是贪心的做法。

在 dfs 回溯过程中,一旦当前点可以成链,就直接钦定下来 :)

具体操作过程中,需要对每个点记录最长与次长子链,这样一旦两者和达到 k,就可以成链了。

证明略。

#include <bits/stdc++.h>

using namespace std;

const int N = 100000 + 5;
const int BLOCK = 100;

int n;
int f[N][2];
vector<int> node;
vector<int> g[N];
int fa[N];

void dfs(int u, int f = 1) {
  for (auto v: g[u]) {
    if (v != f) {
      dfs(v, u);
    }
  }
  node.push_back(u);
  fa[u] = f;
}

int solve(int k) {
  for (int i = 1; i <= n; i++) {
    f[i][0] = f[i][1] = 0;
  }
  int ret = 0;
  for (int u: node) {
    if (f[u][0] + f[u][1] + 1 >= k) {
      ret++;
    } else {
      if (f[fa[u]][0] < f[u][0] + 1) {
        f[fa[u]][1] = f[fa[u]][0];
        f[fa[u]][0] = f[u][0] + 1;
      } else {
        f[fa[u]][1] = max(f[fa[u]][1], f[u][0] + 1);
      }
    }
  }
  return ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  int x = N, k = 1;
  while (x > BLOCK) {
    x = solve(k++);
    printf("%d\n", x);
  }
  for (int i = BLOCK; i >= 0; i--) {
    if (solve(k) != i || k > n) {
      continue;
    }
    int l = k, r = n + 1;
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (solve(mid) == i) {
        l = mid;
      } else {
        r = mid;
      }
    }
    while (k <= l) {
      printf("%d\n", i);
      k++;
    }
  }
  return 0;
}

1059E

与上题不同的是,这题的链要求是竖直的,考虑从链底做贪心。

对于每个点,关注每条从子节点过来的链,并且贪心的选择将当前点并入终点最高的链上。

如果没有这样的链,就直接根据题目条件选择最高的链。

#include <bits/stdc++.h>

using namespace std;

const int N = 100000 + 5;

int up[N];
int dep[N], path[N];
int fa[N][21];
int n, L;
int w[N];
long long S;
long long sumw[N];
vector<int> g[N];

void prepare(int u, int f = 0) {
  dep[u] = dep[f] + 1;
  sumw[u] = sumw[f] + w[u];
  up[u] = u;
  fa[u][0] = f;
  for (int i = 1; i <= 20; i++) {
    fa[u][i] = fa[fa[u][i-1]][i-1];
  }
  int lim = L-1;
  for (int i = 20; i >= 0; i--) {
    if (fa[up[u]][i] != 0 && (1 << i) <= lim && sumw[u] - sumw[fa[fa[up[u]][i]][0]] <= S) {
      up[u] = fa[up[u]][i];
      lim -= (1 << i);
    }
  }
  for (int v: g[u]) {
    prepare(v, u);
  }
}

int solve(int u) {
  int ret = 0, best = -1;
  for (int v: g[u]) {
    ret += solve(v);
    if (path[v] != v) {
      if (best == -1 || dep[path[v]] < dep[best]) {
        best = path[v];
      }
    }
  }
  if (best == -1) {
    ret++;
    best = up[u];
  }
  path[u] = best;
  return ret;
}

int main() {
  scanf("%d %d %lld", &n, &L, &S);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &w[i]);
    if (w[i] > S) {
      printf("-1\n");
      return 0;
    }
  }
  for (int i = 2; i <= n; i++) {
    int p;
    scanf("%d", &p);
    g[p].push_back(i);
  }
  prepare(1);
  printf("%d\n", solve(1));
  return 0;
}

转载于:https://www.cnblogs.com/HailJedi/p/9774769.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107263.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 电力-101/104规约基础1

    电力-101/104规约基础1内容包括IEC101/104规约术语及释义(嵌入实际工程C代码),IEC101/104规约标准与遥测量类型转换介绍,IEC101规约遥信、遥测与遥控及加密。

  • 【mysql】索引优化

    【mysql】索引优化【mysql】索引优化

  • android galley实现画廊效果

    android galley实现画廊效果青春流水指间、每段路,都有即将要来的旅程每颗心,都有值得期待的成分Android之ImageSwitcher,Gallery用法今天在做一个软件界面时用到了ImageSwitcher和Gallery控件,在看API时,感觉上面的例子讲的不是很具体,效率并不高。在这里我就以一个图片浏览功能来具体说明这两个控件的用法。首先看运行效果:在这里图片我用的是API中的图

  • 单片机定时器实验报告C语言,51单片机定时器实验报告.doc

    单片机定时器实验报告C语言,51单片机定时器实验报告.doc51单片机定时器实验报告51单片机定时器实验报告51单片机定时器实验实验内容:实验内容:编写程序使定时器0或者定时器1工作在方式1,定时50ms触发蜂鸣器。C语言程序#include#defineuintunsignedint#defineucahrunsignedcharsbitFM=P0^0;voidmain(){TMOD=0x01;TH0=(65535-50000)/256;…

  • 云端呼叫中心坐席并发测试结果[通俗易懂]

    云端呼叫中心坐席并发测试结果[通俗易懂]很久没有写关于asterisk压力测试的相关文章了。今晚终于可以抽一点时间来写点东西,跟大家来分享一下。以下是本人最近开发的一套云端虚拟坐席租用系统,历经半年时间的实现和优化。          在近段时间,云端服务器是一个比较很热门话题,并且很大程度上综合硬件的资源的,节约成本的同时,还有的好处就是简化服务器部署的难度和时间。其他关于云端服务的其他好处,在此不必多说了,大家可以参考一

  • 风云私服架设教程_风云端游

    风云私服架设教程_风云端游需要软件:SQLsever2005pro本站提供下载将服务器端解压缩到D:盘D:\Sagasevr下有6个文件夹1:databaseSQL数据库文件夹2:LoginServer帐号登陆管理器3:WorldServer服务器数据管理器4:GameServer1游戏数据管理器4:GameServer2游戏数据管理器5:GameServer3游戏数据管理器6:GameS…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号