//法二：一条一条边的画  不断往里
#include
char s[150][150];
int main(){int n, x, y;scanf("%d", &n);x = 0;y = 0;for(int i = 0; i < 4*n + 5; i++){for(int j = 0; j < 4*n + 5; j++){s[i][j] = '.';}}for(int i = 0; i < n + 1; i++){//不断从最外层向里画'$' 最里就是十字for(int j = y + 2; j <= y + 4*(n - i) + 2; j++){//长度为4*(n-i)+1s[x][j] = '$';  }for(int j = x; j <= x + 2; j++){//左边竖着的s[j][y + 2] = '$';}for(int j = x; j <= x + 2; j++){//画十字时左右会重合s[j][y + 4*(n - i) + 2] = '$';}for(int j = y; j <= y + 2; j++){//左边横着的s[x + 2][j] = '$';}for(int j = y + 4*(n - i) + 2; j <= y + 4*(n - i) + 4; j++){s[x + 2][j] = '$';}for(int j = x + 2; j <= x + 4*(n - i) + 2; j++){//左边竖着的s[j][y] = '$';}for(int j = x + 2; j <= x + 4*(n - i) + 2; j++){s[j][y + 4*(n - i) + 4] = '$';}for(int j = y; j <= y + 2; j++){//左边横着的s[x + 4*(n - i) + 2][j] = '$';}for(int j = y + 4*(n - i) + 2; j <= y + 4*(n - i) + 4; j++){s[x + 4*(n - i) + 2][j] = '$';}for(int j = x + 4*(n - i) + 2; j <= x + 4*(n - i) + 4; j++){//左边竖着的s[j][y + 2] = '$';}for(int j =  x + 4*(n - i) + 2; j <= x + 4*(n - i) + 4; j++){s[j][y + 4*(n - i) + 2] = '$';}for(int j = y + 2; j <= y + 4*(n - i) + 2; j++){//横着的s[x + 4*(n - i) + 4][j] = '$';}x += 2;y += 2;}for(int i=0;i<4*n+5;i++){//我们找到了规律,层数为n,边长为4*n+5 for(int j=0;j<4*n+5;j++){printf("%c", s[i][j]);}printf("\n");}return 0;
}

04 使用sort排序讲解（c++）

从大到小排序：

1、前k名的平均数

通过“排序方法”来控制升序/降序：注意不要写等号

除3余数小的排前面：

结构体的构造函数

可以有默认参数

结构体的排序：

05 使用sort排序练习（c++）

1、距离整数最近的浮点数

#include
#include 
#include
using namespace std;
const double EPSILON = 1e-6;
double num[105];
bool cmp(double a, double b){double da = fabs(a - round(a));//fabs:给浮点数取绝对值 round:四舍五入double db = fabs(b - round(b));if(fabs(da - db) < EPSILON){//看作浮点数ab相等，按照浮点数大小排序 return a < b; } return da < db; 
}
int main(){	int n;scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%lf", &num[i]);}sort(num, num + n, cmp);for(int i = 0; i < n; i++){if(i != n - 1){printf("%lf ", num[i]);} else{printf("%lf\n", num[i]);}}return 0;
} 

2、分数线和获奖人数

3、一段升序一段降序

4、字符串按照字典序排列，输出可以串成的手链数量

5、每个数字的和

6、成绩排序

#include
#include 
#include
using namespace std;
struct Student{int num;int score;
};
bool cmp(Student a, Student b){return a.score > b.score; 
}
int main(){	Student stu[105];int n;scanf("%d", &n);for(int i = 0; i < n; i++){stu[i].num = i + 1;scanf("%d", &stu[i].score);}sort(stu, stu + n, cmp);for(int i = 0; i < n; i++){if(i != n -1)printf("%d ", stu[i].num);else printf("%d\n", stu[i].num);}return 0;
} 

7、摘气球（跳的矮的先摘）

#include
#include 
#include
using namespace std;
struct Children{int a;//跳起来的高度int id;
};
Children child[100005];
int h[100005];//记录气球的高度 
int ans[100005];//记录每个小朋友所摘的气球数量
bool used[1005];//记录气球有没有被摘过 
bool cmp(Children a, Children b){return a.a < b.a; 
}
int main(){	int n, m;scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%d", &child[i].a);child[i].id = i;}for(int i = 0; i < m; i++){scanf("%d", &h[i]);} sort(child, child + n, cmp);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(!used[j] && h[j] <= child[i].a){ans[child[i].id]++;used[j] = true;}} }for(int i = 0; i < n; i++){printf("%d\n", ans[i]);}return 0;
} 

降低复杂度：删除used数组，通过将气球排序来看能否摘到气球

int p = 0;//记录摘到第几个气球
sort(h, h + m);
for(int i = 0; i < n; i++){while(p < m && h[p] <= child[i].a){//可以摘到ans[child[i].id]++;p++;}
}

06 快速提升代码能力

1、进制转换

#include
using namespace std;
char ans[105];
int main(){	int N, R, m, now;cin >> N >> R;//N是整数 R是进制 if(N < 0){//如果输入了负数 cout << '-';N = -N;} m = 0;//是转换后的位数 while(N){now = N % R;//存每一位的数 if(now <= 9){//0-9 ans[m++] = '0' + now;}else{//A-Fans[m++] = 'A' + now - 10;}N /= R;}if(m == 0){cout << 0;}for(int i = m - 1; i >= 0; i--){//倒着输出 cout << ans[i];}cout << endl;return 0;
} 

2、判断回文

3、机器人走路 用数组表示方向巧妙

#include
using namespace std;
int dx[4] = {0, -1, 0, 1};//把方向用数组规定出来，就很灵活，方向是这题的难点 
int dy[4] = {1, 0, -1, 0};
char op[15];
int main(){	int n, d, x, nowx, nowy;cin >> n;//表示机器人移动多少步 d = 3;//起始朝向x轴正方向 nowx = 0;nowy = 0;for(int i = 0; i < n; i++){cin >> op >> x;if(op[0] == 'b'){//back：向后转 d = (d + 2) % 4; }else if(op[0] == 'l'){//left：向左转 d = (d + 1) % 4;}else if(op[0] == 'r'){//right：向右转 d = (d + 3) % 4;}nowx += dx[d] * x;//方向*距离 nowy += dy[d] * x;}cout << nowx << " " << nowy << endl;return 0;
} 

07 枚举算法讲解

1、比儿子大27岁，可能的解的个数

2、水仙花数

3、n-m之间的质数 注意swap()是c++自带的函数 注意可以把复杂度降到O(根号n)

4、枚举10位字符串

#include
#include
#include
using namespace std;
char op[15];
int main(){	srand(time(NULL));//利用系统时间，返回随机数 提供新的种子 char s[10];//如果是读入要给'\0'留位子 这里不用 for(int i = 0; i < 10; i++){s[i] = (char)(65 + rand() % 26);//随机产生一个10位的字符串 printf("%c", s[i]);}printf("\n");for(int i = 0; i < 10; i++){//复杂度26*10 纯枚举 for(int j = 0; j < 26; j++){if(s[i] == (char)(65 + j)){cout << (char)(65 + j);break;}}}return 0;
} 

5、回文数 并限定和

6、四叶玫瑰数：注意少用pow 比较奇怪 返回的是double

7、吹蜡烛：从某一岁开始吹

8、不含4

9、所有解

10、

小学数学寒假作业

#include
using namespace std;
int main(){	int a1, a2, a3, a4, a5, a6, a7, a8;//枚举左边8个数 int vis[14] = {0};//记录数字是否被使用int tot = 0;//记录结果for(a1 = 1; a1 <= 13; a1++){vis[a1] = 1;for(a2 = 1; a2 <= 13; a2++){if(a1 + a2 > 13 || vis[a2]){//不符合条件，剪枝 continue;}vis[a2] = 1;vis[a1 + a2] = 1;for(a3 = 1; a3 <= 13; a3++){if(vis[a3]){continue;}vis[a3] = 1;for(a4 = 1; a4 <= 13; a4++){if(a3 - a4 <= 0 || a3 - a4 >= 14 || vis[a4] || vis[a3 - a4] || a4 == a3 - a4){//注意不能重复 continue; }vis[a4] = 1;vis[a3 - a4] = 1;for(a5 = 1; a5 <= 13; a5++){if(vis[a5]){continue;}vis[a5] = 1;for(a6 = 1; a6 <= 13; a6++){if(a5 * a6 > 13 || vis[a6] || vis[a5 * a6] || a6 == a5 * a6){continue;}vis[a6] = 1;vis[a5 * a6] = 1;for(a7 = 1; a7 <= 13; a7++){if(vis[a7]){continue;}vis[a7] = 1;for(a8 = 1; a8 <= 13; a8++){if(vis[a8] || a7 < a8 || a7 % a8 != 0 || vis[a7 / a8] || a8 == a7 / a8){continue;}tot++;}vis[a7] = 0;//不断清0 }vis[a6] = 0;vis[a5 * a6] = 0;}vis[a5] = 0;}vis[a4] = 0;vis[a3 - a4] = 0;}vis[a3] = 0;}  vis[a2] = 0;vis[a1 + a2] = 0;}vis[a1] = 0;} printf("%d", tot);return 0;
} 

08 枚举算法练习

1、字典序最小 枚举abc 算出来d

2、最大的和（动态规划复杂度更低）

#include
using namespace std;
int a[1005];
int main(){	int n, sum, ans;cin >> n;for(int i = 0; i < n; i++){cin >> a[i];} sum = 0;ans = 0;for(int i = 0; i < n; i++){sum = 0;for(int j = i; j < n; j++){sum += a[j];if(sum > ans){ans = sum;}}}printf("%d\n", ans);return 0;
} 

3、双节棍 最大的差

09 常用STL讲解

动态数组vector

#include
#include 
using namespace std;
int main(){	vector vec;//可填入float double等不同数据类型vec.push_back(1);vec.push_back(3);//在尾部添加元素 for(int i = 0; i < vec.size(); i++){//用size()获取vector长度 cout << v[i] << endl;} vec.pop_back();//从尾部删除元素vec.clear();//清空vector 但不清空内存vector v;vector().swap(v);//可以清空内存：与空的vector交换 return 0;
} 

可以存储自定义数据

#include
#include 
using namespace std;
int main(){	//构造函数：定义长度和初始值int n = 10;vector vec(n, 1);//10个数都是1 如果不写默认是1//二维数组n = 5;vector > vec2;for(int i = 0; i < n; i++){vector x(i + 1, 1);vec2.push_back(x);} for(int i = 0; i < n; i++){for(int j = 0; j < vec2[i].size(); j++){cout << vec2[i][j] << " ";}cout << endl;}return 0;
} 

n个vector 其中每个vector有m个0 注意初始化

选正确的：123对 4错因为要传vector不能传0 1写法不好：前面5个都是0 push_back从第5个开始

乘法表

#include
#include 
using namespace std;
int main(){	vector > v2d;for(int i = 0; i < 5; i++){//5行 v2d.push_back(vector());} for(int i = 0; i < v2d.size(); i++){for(int j = 0; j <= i; j++){//第一行：1个 第二行：2个 2*1 2*2 v2d[i].push_back((i + 1) * (j + 1));}}for(int i = 0; i < v2d.size(); i++){for(int j = 0; j < v2d[i].size(); j++){cout << i + 1 << " * " << j + 1 << " = " << v2d[i][j] << "\t";}cout << endl;}return 0;
} 

锯齿数组：

#include
#include
using namespace std;
vector mat[10005];//这是开10005个vector动态数组的意思，代表每一行 
int main(){	int n, m, x, y;cin >> n >> m;for(int i = 0; i < m; i++){cin >> x >> y;mat[x].push_back(y);}for(int i = 1; i <= n; i++){for(int j = 0; j < mat[i].size(); j++){if(j != mat[i].size() - 1){cout << mat[i][j] << " ";}else{cout << mat[i][j];}}cout << endl;}return 0;
} 

集合set（有结构体时必须重载）

#include
#include 
using namespace std;
int main(){	set country;//插入、删除、查找都是对数复杂度 country.insert("China");//若插入重复元素，不会变country.erase("England");//若集合不存在该元素，删除也不会变if(country.count("China")){//如果集合存在该元素，返回1，不然返回0 cout << "China belong to country" << endl;} //set::iterator cit定义了一个指向set这种集合的迭代器it for(set::iterator it = country.begin(); it != country.end(); it++){//用!=做结尾 cout << *it << endl;//注意从小到大遍历 } cout << country.size() << endl;//获取大小 O(1) country.clear(); //清空 O(n) return 0;
} 

重载< 否则insert时不知道前面怎么排序的

//示例：重载< 让坐标从小到大排序
#include
#include 
using namespace std;
struct Point{int x, y;bool operator <(const Point &rhs) const{//重载从小到大 if(x == rhs.x){return y < rhs.y;}else{ return x < rhs.x;//优先x，再比y } }
};
int main(){	int n;set v;cin >> n;for(int i = 0; i < n; i++){Point temp; cin >> temp.x >> temp.y;v.insert(temp); } for(set::iterator it = v.begin(); it != v.end(); it++){cout << it -> x << " " << it -> y << endl;}return 0;
} 

比较罪犯：

#include
#include
using namespace std;
struct people{int h;int w;int age;people(int _h, int _w, int _age){//写构造函数，不用定义再逐个赋值，较简单 h = _h;w = _w;age = _age;}bool operator<(const people &rhs) const{//这里各种情况都要写全，否则会 if(h != rhs.h){return h < rhs.h;} if(w != rhs.w){return w < rhs.w;}return age < rhs.age;}
};
set s; 
int main(){	int n, m, h, w, age;cin >> n >> m;for(int i = 0; i < n; i++){cin >> h >> w >> age;s.insert(people(h, w, age));//人的特征不重复}for(int i = 0; i < m; i++){cin >> h >> w >> age;if(s.count(people(h, w, age))){//样例输出可以不连续输出 看找没找到罪犯cout << "yes" << endl;}else{cout << "no" << endl;}}return 0;
} 

映射表map

如果key存在了，再次insert，不会有任何改变 可用pair保存

访问：用数组访问 常用下标访问插入映射，而且可以更改
dict.count(“Mary”)

遍历：iterator

清空：clear()

#include
#include
#include

#include
#include
#include

10 常用STL练习

1、移积木

#include 
#include 
using namespace std;
vector v[10005];//10005个长度不限的数组
int main(){//归并排序的过程中求逆序对int n, m, a, b;scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){v[i].push_back(i);}for(int i = 0; i < m; i++){scanf("%d%d", &a, &b);if(a == b){continue;}for(int j = 0; j < v[b].size(); j++){v[a].push_back(v[b][j]);//把b位置所有积木移上去即可}vector().swap(v[b]);//把v[b]清掉}for(int i = 1; i <= n; i++){for(int j = 0; j < v[i].size(); j++){if(j != v[i].size() - 1){printf("%d ", v[i][j]);} else{printf("%d", v[i][j]);}}}return 0;
}

2、求并集 用集合即可insert iterator

3、依然注意set 插入用insert 找有没有元素用count

4、求出现次数最多的数：用map记录

5、嵌套的map

11栈和递归讲解

栈：先进后出

struct Stack{//自行实现int data[10000];int top = -1;void push(int x) {top++;if (top < 10000) {data[top] = x;} else {top--;cout << "stack overflow" << endl;}}void pop(){if(top >= 0){top--;}}int topval(){if(top >= 0){return data[top];}}
};

STL：stack

#include 
#include 
using namespace std;
int main(){stack s;s.push("123456");cout << s.size() << endl;while(!s.empty()){cout << s.top() << endl;s.pop();}return 0;
}

题1：火车出入站

题2：括号匹配

题3：给一个n个数的排列a，和一个栈，判断出栈顺序是否可以是排列a。

#include 
#include 
#include 
using namespace std;
int main(){int n;cin >> n;vector a(n);//这是期望的排列for(int i = 0; i < n; i++){cin >> a[i];}//如果不是a[0] 一直push 直到a[0]pop出来 如此循环stack s;int cur = 1;bool f = 1;//1代表可以 否则不行for(int i = 0; i < n; i++){//注意s为空时，s.top()会访问越界while((s.empty() || s.top() != a[i]) && cur <= n){s.push(cur);cur++;}if(s.empty() || s.top() != a[i]){//说明跳出条件是cur>nf = 0;//没有没有符合的排列break;} else{s.pop();//弹出期望的值}}if(f){cout << "legal" << endl;}else{cout << "illegal" << endl;}return 0;
}

13 深度优先搜索讲解

1、路径选择：看上下左右4个方向走不走得通 更简单：顺逆时针

#include 
#include 
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
bool in(int x, int y){return x >= 0 && x < n && y >= 0 && y < m;
}
bool dfs(int x, int y){if(maze[x][y] == 'T')return true;//到达终点vis[x][y] = 1;//记录成访问到maze[x][y] = 'm';int tx = x - 1, ty = y;//左if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){if(dfs(tx, ty))return true;}tx = x, ty = y - 1;//下if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){if(dfs(tx, ty))return true;}tx = x + 1, ty = y;//右;if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){if(dfs(tx, ty))return true;}tx = x, ty = y + 1;//上if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){if(dfs(tx, ty))return true;}vis[x][y] = 0;maze[x][y] = '.';//说明前面都走不通 还原return false;}
int main(){cin >> n >> m;for(int i = 0; i < n; i++){cin >> maze[i];//一共有n行}int x, y;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(maze[i][j] == 'S'){x = i, y = j;//遍历找到起点，赋值坐标}}}if(dfs(x, y)){for(int i = 0; i < n; i++){cout << maze[i] << endl;}} else{cout << "NO!" << endl;}return 0;
}

2、改进：用逆时针方向访问 新建数组来表示xy移动

int dir[4][2] = {{-1, 0}, {0, -1},{1, 0}, {0, 1}};
bool dfs(int x, int y){if(maze[x][y] == 'T')return true;//到达终点vis[x][y] = 1;//记录成访问到maze[x][y] = 'm';for(int i = 0; i < 4; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){if(dfs(tx, ty))return true;}}vis[x][y] = 0;maze[x][y] = '.';//说明前面都走不通 还原return false;
}

3、找路径，或求所有解，要取消路径
这里只用找有没有一条路径 所以不用取消路径

#include 
char s[10][10];//棋盘
int dir[8][2] = {{2, 1}, {1, 2},{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
bool vis[10][10];
bool f;
bool in(int x, int y){return x >= 0 && x < 10 && y >= 0 && y < 9;
}
void dfs(int x, int y){if(f)return;if(s[x][y] == 'T'){f = true;return;}vis[x][y] = true;for(int i = 0; i < 8; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(in(tx, ty) && s[tx][ty] != '#' && !vis[tx][ty]){dfs(tx, ty);}}//找路径，或求所有解，要取消路径//这里只用找一条路径 所以不用取消路径
}
int main(){int x, y;for(int i = 0; i < 10; i++){scanf("%s", s[i]);}for(int i = 0; i < 10; i++){for(int j = 0; j < 9; j++){if(s[i][j] == 'S'){x = i, y = j;//遍历找到起点，赋值坐标}}}dfs(x, y);if(f){printf("Yes");} else{printf("No");}return 0;
}

4、找第一题中的最小路径：新增step 每次比较：注意一定要还原路径！！！！

#include 
#include 
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0},{0, -1},{1, 0},{0, 1}};
int ans = 1000000000;
bool in(int x, int y){return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x, int y, int step){if(maze[x][y] == 'T'){if(step < ans){ans = step;}}vis[x][y] = 1;for(int i = 0; i < 8; i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){dfs(tx, ty, step + 1);}}vis[x][y] = 0;//找路径，或求所有解，要取消路径
}
int main(){cin >> n >> m;for(int i = 0; i < n; i++){cin >> maze[i];}int x, y;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(maze[i][j] == 'S'){x = i, y = j;//遍历找到起点，赋值坐标}}}dfs(x, y, 0);cout << ans << endl;return 0;
}

3、连续的#的最大个数

#include 
char mp[1005][1005];
bool vis[1005][1005];
int n, m;
int cnt;//存当前情况的
int ans;//存最大连续的#个数
void dfs(int x, int y){if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '.'){return;}vis[x][y] = true;//不用还原 因为找完这个片区就不用再找一次了cnt++;dfs(x - 1, y);dfs(x + 1, y);dfs(x, y  - 1);dfs(x, y + 1);
}
int main(){
//    找#连起来最大的路scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", mp[i]);}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(!vis[i][j] && mp[i][j] == '#') {cnt = 0;dfs(i, j);if(cnt > ans){ans = cnt;}}}}printf("%d\n", ans);
}

4、x y说明x是y的父母 输出每个点的子女数

#include 
#include 
using namespace std;
vector son[100005];
bool f[100005];
int ans[100005];
int dfs(int u){int ret = 0;for(int i = 0; i < son[u].size(); i++){ret += dfs(son[u][i]);//直系后代是每个后代的直系后代之和}ans[u] = ret;//将后代数存到数组里return ret + 1;
}
int main(){int n, x, y, u;scanf("%d", &n);//此题有n个人for(int i = 0; i < n - 1; i++){scanf("%d%d", &x, &y);son[x].push_back(y);f[y] = true;//说明不是根节点}for(int i = 1; i <= n; i++){if(!f[i]){u = i;//找到根节点break;}}dfs(u);for(int i = 1; i <= n; i++){printf("%d\n", ans[i]);}return 0;
}

5、马可以走到的位置

#include 
using namespace std;
char s[105][105];
int n, m;
int dir[8][2] = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1},{1, 2}, {1, -2},{-1, 2},{-1, -2}};
void dfs(int x, int y, int step){if(step > 3)return;if(x < 0 || x >= n || y < 0 || y >= m){return;}s[x][y] = '#';for(int i = 0; i < 8; i++){dfs(x + dir[i][0], y + dir[i][1], step + 1);}}
int main(){int x, y;scanf("%d%d%d%d", &n, &m, &x, &y);//此题有n个人for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){s[i][j] = '.';}}dfs(x - 1, y - 1, 0);//把马的初始位置传入for(int i = 0; i < n; i++){printf("%s\n", s[i]);}return 0;
}

14 深度优先搜索练习

1、需要几个人搜草丛：看草丛的数量

5 6
.#…
…#…
…#…#
…##.
.#…

#include 
char mp[105][105];
bool vis[105][105];
int n, m;
void dfs(int x, int y){//会把连起来的#一次性访问，形成草地if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '.'){return;}vis[x][y] = true;dfs(x - 1, y);dfs(x + 1, y);dfs(x, y  - 1);dfs(x, y + 1);
}
int main(){int cnt = 0;scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", mp[i]);}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(!vis[i][j] && mp[i][j] == '#'){dfs(i, j);cnt++;}}}printf("%d\n", cnt);
}

2、迷宫解 所有的情况

#include 
char mp[15][15];
bool vis[15][15];
int n, m, x, y;
int ans;
void dfs(int x, int y){if(x < 0 || x >= n || y < 0 || y >= m || vis[x][y] || mp[x][y] == '#'){return;}if(mp[x][y] == 'e'){ans++;return;}vis[x][y] = true;dfs(x - 1, y);dfs(x + 1, y);dfs(x, y  - 1);dfs(x, y + 1);vis[x][y] = false;//记得还原
}
int main(){scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", mp[i]);}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(mp[i][j] == 's'){x = i;y = j;}}}dfs(x, y);printf("%d\n", ans);
}

15 抽象深度优先搜索讲解

1、N个数，选k个数，和为N 复杂度为O(2^n)

方法一：其实有点像递归 是否选择第i个数

#include 
using namespace std;
int n, k, sum, ans;
int a[40];
void dfs(int i, int cnt, int s){//i：搜素到第几层 cnt:用了几个数 s:sumif(i == n){if(cnt == k && s == sum){ans++;}return;}dfs(i + 1, cnt, s);//不选这个数dfs(i + 1, cnt + 1, s + a[i]);//选这个数
}
int main(){cin >> n >> k >> sum;for(int i = 0; i < n; i++){cin >> a[i];}ans = 0;//方案数dfs(0, 0, 0);cout << ans << endl;return 0;
}

方法二：从剩下的数中选择一个数 依然是遍历 注意恢复xuan[]

结果是方法一的k!倍 因为这里把235 253 这样的算不同的方法 复杂度为O(n^k)

#include 
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
void dfs(int s, int cnt){//cnt：个数 s:sumif(cnt == k && s == sum){ans++;}for(int i = 0; i < n; i++){if(!xuan[i]){xuan[i] = 1;dfs(s + a[i], cnt + 1);xuan[i] = 0;}}return;}
int main(){cin >> n >> k >> sum;for(int i = 0; i < n; i++){cin >> a[i];}ans = 0;//方案数dfs(0, 0);cout << ans << endl;return 0;
}

2、等边三角形问题：依然用从剩下的数中选择一个数的方法，所以要恢复

#include 
int n, sum = 0;
bool f;//标记能不能构成等边三角形
bool vis[15];//标记每根木棍有没有被选
int p[15];
void dfs(int cnt, int s){if(f)return;if(cnt == 3){//cnt：记录边数f = true;return;}if(s == sum / 3){//s：记录当前的和dfs(cnt + 1, 0);return;}for(int i = 0; i < n; i++){if(!vis[i]){vis[i] = true;dfs(cnt, s + p[i]);//从剩下的数中选择一个数的方法vis[i] = false;}}
}
int main(){scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d", &p[i]);sum += p[i];}if(sum % 3 != 0){//凑等边三角形 显然要是3的倍数printf("no");} else{dfs(0, 0);if(f)printf("yes");else printf("no");}return 0;
}

3、依然用-搜索-还原 注意对角线用的是行+列的值来记录！很巧妙

#include 
using namespace std;
int ans = 0;//记录可能性
bool col[10], x1[20], x2[20];//分别是 列 正对角线 反对角线 20：因为记录的是行+列的值
bool check(int r, int i){return !col[i] && !x1[r + i] && !x2[r - i + 8];
}
void dfs(int r){//r是行数if(r == 8){ans++;return;}for(int i = 0; i < 8; i++){//这里的棋盘是8*8 分别看与现有的8行是否冲突if(check(r, i)){col[i] = x1[r + i] = x2[r - i + 8] = true;// r - i可能为负数，所以加8dfs(r + 1);col[i] = x1[r + i] = x2[r - i + 8] = false;}}}
int main(){dfs(0);//从第1行开始cout << ans << endl;return 0;
}

17 深搜的剪枝策略讲解

1、把不可能的去掉

2、最优解：不可能得到比当前更优的解，就减掉

3、重复性剪枝：123 132这样的全排列不需要

解决：选择时按位置递增来选

4、奇偶性剪枝：走过的位置会塌陷，不能走多次；并判断能否在时间T到达门口

#include 
using namespace std;
const int N = 10;
int n, m, T;
char mat[N][N];//迷宫
bool vis[N][N];//标识是否走过
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
bool ok;//标识能不能走
void dfs(int x, int y, int t){//t记录时间if(ok)return;if(t == T){if(mat[x][y] == 'D') ok = true;return;}vis[x][y] = true;for(int i = 0; i < 4; i++){//4个方向都试一下int tx = x + dx[i];int ty = y + dy[i];if(tx < 0 || tx >= n || ty < 0 || ty >= m || mat[tx][ty] == 'X' || vis[tx][ty])continue;//无效的情况dfs(tx, ty, t + 1);}vis[x][y] = false;//恢复
}
int main(){cin >> n >> m >> T;for(int i = 0; i < n; i++){cin >> mat[i];}int sx, sy, ex, ey;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(mat[i][j] == 'S') sx = i, sy = j;//起点if(mat[i][j] == 'D') ex = i, ey = j;//终点}}//奇偶性剪枝 颜色一样->偶数步->T为偶 颜色不同->奇数步->T为奇if((sx + sy + ex + ey + T) % 2 != 0)cout << "NO" <

#include 
#include 
using namespace std;
int n, m;
char mat[1010][1010];//迷宫
bool row[1010], col[1010];//标识是否走过 注意每行每列都只用看一遍！！！
void boom(int x,int y){//每个格子只检查一遍mat[x][y] = 0;//指没有炸弹if(!row[x]){row[x] = true;for(int i = 0; i < m; i++){if(mat[x][i] == '1') boom(x, i);}}if(!col[y]){col[y] = true;for(int i = 0; i < n; i++){if(mat[i][y] == '1') boom(i, y);}}
}int main(){cin >> n >> m;for(int i = 0; i < n; i++){scanf("%s", mat[i]);}int cnt = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(mat[i][j] == '1'){cnt++;boom(i, j);}}}cout << cnt <

#include 
#include 
using namespace std;
int main(){queue q;q.push(1);//向队尾插入元素cout << q.front() << endl;//获取队首元素q.pop();//队首元素出队q.empty();//判断队列是否为空//注意队列没有clear()方法 所以要循环while (!q.empty()){q.pop();}return 0;
}

#include 
#include 
using namespace std;
int main(){int n, m;cin >> n >> m;queue q;for(int i = 1; i <= n; i++){q.push(i);}int cur = 1;while (q.size() > 1){int x = q.front();q.pop();if(cur == m){//如果是就正好pop出去了cur = 1;}else{//如果不是就从队首移到队尾q.push(x);cur++;}}cout << q.front() << endl;return 0;
}

#include 
#include 
#include 
using namespace std;
int n, m;
string maze[110];
bool vis[110][110];
int dir[4][2] = {{-1, 0},{0, -1},{1, 0},{0, 1}};
int ans = 1000000000;
bool in(int x, int y){return x >= 0 && x < n && y >= 0 && y < m;
}
struct node{//定义结构体，存xy坐标和步数int x, y, d;node(int xx, int yy, int dd){x = xx;y = yy;d = dd;}
};
int bfs(int sx, int sy){queue q;q.push(node(sx, sy, 0));vis[sx][sy] = true;while (!q.empty()){node now = q.front();q.pop();for(int i = 0; i < 4; i++){int tx = now.x + dir[i][0];int ty = now.y + dir[i][1];if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){if(maze[tx][ty] == 'T'){return now.d + 1;//到达终点，当前步数+1} else{vis[tx][ty] = true;q.push(node(tx, ty, now.d + 1));}}}}return -1;
}
int main(){cin >> n >> m;for(int i = 0; i < n; i++){cin >> maze[i];}int x, y;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if(maze[i][j] == 'S'){x = i, y = j;//遍历找到起点，赋值坐标}}}cout << bfs(x, y) << endl;return 0;
}

#include 
#include 
using namespace std;
queue> q;
bool vis[5005];//坐标轴上的坐标
int main(){int n, A, B, now, step;//坐标轴长度 起点 终点scanf("%d%d%d", &n, &A, &B);q.push(make_pair(A, 0));vis[A] = true;while (!q.empty()){now = q.front().first;step = q.front().second;q.pop();if(now == B){printf("%d", step);}if(now + 1 <= n && !vis[now + 1]){//向前一步q.push(make_pair(now + 1, step + 1));vis[now + 1] = true;}if(now - 1 >= 0 && !vis[now - 1]){//向后一步q.push(make_pair(now - 1, step + 1));vis[now - 1] = true;}if(now * 2 <= n && !vis[now * 2]){//两倍q.push(make_pair(now * 2, step + 1));vis[now * 2] = true;}}return 0;
}

#include 
using namespace std;
int dir[8][2] = {{2, 1}, {1, 2},{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
bool d[30][30];//标记马的控制点
long long dp[30][30];//从(0,0)到该点的路径条数
int main(){//A:(0,0) B:(n,m) 需算出A到B的路径条数 马在(cx,cy)int n, m, cx, cy;cin >> n >> m >> cx >> cy;d[cx][cy] = true;//马的位置for(int i = 0; i < 8; i++){int tx = cx + dir[i][0];int ty = cy + dir[i][1];if(tx >= 0 && tx <= n && ty >= 0 && ty <= m){d[tx][ty] = true;//把马的8个位置都标记出来}}dp[0][0] = 1;for(int i = 0; i <= n; i++){//要到(n,m)for(int j = 0; j <= m; j++){if(d[i][j] == false){//如果该点不受马控制if(i){//如果i >= 1 dp[i][j] += dp[i - 1][j];//向下走}if(j){dp[i][j] += dp[i][j - 1];//向右走}}}}cout << dp[n][m] << endl;return 0;
}

#include 
#include 
using namespace std;
const int inf = 0x7fffffff;
int num[101];
int main(){int n;cin >> n;for(int i = 0; i < n; i++){cin >> num[i];}int ans = -inf;for(int i = 0; i < n; i++){ans = max(ans, num[i]);//这里可以找到数组中的最大值}if(ans <= 0){//说明都是负数，最大字段和就是最小的负数cout << ans << endl;} else{int sum = 0;for(int i = 0; i < n; i++){if(sum + num[i] < 0){sum = 0;} else{sum += num[i];}ans = max(ans, sum);//存最大数}cout << ans << endl;}
}

#include 
#include 
using namespace std;
int dp[110][110];
string a, b;
int main(){cin >> a >> b;int lena = a.size();int lenb = b.size();//处理边界情况for(int i = 1; i <= lena; i++){dp[i][0] = i;}for(int i = 1; i <= lenb; i++){dp[0][i] = i;}//运用递推式for(int i = 1; i <= lena; i++){for(int j = 1; j <= lenb; j++){if(a[i - 1] == b[j - 1]){dp[i][j] = dp[i - 1][j - 1];} else{dp[i][j] = min(min(dp[i][j - 1],  dp[i - 1][j]), dp[i - 1][j - 1]) + 1;}}}cout << dp[lena][lenb] << endl;return 0;
}

#include 
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main(){int N, V;cin >> N >> V;for(int i = 1; i <= N; i++){cin >> w[i] >> c[i];}for(int i = 1; i <= N; i++){for(int j = 0; j <= V; j++){if(j >= c[i]){//放这个物体dp[i][j] = max(dp[i - 1][j - c[i]] + w[i], dp[i - 1][j]);} else{//不放这个物体dp[i][j] = dp[i - 1][j];}}}cout << dp[N][V] << endl;return 0;
}

#include 
using namespace std;
int dp[1010];
int w[21], c[21];
int main(){int N, V;cin >> N >> V;for(int i = 1; i <= N; i++){cin >> w[i] >> c[i];}//这里要从大到小，才能保证更新的顺序正确for(int i = 1; i <= N; i++){for(int j = V; j >= c[i]; j--){dp[j] = max(dp[j - c[i]] + w[i], dp[j]);}}cout << dp[V] << endl;return 0;
}

#include 
using namespace std;
int dp[21][1010];
int w[21], c[21], n[21];
int main(){int N, V;cin >> N >> V;for(int i = 1; i <= N; i++){cin >> w[i] >> c[i] >> n[i];}for(int i = 1; i <= N; i++){for(int j = 0; j <= V; j++){for(int k = 0; k <= n[i]; k++){if(j >= c[i]*k){dp[i][j] = max(dp[i - 1][j - c[i]*k] + w[i]*k, dp[i][j]);}}}}cout << dp[N][V] << endl;return 0;
}

#include 
using namespace std;
int dp[1010];
int w[21], c[21], n[21];
int main(){int N, V;cin >> N >> V;for(int i = 1; i <= N; i++){cin >> w[i] >> c[i] >> n[i];}for(int i = 1; i <= N; i++){for(int j = V; j >= 0; j--){for(int k = 0; k <= n[i]; k++){if(j >= c[i]*k){dp[j] = max(dp[j - c[i]*k] + w[i]*k, dp[j]);}}}}cout << dp[V] << endl;return 0;
}

#include 
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main(){int N, V;cin >> N >> V;for(int i = 1; i <= N; i++){cin >> w[i] >> c[i];}for(int i = 1; i <= N; i++){for(int j = 0; j <= V; j++){if(j >= c[i]){//拿这一次的更新？dp[i][j] = max(dp[i][j - c[i]] + w[i], dp[i - 1][j]);}else{dp[i][j] = dp[i - 1][j];}}}cout << dp[N][V] << endl;return 0;
}

#include 
using namespace std;
int dp[1010];
int w[21], c[21];
int main(){int N, V;cin >> N >> V;for(int i = 1; i <= N; i++){cin >> w[i] >> c[i];}for(int i = 1; i <= N; i++){for(int j = c[i]; j <= V; j++){dp[j] = max(dp[j - c[i]] + w[i], dp[j]);}}cout << dp[V] << endl;return 0;
}

#include 
using namespace std;
int main(){int n, x, ans = 0, a[30];cin >> n >> x;for(int i = 0; i < n; i++){cin >> a[i];//输入n个数}//类比dp[1 << n] 开了dp[2^n] 这样开n维数组变成开1维for(int i = 0; i < (1 << n); i++){//遍历i，i把n位组合都取到int num = 0;for(int j = 0; j < n; j++){if(i & (1 << j)){//代表是否选择了第j个整数num += a[j];}}if(num == x){ans++;}}cout << ans << endl;return 0;
}

#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int dist[20][20];
int dp[1 << 16][20];//第1位：经过了哪些人的手(最多16人) 第2位：现在在谁手上
int main(){int n;cin >> n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> dist[i][j];if(dist[i][j] == -1) dist[i][j] = INF;}}//如果是Floyd:每个点不一定只经过一遍，所以赋值成最短路径即可，不用管中间怎么走for(int k = 0; k < n; k++){for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}memset(dp, 0x3f, sizeof(dp));dp[1][0] = 0;//因为是一个环，所以从哪里开始不重要for(int s = 0; s < (1 << n); s++){for(int i = 0; i < n; i++){if(s & (1 << i)){for(int j = 0; j < n; j++){if(j != i && (s & (1 << j))){dp[s][i] = min(dp[s][i], dp[s ^ 1 << i][j] + dist[j][i]);//^相当于做减法}}}}}int ans = INF;for(int i = 1; i < n; i++) {//不知道从谁开始传代价最小，所以遍历ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]);}if(ans == INF) ans = -1;cout << ans << endl;return 0;
}

#include 
using namespace std;
const int N = 1e4 + 9;
int a[N], n, m;
int binary_search(int x){int l = 0, r = n - 1;while(l <= r){int mid = (l + r) >> 1;//除以2if(a[mid] == x)return mid;if(a[mid] < x){l = mid + 1;} else{r = mid - 1;}}return -1;
}
int main(){cin >> n;for(int i = 0; i < n; i++){cin >> a[i];}cin >> m;while(m--){int x;cin >> x;cout << binary_search(x) << endl;}return 0;
}

#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int a[20][20];
int dp[1 << 16][20];//第1位：经过了哪些人的手(最多16人) 第2位：现在在谁手上
int main(){int n;cin >> n;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> a[i][j];}}memset(dp, 0x3f, sizeof(dp));for(int i = 0; i < n; i++){dp[1 << i][i] = 0;//初始状态}for(int i = 0; i < (1 << n); i++){for(int j = 0; j < n; j++){if(i & (1 << j)){//如果传过了这个人的手for(int k = 0; k < n; k++){if(!(i & (1 << k))){//状态转移方程：j传球给kdp[i | 1 << k][k] = min(dp[i | 1 << k][k], dp[i][j] + a[j][k]);}}}}}int ans = INF;for(int i = 0; i < n; i++) {//不知道从谁开始传代价最小，所以遍历ans = min(ans, dp[(1 << n) - 1][i]);}cout << ans << endl;return 0;
}

#include 
#include 
#include 
using namespace std;
const double eps = 1e-3;
double f(double x){return pow(x, 4) + 5 * pow(x, 3) + 6 * pow(x, 2) + 7 * x + 4;
}
double cal(double y){if(f(0) > y || f(100) < y){//因为这里是单增的return -1;}double l = 0, r = 100;while (r - l > eps){double mid = (l + r) / 2;if(f(mid) > y) r = mid;else l = mid;}return l;
}
int main(){double y;cin >> y;printf("%.3f\n", cal(y));return 0;
}

#include 
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];
bool check(int x){//当最大数为x时，有几组int now = 0, cnt = 0;for(int i = 0; i < n; i++){if(now + a[i] > x){cnt++;now = a[i];} else{now += a[i];}}return cnt <= k;
}
int cal(int l, int r){//最大数肯定在l-r之间取while(l < r){int mid = (l + r) >> 1;if(check(mid)){r = mid;//是合法的，可以继续找}else{l = mid + 1;}}return l;
}
int main(){int ma = -inf, sum = 0;cin >> n >> k;for(int i = 0; i < n; i++){cin >> a[i];ma = max(ma, a[i]);sum += a[i];}cout << cal(ma, sum) << endl;return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 1e3 + 9;
const double eps = 1e-7;
int n, k;
double a[N], b[N], tmp[N];
double g(double v){//f=比值=v ∑ai-v∑bi>=0 对v进行二分for(int i = 0; i < n; i++){tmp[i] = a[i] - v * b[i];}sort(tmp, tmp + n);double sum = 0;for(int i = k; i < n; i++){//选择最大的n-k个进行求和sum += tmp[i];}return sum;
}
double cal(){//找比值的最大值double l = 0, r = 1e10;while (r - l > eps){double mid = (l + r) / 2;if(g(mid) > 0){//当前的v小了l = mid;} else{//当前的v太大了r = mid;}}return l;
}
int main(){cin >> n >> k;for(int i = 0; i < n; i++){cin >> a[i];}for(int i = 0; i < n; i++){cin >> b[i];}printf("%.2f\n", cal());return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！