leetcode 834. sum of distances in tree-编程思维
原题链接在这里:https://leetcode.com/problems/sum-of-distances-in-tree/description/ 题目: There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n
morethink program
原题链接在这里:https://leetcode.com/problems/sum-of-distances-in-tree/description/ 题目: There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n
请容许我不理解一下为什么这题题解几乎全都是指针实现/kk 其实长链剖分是可以直接用数组来写的。 考虑朴素 DP。设 \(f_{u,i}\) 表示以点 \(u\) 为根的子树中与点 \(u\) 距离为 \(i\) 的点的个数。 则转移方程为: \[f_{u,i}=\sum\limits_{v\in son_u} f_{v,i-1} \]答案为: \[ans_u=\max\{f_{u,i}\} \]
日常写点奇奇怪怪的乱搞做法 awa 这题跟前面几道数位 DP 的区别在于让求第 \(n\) 小的数。 虽然我不会求也不想学这个,但我们可以 binary search! 问题就转换为求 \([1,mid]\) 中的幸运数个数,这样就和前面那些题做法一样了/xyx code #include<bits/stdc++.h> #define int long long using nam
前言:这篇博客是 yx NOIP 前恶补知识点写的,并没有普通树形 DP 捏/wq upd:NOIP 没了,现在这里有普通树形 DP 了( 换根 DP gg 押 NOIP 会考换根 DP,发现自己还没学过/jk 害怕.jpg 或许按本人感受的难度顺序排序(? P3478 [POI2008] STA-Station 当根从 \(u\) 换到 \(v\) 时,\(v\) 的子树内所有节点深度 \(-
部分详见: 概率期望 DP 学习笔记 树形 DP 学习笔记 其余题就不具体分类了。 P1220 关路灯 题解说这是区间 DP 经典题,但我以前居然没听说过,这下尴尬了。 设 \(f_{i,j,0/1}\) 表示关掉区间 \([i,j]\) 所有灯,人在点 \(i/j\) 消耗的最少功率。 那么 \[f_{i,j,0}=\min(f_{i+1,j,0}+dis_{i,i+1}\times (su
emmm 01 背包模板... 设 f[i] 表示背包容积为 i 时所得的最大价值。 则状态转移方程为 f[j] = f[j - w[i]] + c[i] 。 #include<bits/stdc++.h> using namespace std; int w[1001],c[1001],t,m,f[1001]; int main() { scanf("%d%d",&
用时 10min ,一遍过。 设 f[i][j] 表示第一个字符串的前 i 位和第二个字符串的前 j 位最长公共子序列的长度。 当比较的这两个字母相同时,f[i][j] = f[i-1][j-1] + 1 。 否则 f[i][j] = max(f[i-1][j],f[i][j-1]) 。 #include<bits/stdc++.h> using namespace std; ch
思路: 先从左到右求一遍最长不下降子序列,再同样方法从右到左求一遍。 然后我们枚举分界点,则总人数就是左边一半加上右边一半的人数。 取最大值,输出答案。 见注释。 #include<bits/stdc++.h> using namespace std; int n,a[101],f1[101],f2[101],ans; int main() { cin>>n;
想了很久没想出来,无奈之下看了题解。 如果 a[i] < a[j] ,因为要保证都是整数,所以 j - i 必须要小于 a[j] - a[i] ,才能使区间 i,j 内的所有数均可修改。 j - i < a[j] - a[i] 移项得 a[i] - i < a[j] - j。 所以 a[i] 里要存 a[i] - i 的值,则求出最长不下降子序列后就可以保证其中的数都能够修改
CF963B Destruction of a Tree 题解 洛谷题目链接 这里提供一个较为朴素的 DP 想法。 题意简述 给定一棵树,节点个数不超过 \(2 \times 10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。 思路分析 首先可以随便选一个点作为根。 其次,我们考虑在一棵子树的删除情况,我们令根节点为 \(u\),它的直接儿子为
Desc. Link. 你有 \(n\) 个朋友,他们会来你家玩,第 \(i\) 个人 \(1...A_i\) 天来玩,然后 \(A_i+1...2A_i\) 天不来,然后 \(2A_i+1...3A_i\) 又会来,以此类推; 每天你会选一个来玩的人,给他颁个奖,如果没人来玩,你就不颁奖。 你要给每个人都颁 \(K\) 个奖,问至少需要多少天。 Sol. 前面的部分很套
Desc. 给定一棵 \(N\) 个节点无根树,找出满足以下条件的集合 \(S\) 的数量: \(S \subseteq \{1,\dots,n\}\); \(S\) 的导出子图联通; \(\displaystyle\prod_{v \in S} a_v \leqslant M\)。 Sol. 点分治,统计包括当前分治中心的集合数量,如果从子树的角度入手会发现并不好做——合并这一步就
link。 一个 dp(拜谢 ly)和切入点都略有不同的做法,并不需要观察啥性质。 原问题针对子序列进行规划,自然地想到转而对前缀进行规划。接下来我们考虑一个前缀 \([1, i]\) 以及一个 \(j \in [1, i]\) 对答案的贡献,可以写出 \(\displaystyle \textit{cont}(j \text{ to } [1, i]) = [\max_{i < k} a
link。 首先考虑暴力,枚举规划前缀 \([1, i]\) 和前缀 mex \(x\),则我们需要 \(x\) 个数来填了 \([0, x)\),还剩下 \(i-x\) 个数随便填 \([0, x) \cup (x, n]\),如果直接组合数算可能会出问题,考虑 dp。 定义 \(f[i][x][j]\) 表示规划前缀 \([1, i]\),当前的 mex 为 \(x\),还有 \(j\) 个
讲课讲得非常清楚啊,我绝赞膜拜。节奏可以,思路清晰,解法自然,为讲师点赞。 第一个题是 loj3282 / joisc2020 - Treatment Project。原问题由 \(\left(S, t, w\right)\) 三个维度构成,分别表示村民被治疗的状态,时间,花费。比较自然的思路是针对 \(t\) 做规划,但是这样有一个问题——\(t\) 和 \(S\) 是息息相关的,若从 \(t