算法之前： ！！！先读题： 通过关键词确定数据结构和算法 决定出复杂度 进行推导，找特殊性质 推一遍样例 复杂度： 时间复杂度 空间复杂度 使用 O() 表示，里面表示最坏要枚举多少遍，计算机最多1秒可以运行1*10^8 1个int占4个字节，1个字节占8位，可以表示2^8个二进制数，所以1个int可以表示-2^31到2^31-1. 1个long long占8个字节 递归算法： 要求解p,但是p解可以由p - 1推出，p - 1 可以由p - 2推出。。。 ！！注意：要先写停止的返回值，不然会陷入无限循环
枚举算法： 在每一道题目都可以使用的算法，思路很简单，把每一种情况全部枚举一遍，找出最优解 前提：！！一定要先弄清楚自己要枚举什么，每一个for都在干什么（通过写注释） 关键词：。。。好像不需要
模拟算法：(!!!P5731蛇形方阵) 这类题目一般题面很长，不需要动太多的脑子 ！！它终归还是大模拟，不要把中心放在特殊性质上 需要思考的是涉及到的数据结构，合理判断数据结构与有层次的枚举是解这类题目的关键 一定要搞清楚每个for在干什么，必要时写注释
在一个区间内循环的题目：(B4246,P1563) now %= n; if(now < 区间) now += n; 什么意思呢，就是总长度对于总区间取模，再加上取的模数，这一步一般放到最后来写
辨析：多维数组与结构体 若需要以较多的已知条件推得答案，使用多维数组 若已知条件较少，但之中有联系，则使用结构体
贪心算法：(P1223) 关键词：最大值，最小值 核心：贪什么，为什么贪（保证贪心为最优解） 贪心的证明： 要证:若p,则q 反证法： 若 否q，则否p;
双指针： 主要是优化遍历的方法，但要确保其是有序的
二分算法： ！！！！前提：该数组是有序的，且为单调非递减（递增但有重复） 本质就是双指针：l, r, !!mid = (l + r) / 2 二分查找： STL:upper_bound与lower_bound lower_bound找的是第一个>=要找的数的位置 upper_bound找的是第一个>要找的数的位置 int p = upper_bound(数组的开始地址, 数组的结束地址, 要找的变量名); int p = lower_bound(数组的开始地址, 数组的结束地址, 要找的变量名); int p = upper_bound(数组的开始地址, 数组的结束地址, 要找的变量名) - 数组的开始地址; int p = lower_bound(数组的开始地址, 数组的结束地址, 要找的变量名) - 数组的开始地址;
!!注意：两者返回的都为地址，若需要返回下标，需要在后面减去数组的第一个地址（数组名）
思路：每次将查找区间缩小一半，通过不断折半快速定位目标值。使时间复杂度由O(N) 减少至 O(log N)
具体实现步骤：(要找x,左指针l,右指针r)
if(a[mid] == x) {//若找到答案，则减少右指针，找更优解
ans = mid;
r = mid - 1;
}
if(a[mid] < x)
l = mid + 1;
if(a[mid] > x)
r = mid - 1;
二分答案：
使用二分的方法枚举在边界L,R之间每一个数，在用check函数判断是否合法，若合法，R-=mid-1或L+=mid+1 看取最大值还是最小值
桶： 相当于cnt数组，用于批量计数
一维前缀和：P6180 食用范围： 要计算一个区间内的和，但是暴力枚举O(N^2)过不了 方法：先算出第一位到第i位的和，如果要求区间 l到r 则：ans = b[r] - b[l - 1]
二维前缀和：P2004 思路：大减小补重复 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 求(1,2)左上角 到 (3,3)右下角 b(3,3) - b(3, 2) - b(2,3) 算答案从(x1, y1)到(x2, y2)公式:ans = b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1]; 求前缀和数组:b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j]
差分：P2367 d数组是a数组的前缀和 d[i] = a[i] - a[i - 1]; 当你要在原数组 l到r 上 +v d[l] = a[l] - v, d[r + 1] = a[r + 1] - v 最后还原数组a
dfs: 这是一个递归的操作，用于遍历离散的数据，如图，树 板子： void dfs(int i) { if(到达最后的叶子节点) 更新答案 bool 节点已经到达 for(u,v相邻的节点且不为v的) dfs(u); } 子集类 排列类 元组类 : k^n 原理就是再最开始的dfs(0)时，有n种可能，在 n 种可能里的每一种都有 n 种可能，这样有k^n的复杂度
bfs: P1443 使用了队列的数据结构 广搜在无权图中一定保证最短路径（层数） 例题：B3526 首先输入的是一个图，需要使用vis[n][m]来记a[i][j]这个点是否到达，使用了一个struct结构体来放在队列里面，记队首的(x,y)
代码：
include
define int long long
using namespace std;
int n,m;
char a[105][105];//a[i][j]的输入内容
struct POINT{
int x,y;
};
queue
signed main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; POINT first; first.x=1; first.y=1; q.push(first);//把(1,1)放到队尾 while(!q.empty()){//若为空，则代表上下左右都没有符合题目的点，这时停止 POINT now=q.front(); q.pop();//！！这个一定要出队，否则队列永远无法空 int x=now.x,y=now.y;//存一下x,y if(y+1<=m&&vis[x][y+1]==false&&a[x][y+1]=='.'){//右边是否符合3个条件：没有出界，这个点没有被访问过，这个点可以走 POINT tmp; tmp.x=x,tmp.y=y+1; q.push(tmp); vis[x][y+1]=true;//！！一定要标记一下，否则上面的没访问的条件一直可以达到，永远无法停止循环 } if(y-1>=1&&vis[x][y-1]==false&&a[x][y-1]=='.'){//左边 POINT tmp; tmp.x=x,tmp.y=y-1; q.push(tmp); vis[x][y-1]=true; } if(x+1<=n&&vis[x+1][y]==false&&a[x+1][y]=='.'){//下边 POINT tmp; tmp.x=x+1,tmp.y=y; q.push(tmp); vis[x+1][y]=true; } if(x-1>=1&&vis[x-1][y]==false&&a[x-1][y]=='.'){//上面 POINT tmp; tmp.x=x-1,tmp.y=y; q.push(tmp); vis[x-1][y]=true; } } cout<<(vis[n][m]==true?"Yes":"No")<<'\n';//若vis[n][m]没有被搜索过，就是false输出"no"否则输出"Yes" return 0; }