boxxxx

算法

学习(10) 并查集(1) 数位dp(1) 概率dp(1) 线性dp(1) 题解(3)

/ 注册

全部文章 / 算法（共38篇）

牛客每日一题3.25 tokitsukaze and Soldier 权值线段树

考虑我们可以怎么获得答案，如果某一个人选了他，那么答案人数的集合就必定小于等于s[i], 对于答案需要的人的集合的人数为num,那么集合里面所有的s[i]的最小值必然是小于等于num。明确了上述最关键的点后就是可以知道，我们如果答案的人数是2人，则s[i]>=2的全部人数取前2个就是答案，s...

2020-03-24

0 612

Codeforces Global Round 7 cf 1326D 马拉车

题意是叫你找最长的回文串，然后这个回文串可以由原本的串的前驱+后继拼起来。由于前驱和后继是必须选的对不对（可能有一个为空）。那么我们第一步就是吧原本的串倒置，把正的和反的去找出最长的相同的，这样就满足了前驱+后继的限制。下一步是什么？假设原本的长度是[1,len]，我们上面找到的最长相同的...

2020-03-20

0 400

牛客练习赛59 E 石子搬运 dp+三分法

有n堆石子，第i堆石子的石子数量是ai{a_{i}}ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k{k}k，那么这堆石子将对牛牛产生k2{k^{2}}k2的负担值。牛牛最多只能搬运m{m}m次，每次搬运可以从一堆石子中选出一些石子搬回牛客，每次搬运不能同时...

2020-03-14

0 474

洛谷p2018 树DP

首先，本做法和其他的O(N^2logn)做法是完全不一样的，那种做法比较好理解，我说一下我的做法，感jio是O(Nlogn)，不太会算首先思考如何获得每一点要如何知道由当前点出发的答案是什么？对于绝大部分点，都有父亲节点和儿子节点，那么对于每一个点都是这么抉择走的。这里先不看now点，看节点1...

2020-02-16

0 331

洛谷p1773 dp

其实，这个dp还是蛮简单的，dp做多了后就会觉得方程不难出了，其实我的思路和大家都差不多，但是大部分都用了O(N^2)去预处理出这个区间内的值取模后是多少，其实这是完全没有必要的。听我来给你吹 f[i][j] = v：前i个字符各种操作后的数字为j，使用的最少的乘法个数为v，最后一个字符必须要落...

2020-02-14

0 389

洛谷2285 dp

很水的dp，用于在你蓝题dp做疯了的时候来提高下信心。首先那个距离就是曼哈顿距离，所以小于等于1的格子就是当前格子的上下左右，还包含自身。其实唯一的问题就是如何计算贡献的时候不要算重复了，那么分情况考虑就可以不算重复，f[i][j][0]代表到达ij点的走法是从上面走下来，f[i][j][1]代...

2020-02-11

0 303

洛谷p2964 其中一种常见的博弈论的dp方法

题目链接在之前，我写dp看见题目说两个人都足够聪明，然后他们进行一些操作，求某些人的最大利益，我完全不知道怎么去设计dp的方法，然后我接触了一道题，看了题解洛谷p2734 这道题的dp方法和现在这道题其实在设计思路上面是一样。我不知道现在是谁在取数字，但是我就是要为现在这个取数字的人谋取最大...

2020-01-30

0 454

Codeforces Round #615 (Div. 3) F 运行最快的做法！！

一开始输出是cout，发现就第二了，改printf就直接第一快了。我说下这题我的做法是什么。题目就是给你一棵树，叫你给出三个点，这三个点相连的简单路径的边数最多。样例的图解释的很清楚是什么意思了。怎么做呢？我一开始首先考虑两个点相连的情况，两个点的情况下什么时候会是拥有最长的边数？很明显就是大家都...

2020-01-24

0 307

详解2020 CCPC-Wannafly Winter Camp Day3 Div.1 G火山哥周游世界树dp

题目链接上面是样例2的图，首先我们看到数据范围就一定要明确，肯定不是暴力，然后由于题目说了是n个点n-1条边，这就是一棵树，在这里就要考虑到树dp！！（要是没想到就没了）我们来考虑下我们要什么，我们需要知道每个点走过所有目标点的最短路程，一个点怎么走完所有的目标点呢？设当前在i点从点...

2020-01-22

0 336

2019icpc 南昌C And and Pair dp

题目链接大意：给你一个超大数字n的二进制表示，询问有多少组数对（i，j），数对要满足， 0≤j≤i≤n; i & n=i； i & j=0；首先对于我看到其他的什么数位dp，组合数学，我一个没懂。我说下我自己是怎么dp的。对题目分析 i&n = i，那么说明在二进制的...

2020-01-16

0 314