1,首先,在入学测试中的那道题小贝的影分身中我明白了在一些dfs/bfs中不一定要以题目中给定的起点为起点,他可能要从终点往起点遍历;
2,记忆化搜索是一种剪枝,它可以优化时间复杂度,让便利下去没有意义的事务停止遍历
3,一些题目需要对数组实施预处理;
比如在记忆化搜索中:用dp数组既可以标记这个点有没有走过,也可以记录他的步数,这个时候就要最开始的时候将dp数组赋值为-1。
4,锻炼身体的路径告诉我又是要想存下一个字符矩阵,可以用map(因为我以前最讨厌用set和map);
5,小木棍是一个剪枝很多的提,但是在一个bfs或dfs的剪枝中,并不是所有都需要想出所有的剪枝才能AC,比如在此题中有9种不同程度上优化的方法,而我只使用了6种便通过了这道题。
6,在bfs判断中尽量不要用冗长的一行全部判断完;
例如:
不要用:
nxt.x>=1&&nxt.x<=n&&nxt.y>=1&&nxt.y<=m&&nxt.bx>=1&&nxt.bx<=n&&nxt.by>=1&&nxt.by<=m&&vis[nxt.x][nxt.y][nxt.bx][nxt.by]==0&&a[nxt.x][nxt.y]!=1&&a[nxt.bx][nxt.by]!=1❌
建议用:
if(nx<1||ny<1||nx>n||ny>m){
continue;
}
if(a[nx][ny]>=a[x][y]){
continue;
}✔
下场:我改了半个上午;
7,标记数组不一定只有两维
例如:
推箱子:需要写的是搬运工的横坐标和纵坐标以及箱子的横坐标和纵坐标
大学生活:前两维表示横坐标和纵坐标,第三维表示朝向
8,bfs用于最短路径,时间复杂度较小,每个点只会被遍历一次;
dfs是一种递归,时间复杂度较大。
(我比较喜欢bfs,但不太喜欢dfs);
9,我学到了一个比较好玩的算法叫做:状态压缩(我喜欢它巧劲,但不喜欢他的代码);
它可以将一个需要开很多维的东西用一个二进制压成一维,便于储存
关于其的一些技巧:
(1,数字s二进制下第i位是否维1
(s&1<<i)>0
(s>>i&1)>0
(2,数字s二进制下将第i位变为1
s|=1<<i
(3,数字s二进制下将第i位翻转
s^=1<<i
(4,判断二进制表示下s中是否含t
(s&t)==t
10,一定要将自己的变量定义好一点。
比如我:胡求定义变量,结果因为变量定义比较复杂,把一个x写成了y,结果调了1个小时
11,数组在可以的情况下多定义一些,否则有时答案会错误(最主要是它不会报RE,而是WA,就是因为它导致了我大学生活一直WA80,调了好久。