Doran_dinosaur

分类

BFS(10) DFS(4) 二分答案(10) 前缀和(2) 排序算法(1) 树状数组(1) 模拟(1) 线性DP(8) 线段树(3) 背包DP(3) 蓝桥杯(4) 题解(13)

/ 注册

TA的专栏 2篇文章 0人订阅

2篇文章 879人学习

全部文章（共260篇）

P1661 扩散

P1661 扩散题目分析：求解最早的时刻所有点形成连通块连通块需要用到并查集，时间从小到大符合单调用二分答案区间[l,r] (l = 1,r = inf) 代码如下： #include<cstdio> #include<cmath> #include<cst...

2021-01-04

0 586

P1577 切绳子

P1577 切绳子题目分析：有n条绳子，分为相同的k条，求每条最长浮点数二分法：一条绳子最多分(a[i] / x)条,答案区间[l,r] (db l = 0,r = inf) 代码如下: #include<cstdio> #include<cmath> #inclu...

2021-01-04

0 657

P1570 KC喝咖啡

P1570 KC喝咖啡题目分析：一个裸的01分数问题答案区间[l,r] (l = 0,r = inf) 代码如下： #include<cstdio> #include<cmath> #include<cstring> #include<iostr...

2021-01-04

0 567

P1396 营救

P1396 营救题目分析: 并查集+二分法答案区间[l,r] (l 为边的最小值，r 为边的最大值) 代码如下: #include<cstdio> #include<cmath> #include<cstring> #include<iostre...

2021-01-04

0 646

P1281 书的复制

P1281 书的复制题目分析：求解复制时间（抄写页数最多的人用去的时间）最短转换为：长度为m的数列分为k段，每段和的最大值，如何分才能使得最大值最小注意：如果有多解，则尽可能让前面的人少抄写前面的人少抄写，就尽可能的用后面的人，那么从后往前遍历，最后反转一下输出答案代码如下: ...

2021-01-04

0 523

P1182 数列分段 Section II

P1182 数列分段 Section II 题目分析：数据大小把长度为N的数列分为M段，找出每段和的最大值中的最小值二分法：找出答案区间每段和最大值[l,r] 答案存在一个分界点，[l,x] 为非可取解，x为最优解,[x + 1,r]为可取解区间左端点为数列的最大值，右端点为数列的和整数...

2021-01-03

0 659

一元三次方程求解

一元三次方程求解题目分析：根的范围在-100到100之间根与根之间差的绝对值>=1，我们可以用二分判断答案所在最小区间1，求解答案区间在[i,i + 1] (-100<=i<100) 实数范围用浮点数二分代码如下： #include<cstdio> #inc...

2021-01-03

0 546

1292：宠物小精灵之收服（二维费用的01背包问题）

1292：宠物小精灵之收服花费1：精灵球数量，花费2：皮卡丘的体力，价值均为1 注意皮卡丘体力小于等于0不能捕捉，要从体力-1开始递推收服C个小精灵时皮卡丘的剩余体力值最多为R：当我们算出最多收复C个精灵时，最大体力从后往前找，找到需要最小体力的情况,那么剩余体力为m2 - k ...

2020-12-14

0 1121

P1049 装箱问题（01背包）

P1049 装箱问题要使得箱子的剩余空间最小，所占空间需要最大值问题转换为：任取若干个装入箱内，占用最大空间每个物品价值和体积都为v #include<iostream> #include<algorithm> using namespace std; con...

2020-12-14

0 487

P1048 采药（01背包）

P1048 采药法一：未优化空间，时间、空间复杂度均为O(NM) #include<iostream> using namespace std; const int N = 1010; /* 状态表示：f[i][j]表示取前i个草药，时间为j的最大价值状态转移： ...

2020-12-14

0 579