冶炼金属
题目来源：冶炼金属
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金
属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。
现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立
的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
算法原理
算法1
(暴力枚举) O ( n 2 ) O(n^2)O(n2)
设答案为v vv,因为能炼出b bb个但炼不出b + 1 b+1b+1个
所以有b × v ≤ a 且 a < ( b + 1 ) × v b \times v\le a且 a < (b + 1) \times vb×v≤a且a<(b+1)×v
即 a b + 1 < v ⩽ a b \dfrac{a}{b + 1} < v \leqslant \dfrac{a}{b}b+1a<v⩽ba
最小值 a b + 1 + 1 \dfrac{a}{b + 1} + 1b+1a+1 , 最大值a b \dfrac{a}{b}ba
多组数据取一个交集
时间复杂度(O(n))
代码实现
#include <bits/stdc++.h> using namespace std; int main() { int n ; cin >> n ; int mi = 0 , mx = 2e9 ; for(int i = 1 ; i <= n ; i ++) { int a , b ; cin >> a >> b ; int r = a/b , l = a/(b+1)+1; mi = max(mi , l) , mx = min(mx , r) ; } cout << mi << ' ' << mx << endl ; return 0; }
算法2：分块
话不多说，先上图（题目样例分析如下）
思路是，找出最大下限+1，最小上限（这里分别用Min+1,Max来表示）
对于每一次输入的普通金属数量(a)与特殊金属数量(b)
通过观察a，b与最终结果的关系
我们可以发现 a/b 是在满足题意的情况下，冶炼单位特殊金属所使用的最大普通金属数量，我们称为“可以触碰的冶炼上限”
（再大普通金属就不够用了）_
同样的，也能看出 a/(b+1) 是刚好冶炼多一个特殊金属时，单位特殊金属所使用的最小普通金属数量，与之相反我们称为“不能触碰的冶炼下限“
（再小（包括等于）特殊金属就会变多），不能取到，只能往大一个单位，这也是我们为什么最终Min+1的原因！！！
以下为样例分析过后得到的边界范围，以及相交情况
理解完以上过后，就到了代码实现环节。
因为我们要取最大交集（所有数据都满足的情况），所以我们只需要用Min和Max来维护下限的最大值（输出结果记得+1）、上限的最小值，就可得出最终答案
代码实现
#include <iostream> using namespace std; int main() { int m,a,b,Min,Max,flags=0;//flags标记是否为第一次输入 cin>>m; while(m--)//表示输入m组数据 { cin>>a>>b;//输入普通金属、特殊金属数量 if(a/b<Max&&flags==1)//维护上限最小值 { Max=a/b; } if(a/(b+1)>Min&&flags==1)//维护下限最大值 { Min=a/(b+1); } if(flags==0)//让第一次输入的数据作为大小判断的成员，这样就不用考虑Max、Min的初始值 { Max=a/b; Min=a/(b+1); flags=1;//标记已经初始化 } } cout<<Min+1<<" "<<Max;//因为下线不能触碰，得加1 return 0; }
算法3：二分
这道题二分也是可以解决的，但是由于本题没有二段性，很难想到用二分的方式
题目要求找到转换率的最小值和最大值，这个最小值和最大值对每个矿石都成立
考虑到涉及搜索问题，我们就可以想到的应该是二分法
(二分法) O ( n l o g n ) O(nlogn)O(nlogn)
二分法首先要求具有二段性，需要在一个区间内搜索，但本题似乎没有谈及二段性问题，故我们需要自己创造这个性质，我们将k取min(a[i)/b[i],k)，这样最后k的值就是满足条件的转换率的最大值（已经尝试过将maxvalue换成最初的k值，ac了），那么就可以在1~ k区间内找到满足条件的转换率的最小值，为了二分完整性（最开始没发现k的性质），在k~1e9中搜索，找到满足条件的最大值，采用偏右二分（板子），check函数也很容易就可以写出来。
代码实现
#include<iostream> using namespace std; const int N = 10010; int n; int a[N],b[N]; bool check(int mid,int a,int b) { return a / mid == b; } int main() { scanf("%d",&n); int k = 1e9; for(int i = 0 ; i < n ; i ++) { scanf("%d%d",&a[i],&b[i]); if(a[i] / b[i] < k)k = a[i] / b[i]; //找到划分区间的中间值 } int ans = k; int minvalue = -1,maxvalue = 1e9 + 10; for(int i = 0 ; i < n ; i ++) { int l = 1,r = k; while(l<r) //二分板子 { int mid = (l + r) >>1; if(check(mid,a[i],b[i])) r = mid; else l = mid + 1; } minvalue = max(minvalue,l); //找到满足所有矿石的转换率的最小值 思考一下为什么取max? l = k; r = 1e9; while(l<r) //偏右二分板子 { int mid = (l + r + 1) >>1; if(check(mid,a[i],b[i])) l = mid; else r = mid - 1; } maxvalue = min(maxvalue,l); //找到满足所有矿石的转换率的最大值 思考一下为什么取min? } printf("%d %d\n",minvalue,maxvalue); //这里的maxvalue换成ans也是可以AC的 return 0; }
飞机降落
题目来源：飞机降落
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早
可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
算法原理
暴力模拟(dfs)
数据量很小，考虑所有的排列情况然后判定是否可以全部降落即可
使用dfs剪枝可以提高效率
代码实现
#include<iostream> #include<cstring> using namespace std; int t,n,a[15][3]; //st记录是否已经降落，flag标记是否降落完成 bool st[15],flag; //k表示已经降落的飞机数量，last表示上一架飞机降落完成的时间 void dfs(int k,int last) { if(k>=n)//已经全部降落 { puts("YES"); flag=true; } if(flag) return;//已经完成就不再搜索 for(int i=1;i<=n;i++)//枚举每一种情况 { if(!st[i])//还没降落 { //如果最迟降落时间已经过去就不满足，剪掉 if(a[i][1]<last) return; st[i]=true; //降落时间小于当前飞机的最早降落时间就等到了再降落 if(last<a[i][0]) dfs(k+1,a[i][0]+a[i][2]); //否则上一架完成这架立马降落 else dfs(k+1,last+a[i][2]); st[i]=false;//还原现场 } } } int main() { cin>>t; while(t--) { cin>>n; memset(st,0,sizeof st);//设置为都未降落 flag=false;//还没完成 for(int i=1;i<=n;i++) { cin>>a[i][0]>>a[i][1]>>a[i][2]; //到达时间加上盘旋时间==最迟降落时间 a[i][1]+=a[i][0]; } dfs(0,0); if(!flag) puts("NO");//所有的情况都不满足 } return 0; }
接龙数列
题目来源：接龙数列
算法原理
本题让我们求最少删除的数的个数，我们实际上可以将其转化为求该数列里的最长接龙子序列，再用 n 减去该值即可。
代码实现：
#include<bits/stdc++.h> using namespace std; int n,dp[10],maxn; string a;//为了方便取头尾，可以以字符串形式存储 signed main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a; int len=a.length(); dp[a[len-1]-'0']=max(dp[a[len-1]-'0'],dp[a[0]-'0']+1); } for(int i=0;i<=9;i++) maxn=max(maxn,dp[i]); cout<<n-maxn; return 0; }
岛屿个数
题目来源：岛屿个数
算法原理
再正式讲解这道题之前，我们先来学习一个比它更简单的问题
如果没有“子岛屿”这个题目限制，该如何判断有图中有几个岛屿？
其实很简单：我们遍历图中每一个点，遇到1说明遇到了岛屿，岛屿数加1，然后把其所在的四连通区域（也就是整个岛屿，不知道这个概念的读者可点击链接学习）全部变成0（“染色”抹去这个岛屿，以免后面重复计算），继续这个过程直到没有1说明已经没有岛屿了。
Leetcode练习：岛屿数量
学会这个更简单的问题后，我们就可以正式开始这道题目的思考了
我们关键是要解决一个问题：
怎么判断一个岛屿是另一个岛屿的“子岛屿”？
方法是“合并”
- 首先我们用一个比地图大一圈的矩阵来存储这个地图（只需要大一圈就行，数组这样开sea[52][52]）
- 由于地图外都是海水，所以先所有点都初始化为0（注意是字符’0’）
- 然后，我们从(0,0)开始把所有相连的海水都标记为2（第一次DFS），这个过程之后图中所有剩下没有被更改的0一定在岛屿内部，（这次搜索要八连通，请读者自己思考为什么）；
- 接下来我们再遍历一遍地图，把所有0都变成1，这样岛屿和其内部的子岛屿就“合为一体”了（请读者仔细分析）；
所以，剩下来的问题就是上面那个更简单的问题了。（第二次DFS）
其实还有一个关键的问题！那就是为什么我要开52x52的数组，开51x51的数组行不行？
答案是不行！只能多不能少。因为如果我们开51x51的数组，对于50x50那个海域地图，对于右下角的“边角”岛屿，即使不是子岛屿的“包含“关系，我们也无法搜索进去
所以我们要开数组52x52搜索一个更大的海域就能搜索进去了。
代码实现
#include <bits/stdc++.h> using namespace std; #define For(i, x) for (int i = 0; i < x; i++) #define For1(i, x) for (int i = 1; i <= x; i++) int t, m, n; int next4[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, // 四连通 next8[8][2] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; // 八连通 char sea[52][52]; // 至少52x52 void dfs(int x, int y) { // 第一次搜索 sea[x][y] = '2'; int newx, newy; For(i, 8) { newx = x + next8[i][0], newy = y + next8[i][1]; if (0 <= newx && newx <= m + 1 && 0 <= newy && newy <= n + 1 && sea[newx][newy] == '0') dfs(newx, newy); } } void dfs1(int x, int y) { // 第二次搜索 sea[x][y] = '2'; int newx, newy; For(i, 4) { newx = x + next4[i][0], newy = y + next4[i][1]; if (1 <= newx && newx <= m && 1 <= newy && newy <= n && sea[newx][newy] == '1') dfs1(newx, newy); } } int main() { cin >> t; while (t--) { int ans = 0; cin >> m >> n; For(i, m + 2) For(j, n + 2) sea[i][j] = '0'; // 初始化 For1(i, m) For1(j, n) cin >> sea[i][j]; dfs(0, 0); For1(i, m) For1(j, n) if (sea[i][j] == '0') sea[i][j] = '1'; For1(i, m) For1(j, n) if (sea[i][j] == '1') ans++, dfs1(i, j); cout << ans << endl; } return 0; }
子串简写
题目来源：子串简写
算法原理：
前缀和/双指针 O ( n ) O(n)O(n)
这题首先想到的暴力做法，是两层循环控制区间的长度,再判断区间的首尾是否和条件相等, 时间复杂度为O(n2)显然会超时.
这里用双指针动态维护一段长度为k的区间， 在右端点往后用前缀和思想预处理b的数量，b的数量即为以a为起点所有满足题意区间的数量，再移动动态区间即可。
时间复杂度
O(n)
C++ 代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; int k,cnt; string s; char a,b; int main() { cin>>k>>s>>a>>b; int n=s.size(); ll ans=0; //答案记得开longlong // for(int i=0,j=k-1;j<n;i++,j++) // { // if(s[i]==a)cnt++; // if(s[j]==b)ans+=cnt; // } //为了方便理解写成后缀和形式 for(int i=n-k,j=n-1;i>=0;i--,j--) { if(s[j]==b)cnt++; if(s[i]==a)ans+=cnt; } cout<<ans; return 0; }
