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

前缀和与差分 前缀和公式为 num[i] = num[i - 1] + a[i]差分公式为 diff[i] = a[i] - a[i - 1]前缀和与差分是能互相转换的前缀和数组进行一次差分可得原数组差分数组进行前缀和可得原数组原数组 ---前缀和---> 前缀和数组前缀和数组 ---差分---> 原数组原数组 ---差分---> 差分数组差分数组---前缀和---> 原数组前缀和数组 原数组 差分数组一维前缀和 题目描述 给定义一个数组𝑎，有𝑞+1次询问，对于每次询问：给定两个整数𝑙,𝑟，求出𝑎𝑙 + 𝑎𝑙+1 + ... + 𝑎𝑟的结果。输入描述 第一行一个整数表示样例个数T(1≤T≤10)。对于每组样例：第一行2个整数n(1≤n≤10^5),q(1≤q≤10^5)，分别表示数组长度和询问次数。第二行n个整数，表示数组a(−10^9≤ai≤10^9)。接下来q行，每行两个整数r(1≤l≤r≤n)表示询问的区间。输出描述 对于每组样例，一行一个整数表示答案。输入样例1 25 31 2 3 4 51 22 53 47 2-1 9 -10 8 2 6 111 52 7 输出样例1 3147826题解 根据输入的数组，建立一个每次相加前一位的数组如输入的为1 2 3 4 5根据前缀进行和1，1+2=3，3+3=6，6+4=10，10+5=15建立的数组为1 3 6 10 15对于查询的区间（l,r）只需进行算出：r位减去（l-1）位之间的值即可如查询（2,5）之间的和，15-1即是（2,5）区间的和代码样例#include<iostream> #include<vector> using namespace std; using ll = long long; void vol() { ll m, n; cin >> m >> n; vector<ll>ve(m + 1 , 0); for (ll i = 1; i <= m; i++) { cin >> ve[i]; } vector<ll>cop(m + 1, 0); for (ll i = 1; i <= m; i++) { cop[i] = cop[i - 1] + ve[i]; } ll l, r; for (ll i = 1; i <= n; i++) { cin >> l >> r; cout << cop[r] - cop[l - 1] << '\n'; } } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll t; cin >> t; while (t--) { vol(); } return 0; }一维差分 题目描述 给定一个长度为n的数组a，和两个整数p,q。先进行p次区间加操作：将区间[l,r]的数字都加上x。再进行q次区间查询操作：求出[l,r]的数字之和。对于每次区间查询操作，输出结果。 输入描述 第一行三个整数n,p,q。(1≤n≤10^5 ,0≤p≤10^5 ,0≤10^5 ≤q)第二行n个整数表示数组a。(−10^9 ≤ai ≤10^9 )接下来p行，每行三个整数l,r,x。(1≤l≤r≤n,−10^9 ≤x≤10^9 )接下来q行，每行两个整数(1≤l≤r≤n)输出描述 对于每次区间查询操作，输出结果。输入样例1 5 1 21 1 1 2 21 4 21 31 5 输出样例1 915题解 根据输入的数组建立一个差分数组如输入1,2,3,4,51-0=1，2-1=1，3-2=1，4-3=1，5-4=1因此建立的差分数组为1,1,1,1,1代码实例#include<iostream> using namespace std; const int N = 1e5+9; using ll = long long; ll a[N], diff[N], num[N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n , p , q ; cin >> n >> p >> q ; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) diff[i] = a[i] - a[i - 1]; while (p--) { ll l, r, x; cin >> l >> r >> x; diff[l] += x; diff[r + 1] -= x; } for (int i = 1; i <= n; i++) a[i] = diff[i] + a[i - 1]; for (int i = 1; i <= n; i++) num[i] = num[i - 1] + a[i]; while (q--) { ll l, r; cin >> l >> r; cout << num[r] - num[l - 1] << '\n'; } return 0; }二维前缀和 二维数组基本原理与一维前缀和几乎相同 注意重叠部分即可题目描述 给定一个n行m列的整数矩阵。 q个询问，每个询问格式为：x1,y1,x2,y2，表示一个子矩阵的左上角和右下角的坐标。对于每个询问，请回答子矩阵的所有数之和。输入格式 第一行包括三个整数n,m,q（1≤n,m≤10^3 ，1≤𝑞≤10^5,1≤q≤10^5 ）。接下来n行，每行包括m个整数，表示整数矩阵（每个整数的取值范围为[1,10^5 ]）。接下来q行，每行包括四个整数x1,y1,x2,y2(1<=x1<=x2<=n,1<=y1<=y2<=m)，表示一个询问的左上角、右下角坐标。输出格式 共q行，第i（1≤i≤q）行输出第i个询问的结果。样例输入1 7 3 23 5 1 6 2 4 7 9 10 4 3 6 3 9 9 6 10 1 9 10 4 2 2 7 32 1 4 2 样例输出1 7731代码实例#include<iostream> #include<vector> using namespace std; using ll = long long; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); ll n, m, q; cin >> n >> m >> q; vector<vector<ll> >a(n + 1, vector < ll >(m + 1, 0)); ll i, j; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { cin >> a[i][j]; } } vector<vector<ll> >b(n + 1, vector < ll >(m + 1, 0)); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { b[i][j] = b[i - 1][j] + b[i][j - 1] + a[i][j] - b[i - 1][j - 1]; } } while (q--) { ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1] << '\n'; } return 0; }二维差分 题目描述给定一个n行m列的整数矩阵。有q个操作，每个操作格式为：x1,y1,x2,y2,c，其中(𝑥1,𝑦1)、(x2,y2)分别表示一个子矩阵的左上角和右下角的坐标，每个操作将对应的子矩阵的每个元素加上c。请输出进行完所有操作后的矩阵。输入描述第一行包括三个整数n,m,q（1≤n,m≤10^3 ,1≤q≤10^5 ）。输出描述共n行，每行包括m个整数，表示进行完所有操作后的矩阵。输入样例14 3 31 5 1 3 3 2 5 3 4 4 4 2 1 2 1 2 22 1 2 3 24 2 4 3 1输出样例11 7 1 5 5 4 5 3 4 4 5 3 代码示例//二维差分 #include<iostream> using namespace std; using ll = long long; const int N = 1e3 + 9; ll a[N][N], diff[N][N]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m, q; cin >> n >> m >> q; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } //差分 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { diff[i][j] += a[i][j]; diff[i + 1][j] -= a[i][j]; diff[i][j + 1] -= a[i][j]; diff[i + 1][j + 1] += a[i][j]; } } //修改 while (q--) { int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c; diff[x1][y1] += c; diff[x2 + 1][y2 + 1] += c; diff[x2 + 1][y1] -= c; diff[x1][y2 + 1] -= c; } //求原数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i][j]; cout << a[i][j] << " "; } cout << '\n'; } return 0; }