ecnuoj 5039 摇钱树

5039. 摇钱树

题目链接:5039. 摇钱树

感觉在赛中的时候,完全没有考虑分数规划这种做法。同时也没有想到怎么拆这两个交和并的式子。有点难受……

当出现分数使其尽量大或者小,并且如果修改其中直接相关的某个值会导致分子分母同时变化的时候,还是要多想想分数规划的做法。

下面引用一下题解

另外这两个交和并的式子,令 \(a = S \and T, b = T - a\),所以原来的式子变成了

\[\frac{|S \and T|}{|S \or T|} = \frac{a}{b + |S|}
\]

所以,用分数规划的做法,二分一个答案 \(ans\),则有

\[\frac{a}{b + |S|} \ge ans \implies a - b \cdot ans \ge |S|\cdot ans
\]

接下来用树上 dp 求一个最大的 \(a - b \cdot ans\) 即可。

\(f_{i,j}\) 表示此时 \(i\) 号点上选了 \(j\) 个子树加和起来最大的 \(a-b\cdot ans\) 值,\(x_{i,j}\) 表示这个式子中的 \(a\)\(y_{i,j}\) 表示这个式子中的 \(b\)

那么接下来就是一个普通的树上背包的转移了,不过区别在于转移完整个 \(f_u\) 后,需要再用取整个以 \(u\) 为根构成的一颗子树去更新一下 \(f_{u,1}\)

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;

#define IL inline
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl

template<typename Tp> IL void read(Tp &x) {
    x=0; int f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    x *= f;
}
int buf[42];
template<typename Tp> IL void write(Tp x) {
    int p = 0;
    if(x < 0) { putchar('-'); x=-x;}
    if(x == 0) { putchar('0'); return;}
    while(x) {
        buf[++p] = x % 10;
        x /= 10;
    }
    for(int i=p;i;i--) putchar('0' + buf[i]);
}

const int N = 100000 + 5;
const int M = 50 + 5;
int n, m;
int a[N], suma[N], sz[N], x[N][M], y[N][M];
db f[N][M];
vector<int> G[N];

struct fs {
    int fz, fm;
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}
    fs(int fz=0, int fm=1) {
        if(fz == 0) this -> fm = 1;
        else {
            int g = gcd(fz, fm);
            this -> fz = fz / g;
            this -> fm = fm / g;
        }
    }
};

int dfs2(int u, int fa, const db& ef_x) {
    int u_leaf = 0;
    if(u != 1 && G[u].size() == 1) {
        if(a[u] == 1) {
            f[u][1] = 1.0;
            x[u][1] = 1; y[u][1] = 0;
        }
        return ++u_leaf;
    }
    for(int i=0;i<=m;i++) f[u][i] = x[u][i] = y[u][i] = 0;
    for(int v : G[u]) {
        if(v == fa) continue;
        int v_leaf = dfs2(v, u, ef_x);
        for(int i=min(u_leaf,m);i>=0;i--) {
            for(int j=1;j<=v_leaf && i+j <= m; j++) {
                if(f[u][i] + f[v][j] > f[u][i+j]) {
                    f[u][i+j] = f[u][i] + f[v][j];
                    x[u][i+j] = x[u][i] + x[v][j];
                    y[u][i+j] = y[u][i] + y[v][j];
                }
            }
        }
        u_leaf += v_leaf;
    }
    if(suma[u] - (sz[u] - suma[u]) * ef_x >= f[u][1]) {
        f[u][1] = suma[u] - (sz[u] - suma[u]) * ef_x;
        x[u][1] = suma[u];
        y[u][1] = sz[u] - suma[u];
    }
    return u_leaf;
}

array<int, 3> check(const db& x) {
    dfs2(1, 0, x);
    int ansu = 1, ansi = 1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        if(f[i][j] > f[ansu][ansi]) {
            ansu = i; ansi = j;
        }
    }
    return {f[ansu][ansi] >= suma[1] * x, ansu, ansi};
}

void dfs1(int u, int fa) {
    suma[u] += a[u];
    sz[u] = 1;
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs1(v, u);
        suma[u] += suma[v];
        sz[u] += sz[v];
    }
}

void solve() {
    read(n); read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++) {
        int u, v; read(u); read(v);
        G[u].pb(v); G[v].pb(u);
    }
    dfs1(1, 0);
    db L = 0.0, R = 1.0;
    fs ans;
    while(R - L >= 1e-10) {
        db M = (L + R) / 2.0;
        auto arr = check(M);
        if(arr[0]) {L = M; ans = fs(x[arr[1]][arr[2]], y[arr[1]][arr[2]] + suma[1]);}
        else R = M;
    }
    write(ans.fz); putchar(32); write(ans.fm); putchar(10);
}

