??1 马的遍历——BFS
1.1 解题思路
这道题就是标准的bfs（广度优先搜索）模板题型，知道迷宫类问题怎么做，这道题就不难。不一样的点就是下一步有8个位置可以选择。
1.2 代码贴贴
#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int vis[N][N];
int maze[N][N];
int n, m;
int tx,ty;
struct ma{
int x, y;
};
int step[N][N];
ma beg, cur, nt;
queue<ma> Q;
int dir[8][2] = { {2,1}, {2,-1}, {1,2},{1,-2}, {-1,2},{-1,-2},{-2,1},{-2,-1} };
int in(int tx, int ty){
return (tx>=1 && tx <= n && ty >= 1 && ty <= m);
}
int main(){
cin>>n>>m>>beg.x>>beg.y;
step[beg.x][beg.y] = 0;
vis[beg.x][beg.y] = 1;
Q.push(beg);
// bfs模板进行遍历。
while(!Q.empty()){
cur = Q.front();Q.pop();
for(int i = 0; i < 8 ; ++i){
tx = cur.x + dir[i][0]; ty = cur.y + dir[i][1];
if(in(tx,ty) && vis[tx][ty] == 0){
vis[tx][ty] = 1;
nt.x = tx; nt.y = ty;
step[nt.x][nt.y] = step[cur.x][cur.y]+ 1;
Q.push(nt);
}
}
}
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){
if(step[i][j] == 0 && !(i == beg.x && j == beg.y)){ //没有遍历到的点
//控制左对齐
cout<<setiosflags(ios::left)<<setw(5)<<setfill(' ')<<-1;
}else{
cout<<setiosflags(ios::left)<<setw(5)<<setfill(' ')<<step[i][j];
}
}
cout<<'\n';
}
return 0;
}
??2 切绳子——二分
2.1 解题思路
属于浮点数二分类题型，这种二分的边界条件问题，我也是靠自己模拟一些数据去二分，分析哪一边二分时取等，看答案是在l处，还是在mid处，亦或在l-1处，总之需要具体场合具体分析。
2.2 AC代码贴贴
#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
double lines[N];
int n , K;
//题目要求 6位小数，1e-8, 4位小数1e-6 ,2位小数 1e-4。 精度多一点没关系，只允许多不允许少。
//带精度的二分
int main(){
cin>>n>>K;
for(int i = 0; i < n ; ++i) cin>>lines[i];
double l = 0, r = 1e5; //初始——末范围
double mid;
int ans; //记录每一根长度为mid时所能得到的绳子数量。
while(r- l >= 1e-4){
mid = (l + r) / 2;
ans = 0;
for(int i = 0 ; i < n ;++i){
ans += lines[i] / mid;
}
if(ans < K){ //长度为mid时数量不够， 减小 mid 这里减少0.01 ，同样精度只可以高，不可以少
r = mid - 0.01;
}else{ // 数量够了的时候，看能不能找到更大的。 这里加上0.01
l = mid + 0.01;
}
}
//最终答案为l。
printf("%.2f", (int)(l * 100) / 100.0); //取2位小数，之后的小数舍去。
return 0;
}
??3 导弹拦截——LIS
3.1 解题思路
这道题有两个问：
- 求一个最长非递增（注意是非递增）的子序列。
- 求一个最长递增子序列。
第一个问题我相信大家了解过LIS（最长递增子序列）的都应该能转化为LIS问题做，就是在一串数字中找出一个最长的递增子序列（不一定连续，但必须递增），用二分做（大家可以搜一下LIS的做法再来看这道题），当然也可以dp但时间复杂度较高。
第二个问题，求最少需要的系统个数能拦截所有的导弹，那么转化为最少的非递增子序列个数，也就是有多少个最长非递增子序列，这个命题等价于求最长递增子序列长度。（可以由狄尔沃斯定理得证，该定理断言：对于任意有限 偏序集 ，其最大 反链 中元素的数目必等于最小链划分中链的数目——百度）
3.2 代码贴贴
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int decre[100005]; //存储最长非递增子序列
int incre[100005]; //存储最长递增子序列
// x > y: 代表原序列是降序序列。 x < y:代表原序列是升序序列
int cmp(int x ,int y){
return x > y;
}
int main(){
int i = 0; //输入数据的个数。
int x;
while(cin>>x) a[i++] = x;
int len1 = 1;
int len2 = 1;
decre[0] = a[0];
incre[0] = a[0];
for(int j = 1; j < i ; ++j){
//求 最长不上升（后一个 小于等于 前一个） 子序列。
if(a[j] <= decre[len1-1]){
decre[len1++] = a[j];
}else{
//找到第一个 小于 a[j]的位置。= 没有意义，如5,3,2，来了个3，要使整个序列能添加的元素更多，那么肯定应该替换2才可以更多，如果替换3后面替换元素就会少一些。
//所以这里用upper_bound：找到第一个 > a[j]的数的位置
int pos = upper_bound(decre,decre+len1,a[j],cmp) - decre;
decre[pos] = a[j];
}
//求 最长递增（后一个严格 大于 前一个） 子序列。
if(a[j] > incre[len2-1]){
incre[len2++] = a[j];
}else{
//找到第一个 大于等于 a[j]的位置，才能满足递增。这里为什么要取大于等于，因为这是一个递增的，不能后面一个和前面一个相等，所以若遇到相等的要取出来把它替换掉。
//所以这里用lower_bound：找到第一个 >= a[j]的数的位置
int pos = lower_bound(incre,incre+len2,a[j]) - incre;
incre[pos] = a[j];
}
}
cout<<len1<<'\n'<<len2;
return 0;
}
