分类算法下的文章

2024-05-08

(DFS) Depth-First Search入门 Depth-First Search简称DFS，深度优先搜索。深度优先，优先在于深度，尽量往最深处走。原理:从某一节点开始走，若遇到分支，选择某条路冲到底，遇到分支就随便选只管冲冲冲，直到冲到底再无选择，然后按原路返回如果再遇到分支且有没走过的路，依然冲冲冲。直到全部都搜索完。 DFS 就如《葬送的芙莉莲》中芙莉莲与勇者探索迷宫的精神，攻略迷宫要将迷宫全部探索完才是迷宫寻宝的真正魅力！！！如题【入门】扫地机器人我们根据题意可以知道n与m的值为2~9，所以二维数组可以开a11即使nm为最大时依然可以在周围留一圈0，反正判断时越界等问题。根据题意我们需要设置一个判断规则: 按右下左上的优先级进行判断。下面给出AC代码#include<iostream> #include<vector> using namespace std; const int N = 11;//因为n和m是2~9的数所以周围留下了一圈 int n,m; vector<vector<int> >a(N,vector<int>(N, 0)); //递归深搜 void dfs(int x, int y, int k)//为（x,y）赋k值 { a[x][y] = k; //按照题目要求的右下左上的顺序依次设计判断x与y的加减依次对应了右下左上 if(y + 1 <= m && a[x][y + 1] == 0){ dfs(x, y + 1, k + 1); }else if(x + 1 <= n && a[x + 1][y] == 0){ dfs(x + 1, y, k + 1); }else if(y - 1 > 0 && a[x][y - 1] == 0){ dfs(x, y - 1, k + 1); }else if(x - 1 > 0 && a[x - 1][y] == 0){ dfs(x - 1, y, k + 1); } } int main() { std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); //输入行列 cin >> n >> m; //赋初值 dfs(1, 1, 1);//依题意设计函数dfs为(1,1)赋值为1,dfs函数赋值的点是我们搜索开始的最初点 //输出 for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ printf("%3d",a[i][j]); } printf("\n"); } }

2024年05月08日
11 阅读
0 评论
0 点赞

2024-05-07

