首页 > 其他分享 >20221114_T4B_树形dp换根dp

20221114_T4B_树形dp换根dp

时间:2022-11-14 19:12:20浏览次数:59  
标签:power int 20221114 db read score T4B dp

题意

太冗长了

img

传一张图片自己看吧。

题解

赛时得分 15/100/100

赛时写了 \(A=0\) 的乱搞,没写对但是拿了 15pts。

首先这个函数是一个增函数,对于 power 和 score 两个指标来说。

既然是增函数,那么我们显然是当前 score 越大越好,并且 power 具有单调性,可以二分。

我们首先二分 power,然后选择树形 dp。

首先一轮记录从叶子节点走上来的 score,power在整个过程中是不会改变的。

然后我们考虑记录从父亲节点下来的到子节点的最优秀的一条,走到一个叶节点计算答案就好了。注意要维护最大值和次大值,因为这个叶节点不能是我从父亲走下来的叶节点。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T& t){t=0; register char ch=getchar(); register int fflag=1;while(!('0'<=ch&&ch<='9')) {if(ch=='-') fflag=-1;ch=getchar();}while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;}
template <typename T,typename... Args> inline void read(T& t, Args&... args) {read(t);read(args...);}
const int N = 1e5 + 10, inf = 0x3f3f3f3f;

typedef long double db;
int n, A, du[N], fa[N], fr1[N], fr2[N];
db ori, tar, f1[N], f2[N], g[N];
const db eps = 1e-8;
struct person {
	db power, score;
	void R() {cin >> power >> score;}
	db sig(db x) {
		if(fabs(x) < eps) return 0;
		if(x > 0) return 1;
		else return -1;
	} 
	db YeMenYaoZhanDou(person x) {
		db dpow = power - x.power, dpoi = score - x.score;
		db delta = 2 * sig(dpow) * (sqrt(fabs(dpow) + 1) - 1) - A * sig(dpoi) * (sqrt(fabs(dpoi) + 1) - 1);
		return x.score - delta;
	}
}a[N];
vector<int>G[N];
db ans;

void dfs(int u, db power) {
	f1[u] = f2[u] = -1e9; fr1[u] = fr2[u] = 0;
	if(du[u] <= 1 && u != 1) {f1[u] = a[u].YeMenYaoZhanDou((person){power, ori}); return;}
	for(int v : G[u]) {
		if(v == fa[u]) continue; fa[v] = u;
		dfs(v, power);
		db zhan = a[u].YeMenYaoZhanDou((person){power, f1[v]});
		if(f2[u] < zhan) f2[u] = zhan, fr2[u] = v;
		if(f1[u] < f2[u]) swap(f1[u], f2[u]), swap(fr1[u], fr2[u]);
	}
}
void dfs1(int u, db power) {
	if(du[u] <= 1) {ans = max(ans, g[u]);} // solved
	for(int v : G[u]) {
		if(v == fa[u]) continue;
		db up = (v == fr1[u]) ? f2[u] : f1[u]; up = max(up, g[u]);
		g[v] = a[v].YeMenYaoZhanDou((person){power, up});
		dfs1(v, power);
	}
} 
bool check(db x) {
	ans = -1e18; fa[1] = 0; if(du[1] <= 1) {g[1] = a[1].YeMenYaoZhanDou((person){x, ori});} else g[1] = -1e18;
	dfs(1, x); dfs1(1, x);
	return ans >= tar;
}

int main() {
	freopen("pigeatyy.in", "r", stdin);
	freopen("pigeatyy.out", "w", stdout);
	read(n, n); cin >> ori >> tar >> A;
	for(int i = 1; i < n; ++i) {
		int u, v;
		read(u, v);
		G[u].push_back(v);
		G[v].push_back(u);
		du[u]++; du[v]++;
	}
	for(int i = 1; i <= n; ++i) a[i].R();
	db l = -1e6, r = 1e6;
	while(r - l > eps) {
		db mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid;
	} 
	cout << fixed << setprecision(6) << l << endl;
	return 0;
}

标签:power,int,20221114,db,read,score,T4B,dp
From: https://www.cnblogs.com/Mercury-City/p/16890076.html

相关文章

  • 20221114-python字符串
    1.字符串定义:    2.字符串的转义符    3.字符串的拼接:      4.字符串的下标:    5.字符串的切片 ......
  • 20221114_T4B_拓扑排序贪心
    题意L国正在举行各种会议,但是可怜的是L国只有一个主持人,每场会议的开始主持人都必须去主持会议,使会议得以开始,在会议开始后主持人可以离开。 主持人不会分身,他在一个时刻......
  • 【CF1750F】Majority(容斥+DP)
    题目链接规定一个\(01\)串\(s\)是好的,当且仅当可以经过若干次下面的操作将它变成全\(1\):选择一对\(i,j\)满足\(s_i=s_j=1\)且\(\sum_{k=i}^js_k\ge\frac{j-i+1......
  • 概率期望 DP 学习笔记
    期望这东西学了一次忘了,再学一次过了两天又不会了。我是鱼。故写此博客以便加深记忆及日后复习。经典问题1某事件发生概率为\(p\),则该事件首次发生的期望次数为\(\fr......
  • 今日笔记之20221114
    1.vue中刷新页面,echarts图表不显示问题? <divid="myChart"></div><script>exportdefault{data(){return{myChart:{}}},mounted:{this.init......
  • 状态压缩DP
    一、状态压缩DP概述1、概念状态压缩dp通过将状态转换成整数,来实现状态转移。前置知识:位运算(&、|、!、^)当要处理一些集合问题的时候,可以将状态转换为整数,运用二进制相关......
  • expdp导出sys用户下test表空间报错ora-31655
    数据库:oracle11.2.0.4系统:centos7.9问题描述:expdp导出sys用户下test表空间报错ora-31655,如下所示:[oracle@leo~]$expdp\'/assysdba\'directory=ts_expdpdumpfile=ts......
  • [期望DP]P1654 OSU!
    题目描述osu是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子:一共有n次操作,每次操作只有成功与失败之分,成功对应1,失败对应0,n次操作对应为1......
  • 动态 dp 学习笔记
    好耶!来学新算法了(最近停课了就有时间学算法啦因为CSP-S考了个什么ddp然后我不会(CSP炸了)学了一个晚上加一个上午才学会(我太菜了)嗯嗯其实说起来是个很简单的东西.前......
  • 动态规划(Dynamic Programming)套路学习 ----- 动态规划、备忘录、dp table、状态压缩、
    明确套路:首先,动态规划问题的一般形式就是求最值。而求解动态规划的核心问题是穷举。动态规划三要素。重叠子问题最优子结构状态转移方程⭐ 实战:一、斐波那......