凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

cf contest551 D 树上dp

Serval and Rooted Tree 题目链接题目大意给一棵有根树，设有k个叶子节点，给所有的叶子节点标号1~k；然后每个非叶子节点都有一个得到当前节点标号的方法，就是取他的所有子节点的最大值或最小值（取决于输入）；问根节点能得到的最大的标号是啥。刚开始不会做，想着贪心可不可以...

2020-09-15

0 487

吉老师线段树 hdu5306

吉老师线段树这个是干啥的？其实就是个线段树，我也不知道为什么叫吉老师线段树简单例题：hdu5306 三种操作： 0 l r x 把 l ~ r 区间里大于 x 的数变成 x 1 l r 求 l ~ r 区间里的最大值 2 l r 求 l ~ r 区间和题解: 线段树里记一个最大值max、最...

2020-09-15

0 752

树形dp 的一道巨简单题

我好菜（这三个字写这么大完全是为了提醒自己 hhhh 竟然这都不会）树形dp；不懂得如何推出状态表达式（即使再简单）看见题目就无从下手！！！有点烦所以决定多刷一点dp题，先看了最基础的：洛谷P1352 这个题其实挺简单的，但是我是真的废。。。题意: 给出一棵树，每个节点有自己...

2020-09-15

0 476

P2015 二叉苹果树树形dp 01背包

P2015 二叉苹果树题目链接题意：给一棵树，每个边都有权值，选择一些边删除，剩余m条边。问删除后所有变得权值和最大是多少？树形dp 01背包问题； dp数组：dp[maxn][maxn] ； dp[x][i] 代表x为根节点的子树上有i条边的最大权值；转移方程： num[x]为子树上...

2020-09-15

0 500

洛谷P3177树上染色树形dp 背包

树形dp 又是树形dp。。。题目链接题意: 给一棵树，给出边权（边权为距离）把m个点标记为黑色，让求黑色点两两之间的距离加白色点两两之间的距离的最大值。怎么做呢？我还是菜了呀 <mark>dp[x][i] 代表x子树上有i个黑点的对答案的贡献的最大值。</mark>...

2020-09-15

0 448

牛客Treepath

Treepath 题目链接题意: 给一棵树，让求两个点距离为偶数的点有多少对。题解：两个点的距离可以换为：d[x] + d[y] - 2 * d[lca];(d数组为到根节点的距离) 于是后面的-2*d[lca]不影响奇偶性。所以到根节点奇偶性相同的点可以组成一对。就很简单了。代码...

2020-09-15

0 430

树上启发式合并 cf600E

树上启发式合并这个是啥？先说一下并查集的启发式合并：并查集的启发式合并就是把集合小的并到集合大的上去。(按秩合并是把低的并到高的上面去) 于是树上的也差不多：就这样一个优化的思路。把大的并到小的上去树上：什么是大的：重儿子的那个子树。小的: 轻儿子的那几个子树。就是算答案的时候把轻...

2020-09-15

0 540

cf 621D

CF 621D 题目链接题目大意: 给一个图，n个点m个边，给出k个特殊点，保证图联通，让在特殊点中选一对点连起来，求连完后的1到n节点的最短路的最大值。，，，怎么做呢？朴素做法：显然是预处理1~每个结点的最短路，n到每个结点的最短路，然后枚举k里的两个节点，连起来，取最大值，然后最后...

2020-09-15

0 465

cf 662c2

cf div2 c2 题目链接自闭了这个题题意: 给一个数组，让构造一个左边跟右边不能同时有大于这个数的（左边右边不一定是挨着的）、给出的数组是当前位置的最大值。构造出来的数组的和尽可能大很明显要么递增、要么递减、要么找个峰值左边递增，右边递减。第一二种情况可以归为第三种情况。比赛...

2020-09-15

0 390

cf div2 D dp

D. Array Without Local Maximums 题目链接题意给一个数组，给出一个数组，（1e5）包含数字 1~200 或 -1 -1代表这个数字不知道是多少，让构造数组，把-1填上，使得数组里的每一位数字都有旁边的两个数至少有一个大于等于这个数。也就是 ai≤max(a...

2020-09-15

0 456