int main() {
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
#endif
    int T = 1;
    // read(T);
    while(T--) solve();
    return 0;
}

原文链接:https://www.cnblogs.com/bringlu/p/17284738.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:ecnuoj 5039 摇钱树 - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • 基于Python实现Hash算法

    下面是关于“基于Python实现Hash算法”的完整攻略。 1. Hash算法简介 Hash算法是一种将任意长度消息压缩到某一固定长度的算法。Hash算法的主要应用包括数据加密、数字签名、数据完整性校验等。常见的Hash算包括MD5、SHA-1、SHA-256等。 2. Python实现Hash算法 在Python中,我们可以使用 hash 模块来实现Has…

    python 2023年5月13日
    00
  • python 普通克里金(Kriging)法的实现

    Python普通克里金(Kriging)法的实现 普通克里金法是一种常用的空间插值方法,它可以用于预测未知位置的值。在本文中,我们将介绍如何使用Python实现通克里金法,并提供两个示例说明。 实现原理 普通克里金法是一种基于统计学的插值,它基于已知点值和它们之间的距离来预测未知点的值。具体实现步骤如下: 首定义一个克里金模,包含变异函数和协方差函数。 然后…

    python 2023年5月14日
    00
  • 浅谈iOS 数据结构之链表

    浅谈iOS 数据结构之链表 在计算机科学中,链表是一种数据结构,用于存储一系列按顺序排列的元素。链表的一个关键点是它不需要连续的内存空间来存储元素,相反,每个元素由一个指向下一个元素的指针组成。在iOS开发中,链表在各种场景下都有所应用,如UITableView和UICollectionView的数据源等。本文将详细讲解链表的基本知识和使用技巧。 链表的基本…

    数据结构 2023年5月17日
    00
  • Codeforces Round 866 (Div. 2)

    A. Yura’s New Name 题意: 给出一个仅由_或^组成的字符串,你可以在任意位置添加_或^字符,使得字符串满足:任意字符要么属于^_^的一部分,要么属于^^的一部分。求最少添加的字符数量。 分析: 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加^ ③如果_在中间部分且右边没有^则…

    算法与数据结构 2023年4月25日
    00
  • js处理层级数据结构的方法小结

    “JS处理层级数据结构的方法小结”是一篇讲解JavaScript如何处理嵌套数据结构的文章。在现代的web应用中,嵌套结构是非常常见的,比如JSON数据、树形数据等。以下是对该话题的详细讲解: 1. 嵌套数据结构的概念 指的是包含嵌套关系的数据类型,如数组、对象、树形结构、XML文档等。这些类型之间有着固定层级关系,包含多个层次的数据。嵌套数据结构的处理,往…

    数据结构 2023年5月17日
    00
  • Python实例详解递归算法

    下面是关于“Python实例详解递归算法”的完整攻略。 1. 递归算法概述 递归算法是一种基于函数调用自身的算法,它的基本思想是将一个大问题分解成若干个小问题,然后递归地解决每个小问题,最终将所有小问题的解合并成大问题的解。在Python中,我们可以使用递归算法来解决各种问题,例如计算阶乘、斐波那契数列等。 2. 递归算法实现 2.1 计算阶乘 阶乘是一个正…

    python 2023年5月13日
    00
  • C语言实现带头结点的链表的创建、查找、插入、删除操作

    C语言实现带头结点的链表的创建、查找、插入、删除操作攻略 一、链表基本概念 链表是一种动态的数据结构,它可以在运行时动态地分配内存,支持数据的插入、删除等操作。链表(Linked List)由多个节点(Node)组成,每个节点包含两部分,一个是数据部分(Data),另一个是指向下一个节点的指针(Next)。 二、带头结点的链表 带头结点的链表是一种特殊的链表…

    数据结构 2023年5月17日
    00
  • Python执行时间计算方法以及优化总结

    Python执行时间计算方法以及优化总结 在Python中,我们可以使用time模块来计算程序的执行时间。具体步骤如下: 在程序的处调用time.time()函数,记录当前。 在程序的结束处再次调用time.time(),记录当前时间。 计算两个时间之间的差值,即为的执行时间。 是一个示例代码,用于计算一个函数的执行时间: import time def m…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部