二分法二分查找本质上是按照某一性质每次一分为二查找左右边界普通的二分查找题目题目解释:在一组有序无重复数组中查找某一个数，如果能查找到输出这个数是第几个数，否则输出-1. 我们可以使用二分法进行查找，即将数组一分为二，从中间的数进行判断是否大于或小于我们要查找的数，因为数组是有序递增的，所以如果中间数大于查找的数我们便查找左部分的数否则查找右部分的数。代码示例:#include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int l = 1, r = n;//因为数组大小为n所以左右边界为(1,n) int x; cin >> x;//输入要查找的数 while (l < r)//设置跳出循环的条件，即当l=r时退出循环 { int mid = (l + r) >> 1;//(l+r)/2,对中间数进行向下取整 if (a[mid] >= x)r = mid; //如果查询的数小于等于中间数，查询左部分，将右边界向左移 else l = mid + 1; //如果查询的数大于中间数，查询右部分，将左边界向右移，因为数组mid对应的数不对所以再右移一位 } //l下标对应的即是最后的查找 if (a[l] == x) cout << l << '\n'; else cout << -1 << '\n'; return 0; }二分查找左右边界二分查找左边界二分查找右边界题目解释:左右边界意思是最左或最右，或者最小或最大。如一组数12333445，查找3的左边界，答案为3.查找3的右边界，答案为5二分查找左边界左边界代码://二分查找左边界 #include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int y; cin >> y; while (y--) { int x; cin >> x; int l = 1, r = n; while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= x)r = mid; else l = mid + 1; } if (a[l] == x)cout << l << ' '; else cout << -1 << ' '; } return 0; }可以看到查找左边界和普通二分查找原理相同，稍有的不同只是因为题目的需求不同，实际上普通二分查找是查找左右边界的特例，只不过是因为数组中的数是否重复而不同下面给出右边界代码:#include<iostream> #include<vector> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; vector<int>a(n + 1); for (int i = 1; i <= n; i++)cin >> a[i]; int y; cin >> y; while (y--) { int x; cin >> x; int l = 1, r = n; while (l < r) { int mid = (l + r + 1) >> 1;//1.注意，如果 l=r-1 && nums[mid] <= target 此时l不能变化，进入死循环因此 mid更新应该改变，即 +1 if (a[mid] <= x)l = mid;//2.注意 else r = mid - 1;//注意 } if (a[l] == x)cout << l << ' '; else cout << -1 << ' '; } return 0; }注意代码中的注意，为与左边界不同的地方 1.如果 l=r-1 && nums[mid] <= target 此时l不能变化，进入死循环，因此 mid更新应该改变，即 +12.l不能+1,如果r=l+1，可能存在mid =r =l +1让循环进入死循环3.r-1是因为当前mid对应的数不为查找的数查找最小值用左边界，查找最大值用右边界左右边界的不同可以简单记忆为:左加右减二分答案-以伐木工为例伐木工咋一看与二分无关，如果直接暴力容易超时，因此使用二分法。具体思路为写一个check函数判断当前高度以上的数相加是否符合所需的木材此时的左右边界设置为0与最高高度的树，因为我们需要求的是伐木的高度，因此我们使用的二分法是求右边界，边界范围只与给出树的最高高度有关，再高就不礼貌了。代码示例#include<iostream> #include<vector> using namespace std; using ll = long long; bool check(ll mid, ll n, ll m, vector<ll>& a) { ll num = 0;//num求a中mid高度以上的树的和 for (ll i = 1; i <= n; i++) { if (a[i] > mid)num += (a[i] - mid); if (num >= m)return true;//如果相加的木材长度大于或等于需要的木材长度，返回true，继续增加高度 } return false; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, m; cin >> n >> m; vector<ll>a(n + 1); for (ll i = 1; i <= n; i++)cin >> a[i]; ll l = 0;//左边界 //找出最高的树作为右边边界 ll r = a[0]; for (ll i = 1; i <= n; i++) r = max(r, a[i]); //二分查找右边界 while (l < r) { ll mid = (l + r + 1) >> 1; if (check(mid, n, m, a)) l = mid; else r = mid - 1; } cout << l << '\n'; return 0; }洛谷-进击的奶牛题解本题查找相邻两头牛最大的最近距离，因此使用右边界选择好使用哪种二分后想想该怎么具体实现。我们想要对首先我们需要对输入的数组进行排序，然后取 l 为 1 ， r 为一个很大的值即可。 check 函数中我们需要定义一个 num 对间隔距离进行求和，当 num>=mid 时对牛牛数量进行加 1 并且让 num为0 ，重新计数，直到牛牛的数量 >= 输入的奶牛的数量 c 。示例代码//洛谷进击的奶牛 #include<iostream> #include<vector> #include<algorithm> using namespace std; const int N=0x3f3f3f3f; using ll = long long; ll n, c; vector<ll>a(1); bool check(ll mid){ ll num = 0; ll nn = 1; for(ll i = 2; i <= n; i++){ num += a[i] - a[i - 1]; if(num >= mid) { nn++; num = 0; } if(nn >= c) return true; } return false; } int main() { std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n >> c; a.resize(n + 1); for(ll i = 1;i <= n; i++) cin >> a[i]; sort(a.begin(), a.end()); ll l = 0,r = N; while(l < r){ ll mid = (l + r + 1) >> 1; if(check(mid)) l = mid; else r = mid - 1; } cout << l <<'\n'; return 0; }

2024年05月07日
12 阅读
0 评论
0 点赞

2024-05-01

