单调栈 (单调栈模板题)题目描述给定一个长度为n的整数数组a，你需要求出每个元素的左边离它最近且比它小的元素。输入描述第一行：一个整数n(1≤n≤2×10^5)第二行：n个整数，表示整数数组a.(1≤a≤10^9)输出描述共一行，n个整数，表示每个元素的左边第一个比它小的元素，若不存在则为−1。输入样例157 8 5 6 7输出样例1-1 7 -1 5 6我们可以使用STL中的stack实现思路主要为将数组中的数值于栈中的数值进行对比，但栈中的数组比数组中的值大时，我们需要舍弃栈中的数，否则将数组中的值压入栈中代码示例:#include<iostream> #include<stack> using namespace std; const int N = 2e5; int a[N], b[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; stack<int>q; for (int i = 1; i <= n; i++) { while (!q.empty() && q.top() >= a[i])q.pop(); if (q.empty())b[i] = -1; else b[i] = q.top(); q.push(a[i]); } for (int i = 1; i <= n; i++)cout << b[i] << " "; return 0; }使用stack是一种选择，但是更推荐使用数组模拟来实现单调栈，因为数组能进行更多操作，对于题目的适应与灵活度更高。但是因为数组空间固定要注意数组栈的溢出问题。下面给出数组实现的代码:#include<iostream> using namespace std; const int N = 2e5; int a[N], b[N], stk[N], top; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; for (int i = 1; i <= n; i++) { while (top && a[stk[top]] >= a[i])top--; if (top)b[i] = a[stk[top]]; else b[i] = -1; stk[++top] = i; } for (int i = 1; i <= n; i++)cout << b[i] << " "; return 0; }

(BFS) Breadth-First Search入门 广度优先搜索:BFS全称Breadth First Search.广度优先，优先在于广度，尽量的往周围扩散再前进。如果是DFS是一只迷宫里的蚂蚁，那么BFS就像倒在地上的一滩水.BFS的搜索是蔓延式的进行.观察下列，搜索是从(1,1)开始的 搜索的优先级为右下左上 每个数字代表是第几个被搜索到的1 2 4 7 113 5 8 12 166 9 13 17 2010 14 18 21 2315 19 22 24 25可以观察到我们的搜索是如水一般蔓延开来的，按照我们设置好的搜索规则依次判断.我们设置了一个边长为5X5的图,且初始点我们让其从(1,1)开始进行.过程的简单描述:从(1,1)开始,先判断右边是否走过,没走过将其标为2.然后再回到(1,1)接着判断下面是否走过，没走过将其标为3.然后判断左边，为边界无法走，接着判断上面，为边界无法走.(1,1)此时4个方位都判断完了，接着来到(1,1)这个点判断标记的第一个点———(1,2)然后从(1,2)开始刚刚的过程,最终形成了这个图.题目:快乐的马里奥 这是一个基础的bfs题,题解思路如我们上述相同. 用代码怎么实现呢？ 我们需要用到核心为 queue 和 pair 使用队列的特性---先进先出，记录最先标记了的坐标位置,下面给出AC代码#include<iostream> #include<queue> #include<vector> using namespace std; int fx[4]={0,1,0,-1}; int fy[4]={1,0,-1,0}; int main() { std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int m, n; cin >> m >> n;//输入行列 vector<vector <int> >v( m + 1,vector<int> ( n + 1, 0 ));//设置二维数组 queue<pair<int,int> >q;//队列用来记录坐标 q.push({1,1});//设置初始的坐标，也是开始的坐标 v[1][1] = 1;//对初始点赋初值 int cnt = 2;//因为初始点为1,第二个点从2开始 while(!q.empty()){//队列存储的坐标不为空就执行 //取出队列中存储的第一个坐标，用完就丢 int x = q.front().first; int y = q.front().second; q.pop(); //依次判断四个方位 for(int i = 0;i < 4;i++){ int nx = x + fx[i]; int ny = y + fy[i]; if(nx <= m && nx > 0 && ny <= n && ny > 0 && v[nx][ny] == 0){ v[nx][ny] = cnt++;//赋值标记 q.push({nx,ny});//将赋值点的坐标存入队列 } } } //打印输出 for(int i = 1; i <= m;i++){ for(int j = 1; j <= n;j++){ cout << v[i][j] << " "; } cout << '\n'; } return 0; }

(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"); } }

二分法 二分查找本质上是按照某一性质每次一分为二查找左右边界 普通的二分查找 题目 题目解释:在一组有序无重复数组中查找某一个数，如果能查找到输出这个数是第几个数，否则输出-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; }

递归模拟 题目描述 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; }