1249：Lake Counting 题目分析： 1.八连通积水是连通在一起，叫水洼2. 求水洼个数：转换为求W连通块个数 代码如下： #include<iostream> #include<queue> using namespace std; #define x first #define y second #define pii pair<int,int> const int N = 115; int n,m; char g[N][N]; bool st[N][N]; void bfs(int sx,int sy){ queue&lt...

P1873 砍树 题目分析： 答案区间[l,r] (l = min(a[i]),r = max(a[i])) 找最优解：最高砍树高度 mid取(l + r + 1) >> 1,偏右 注意： 二分出现死循环往往是mid写错了 代码如下: #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<set> using na...

P1843 奶牛晒衣服 题目分析： 数据范围： 为了避免踩坑，用long long型 求解弄干所有衣服的时间 二分答案区间[l,r] (l = 1,r = inf) 注意： 踩坑了，int改半天，w[i] - a * x里面乘以x可能爆int，用long long啊 代码如下： #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include&l...

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

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

P1570 KC喝咖啡 题目分析： 一个裸的01分数问题 答案区间[l,r] (l = 0,r = inf) 代码如下： #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; #define inf 0x3f3f3f3f #define eps 1e-6 #define db...

P1396 营救 题目分析: 并查集+二分法 答案区间[l,r] (l 为 边的最小值，r 为 边的最大值) 代码如下: #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; #define inf 0x3f3f3f3f #define eps 1e-6 #define db ...

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

P1182 数列分段 Section II 题目分析： 数据大小 把长度为N的数列分为M段，找出每段和的最大值中的最小值 二分法：找出答案区间每段和最大值[l,r] 答案存在一个分界点，[l,x] 为非可取解，x为最优解,[x + 1,r]为可取解 区间左端点为数列的最大值，右端点为数列的和 整数二分解题,mid取最小情况(l + r) >> 1; 代码如下: #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algo...

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

1292：宠物小精灵之收服 花费1：精灵球数量，花费2：皮卡丘的体力，价值均为1 注意皮卡丘体力小于等于0不能捕捉，要从体力-1开始递推 收服C个小精灵时皮卡丘的剩余体力值最多为R： 当我们算出最多收复C个精灵时，最大体力从后往前找，找到需要最小体力的情况,那么剩余体力为m2 - k int k = m2 - 1; while(k > 0 && f[m1][k - 1] == f[m1][m2 - 1]) k --; cout<<m2 - k;代码如下： #include<iostream> #include<...

P1049 装箱问题 要使得箱子的剩余空间最小，所占空间需要最大值 问题转换为：任取若干个装入箱内，占用最大空间 每个物品价值和体积都为v #include<iostream> #include<algorithm> using namespace std; const int N = 2e4 + 10; int n,m; int f[N]; int main(){ cin >> m >> n; for(int i = 1; i <= n; i ++ ){ int v,w; cin >&g...

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

interval GCD 题目分析: 把 A[l],A[l+1],…,A[r] 都加上 d 利用差分改变区间[l,r]的值a[l] += d,a[r + 1] -= d 询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD) 根据辗转相除法，gcd(a,b) = gcd(b,a - b),gcd(a,b,c) = gcd(a,b - a,c - b) 那么，询问区间[l,r]最大公约数为：gcd(query(1,1,l).sum,query(1,l + 1,r).d) 需要维护两个属性：ll sum; //sum表示和，求差分区间[l,r]的和，值为a[r] ll...