递归模拟题目描述 Dr. JYY has just created the Coffee Chicken strings, denoted as S(n). They are quite similar to the Fibonacci soup --- today's soup is made by mingling yesterday's soup and the day before yesterday's soup:S(1)="COFFEE";S(2)="CHICKEN";S(n) = S(n-2) :: S(n-1), where :: denotes string concatenation.The length of S(n) quickly gets out of control as n increases, and there would be no enough memory in JYY's game console to store the entire string. He wants you to find 10 contiguous characters in S(n), starting from the kth character.输入描述: The first line of input is a single integer T (1≤T≤1000), denoting the number of test cases. Each of the following T lines is a test case, which contains two integers n, k (1≤n≤500,1≤k≤min{∣S(n)∣,10^12 }). |S| denotes the length of string S. 输出描述: For each test case, print the answer in one line. If there are no enough characters from the kth character, output all characters until the end of the string. 示例1 输入 247 输出 FEECHICKENN题解题目与斐波那契数列有关但是因为Sn的增长到后面过于爆炸，因此不能直接求Sn然后求十个字符需要转换一下,请观察下面的规律A 1 B 1 AB 2 BA 3 ABBAB 5 BABABBAB 8 ABBABBABABBAB 13 BABABBABABBABBABABBAB 21 ABBABBABABBABBABABBABABBABBABABBAB 34 BABABBABABBABBABABBABABBABBABABBABBABABBABABBABBABABBAB 45可以知道当前指向的位置大于a[n-2]就可以求a[n-1]的第k-a[n-2]个数（上面的数一数），如果小于等于a[n-2]就等于求a[n-2]的第几个数代码示例 #include<iostream> using namespace std; using ll = long long; ll a[700]; //mello函数记录Sn的字符串长度的值 void mello() { a[1] = 6;//6是COFFEE的长度 a[2] = 7;//7是CHICKEN的长度 for (int i = 3; i <= 60; i++) { a[i] = a[i - 1] + a[i - 2];//循环记录Sn的长度 } } int main() { mello(); int t; cin >> t; while (t--) { ll n, k; cin >> n >> k; //对于大于60的n，我们只需要取小的值替代即可，奇数用59，偶数用58 //为什么用60？因为k最多到1e12，当Sn大于58时长度就超过了1e12 if (n >= 60) { if (n % 2) n = 59; else n = 58; } for (ll i = k; i <= a[n] && i < k + 10; i++) { ll w = i, v = n;//w追踪当前位置，v追踪当前序列项 while (v != 1 && v != 2) {//不断递归减小，直到v选择COFFEE或CHICKEN if (w > a[v - 2]) { w = w - a[v - 2]; v -= 1; } else { v -= 2; } } if (v == 1) printf("%c", "COFFEE"[w - 1]); else if (v == 2) printf("%c", "CHICKEN"[w - 1]); } printf("\n"); } return 0; }

2024年05月01日
9 阅读
0 评论
0 点赞

2024-04-28

2024年04月28日
9 阅读
0 评论
1 点赞

2024-04-22

简单的背包问题描述小冯有个存储重量为m的空间存储袋，现在有n件物品，每件物品的重量为w，价值为v。问小冯最多能装的最大价值为多少？输入第一行输入两个数m、n，（1<=n,m<=1000）n表示物品数量，m表示存储袋的最大重量;接下来的n行，每行输出w,v,(1<=w,v <= 100)分别表示物品的重量，物品的价值; 输出输出小冯能装的物品最大价值; 样例输入 70 371 10069 11 2 样例输出 3题解利用动态空间规划可以建立一个二维数组存储物品价值，行为物品个数，列为重量比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大否则返回上一个物品的价值个数/重量01230000010000200003000040000放入第一个物品重量为1，价值为2个数/重量01230000010222200003000040000放入第二个物品重量为2，价值为4个数/重量01230000010222202463000040000代码实例#include<iostream> #include<cstdlib> using namespace std; int m, n, i, j; int w[1000], c[1000], f[1000][1000]; int main() { cin >> m >> n;//m代表背包最大能装的重量，n代表物品的数量 for (i = 1; i <= n; i++) { cin >> w[i] >> c[i];//输入每个物品的重量和价值 } //i控制物品，j控制重量 for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (j >= w[i]) { f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]); } else{ f[i][j] = f[i - 1][j]; } } } cout << f[n][m] << endl; return 0; }vector版：#include<iostream> #include<vector> #include<cstdlib> using namespace std; int n, w, i, j; int main() { cin >> w >> n; //定义容器行为几号物品，列为重量 vector<vector<int>>f(n + 1, vector<int>(w+1,0)); //定义重量与价值的容器 vector<int>weight(n +1); vector<int>price(n + 1); //输入 for ( i = 1; i <= n; i++) { cin >> weight[i] >> price[i]; } for (i = 1; i <= n; i++) { for (j = 1; j <= w; j++) { if (j >= weight[i]) { f[i][j] = max(f[i - 1][j - weight[i]] + price[i], f[i - 1][j]);//比较和比这个物品重量小的物品的价值的和，和上一个物品价值的值哪个大 } else { f[i][j] = f[i - 1][j];//否则返回上一个物品的价值 } } } cout << f[n][w] << "\n"; return 0; }

2024年04月22日
6 阅读
0 评论
0 点赞