boxxxx

学习

并查集(1) 数位dp(1) 概率dp(1) 算法(38) 线性dp(1) 题解(3)

/ 注册

全部文章 / 学习（共10篇）

牛客每日一题 4.7 树树dp+组合数学

https://blog.csdn.net/qq_43804974/article/details/105345340昨天的牛客鸽了，我不会数学首先第一步要理解题意就是要把树分成多个联通块，每个联通块的颜色都要不一样，求方案数。为什么每个联通块的颜色都不一样，因为如果有同样的颜色在不同的联通块上...

动态规划

2020-04-06

0 676

牛客每日一题4.3 Shortest Path 树dp

https://blog.csdn.net/qq_43804974/article/details/105269874首先这个数据范围，看着就是O(N)或者O（Nlogn）的东西，考虑树dp。先贪心的考虑。一个点怎么找到另一个点？肯定是他能接触到的最短的那个点，如果与他最短的那个点被用过了呢？找其他...

2020-04-02

0 611

牛客每日一题4.2 月月查华华的手机二分查找

https://blog.csdn.net/qq_43804974/article/details/105241744 问题就是询问某一个串是不是初始串的子序列。那么序列都是小写字母，就对存入每一个字母在初始串的位置。然后对目标串的字母一个个查询，如果存在一个最接近并且比上一个字母远的位置，则这个当...

2020-04-01

0 689

牛客每日一题4.1 Rinne Loves Edges 树dp

https://blog.csdn.net/qq_43804974/article/details/105222630 首先理解题意后可以转化为以S为根的树，用最少的权值去删除边，使得所有的叶子与S不相连。如果可以得出上面的题意那这题就是个树dp简单题了。那么设f[i] 为以i为根的子树，他的所有叶...

dp

2020-03-31

0 591

牛客每日一题3.31 城市网络树上倍增

https://blog.csdn.net/qq_43804974/article/details/105196280 数据修复后，之前的就T掉了~还是树上倍增，dp[i][j]就是节点i开始拿了2^j个物品后所在的位置，递推就是dp[i][j] = dp[dp[i][j-1]][j - 1];然后...

2020-03-30

0 672

牛客每日一题3.30 滑动窗口单调队列

https://blog.csdn.net/qq_43804974/article/details/105176524这道题由于空间限制的很死，所以原本用线段树之类O(nlogn)的算法都会MLE，唯一的做法就是O（N）的单调队列。对于每一个滑动窗口的元素，都是从上一个窗口的基础上，增加一个新的...

2020-03-29

0 714

牛客竞赛每日一题3.27 数学考试动态规划

https://blog.csdn.net/qq_43804974/article/details/105115539 虽然说是动态规划实则就是在暴力找答案。我们答案要求的是两个区间，所以我们只要选取一个区间，然后枚举这个区间往前的所有区间能提供的最大答案就好了。我们需要什么呢value[i] , ...

2020-03-26

0 841

牛客每日一题3.26 合并回文子串动态规划

https://blog.csdn.net/qq_43804974/article/details/105103097首先这种题肯定是动态规划！！！！！不要往其他地方想。要怎么做呢先从单个串要怎么判断区间最长回文来说。单个串如果要判断任意一个区间[L,R]是不是回文可以去写区间dp，对于一个串长度...

动态规划 dp

2020-03-25

0 666

hdu4123 树求每个节点的最长链+尺取法

题意：50000个点的树，每个点有一个人，每个人会跑到离自己初始点距离最远的点上，这个距离为distance[i]。给你500个查询，对于每个查询Q，找一段连续编号的人，比如[left,right]，满足 max( distance[i] i∈[left,right] ) – min( distan...

2019-09-15

0 451

ST表的动态规划方程解释

在我学st表的时候，对于动态规划方程总是有点不理解，我相信肯定也有人会遇见同样的问题，我就把我现在对于这个方程的理解说一说。ST表的数组st[i][j]是指以i为左端点，含有2^j个数的闭区间（包含了i）；那么对于st[i][j]所代表的区间就是 [i,i+2^j-1]；（如果不减1就多了一个数了，...

2019-08-27

0 452