算法day7-bfs搜索1题-动归1题
算法day7 bfs搜索1题 动归1题
这里是记录作者的算法进程的，答案不是最优，但是是可以让每个人都可以理解，初学者都不可能一下写出最优的，所以还请见谅
一 青蛙跳杯子
青蛙跳杯子
题目描述
XX 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
XX 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
∗WWWBBB∗WWWBBB
其中，WW 字母表示白色青蛙，BB 表示黑色青蛙，∗∗ 表示空杯子。
XX 星的青蛙很有些癖好，它们只做 3 个动作之一：
- 跳到相邻的空杯子里。
- 隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。
- 隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要 1 步，就可跳成下图局面：
WWW∗BBBWWW∗BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入描述
输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。
输出描述
输出要求为一个整数，表示至少需要多少步的青蛙跳。
输入输出样例
示例
输入
*WWBB WWBB*输出
2运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
首先我们学习过广度优先，但是我们只写过走迷宫问题，我们就要进行思考，让这个青蛙怎么进行跳跃
我们先来思考一下走迷宫是怎么走的
1 如何跳跃
首先走迷宫不就是上下左右走嘛，那我们反观这个题目，我们的青蛙可以向左跳跃，或者向右跳跃，但是没有向上或者向下跳跃，但是这个向左和向右是不一样的，它可以跳跃不同的步长，那么我们可以用向量数组来进行处理，又或者不用向量数组，用for循环是不是也可以解决，所以我们这里择优选择，因为这个跳跃式二维，直接用for循环就好
2 状态的设置
我们回忆我们走迷宫的时候，是不是需要进行状态的设置，为什么？因为我们走过的点就不要再继续走了，所这里也一样，我们青蛙跳跃的状态如果走过了，那么我们就不需要再进行跳跃了，要不然就重复了，加大了时间的开销
3 如何进行广度搜索
首先我们进行广度搜索的最大的特点就是有一个队列，对吧，然后我们需要把这个所有的情况都找完，然后队列就是一进一出，这样就可以实现先找左边或者先找右边，那么我们后面就可以进行广度搜索了
栈的经典逻辑就是先把最初的元素放入，然后再把这个最初的拿出来，进行弹出，利用二元组进行每一个元素的取出就好了
代码展示
这个代码的通过率只有6个通过4个，有两个是运行超时了
#include <bits/stdc++.h> using namespace std; typedef pair<string, int> PSI; const int N = 10010; string visitedarray[N]; long visitedCount = 0; queue <PSI> q; bool visited(const string& state){ for(int i = 0; i <= visitedCount; i++){ if( state == visitedarray[i]){ return false; } } return true; } int bfs(string start,string end){ if( start == end ) return 0; q.push({start, 0}); visitedarray[visitedCount++] = start; while(!q.empty()){ auto t = q.front(); q.pop(); string nowstr = t.first; int steps = t.second; int marker = nowstr.find('*'); //向右跳 for(int i = 1; i <= 3; i++){ int wajump = marker + i; if(wajump < nowstr.length()){ string newstr = nowstr; swap(newstr[wajump],newstr[marker]); if(newstr == end) return steps + 1; if(visited(newstr)){ visitedarray[visitedCount++] = newstr; q.push({newstr,steps + 1}); } } } //向左跳 for(int i = 1; i <= 3; i++){ int wajump = marker - i; if(wajump >= 0){ string newstr = nowstr; swap(newstr[wajump],newstr[marker]); if(newstr == end) return steps + 1; if(visited(newstr)){ visitedarray[visitedCount++] = newstr; q.push({newstr,steps + 1}); } } } } return -1; } int main(){ string start; string end; cin >> start; cin >> end; int result = bfs(start, end); if(result != -1) cout << result << endl; return 0; }写算法题目前期注重对于自己知识的运用为主，等到后面思路多了，就可以进行代码的优化，没有一个人是可以再最初的时间点写出最优的代码出来
这个函数就是我们利用二元组记录步数和字符串，然后用一个数组记录下这个字符串是否出现过，然后我们分别有向左或者向右边跳跃
二 砍柴
问题描述
小蓝和小乔正在森林里砍柴，它们有 TT 根长度分别为 n1,n2,⋯,nTn1,n2,⋯,nT 的木头。对于每个初始长度为 nn 的木头，小蓝和小乔准备进行交替砍柴，小蓝先出手。
每次砍柴时，若当前木头长度为 xx，需要砍下一截长度为 pp 的木头，然后换另一个人继续砍，其中 2≤p≤x2≤p≤x 且 pp 必须为质数。当轮到某一方时 x=1x=1 或 x=0x=0，它就没法继续砍柴，它就输了。它们会使用最优策略进行砍柴。请对每根木头判断是小蓝赢还是小乔赢，如果小蓝赢请输出 11（数字 11），如果小乔赢请输出 00（数字 00）。
输入格式
输入的第一行包含一个正整数 TT ,
接下来 TT 行，每行包含一个正整数，其中第 ii 的整数为 nini 。
输出格式
输出 TT 行，每行包含一个整数，依次表示对于每一根木头的答案。
样例输入
3 1 2 6样例输出
0 1 1样例说明
对于 n1=1n1=1，由于当前长度 x=1x=1 ，小蓝直接输掉，小乔赢；
对于 n2=2n2=2，小蓝选择 p=2p=2，轮到小乔时当前长度 x=2−2=0x=2−2=0 ，小乔输掉，小蓝赢；
对于 n3=6n3=6，小蓝选择 p=5p=5，轮到小乔时 x=6−5=1x=6−5=1，小乔输掉，小蓝赢。
评测用例规模与约定
对于 20%20% 的评测用例，1≤ni≤1031≤ni≤103；
对于所有评测用例，1≤ni≤105,1≤T≤1041≤ni≤105,1≤T≤104。
运行限制
语言 最大运行时间 最大运行内存 C++ 1s 256M C 1s 256M Java 3s 512M Python3 10s 512M PyPy3 3s 512M Go 5s 512M JavaScript 5s 512M
这个题目是考动态规划，那么能动态必须可以用dfs和记忆化的呀，wok直接上暴力试试，暴力求解这个题目
dfs暴力求解
1 解题思路
首先我们看到这个题目，就是要考虑用搜索类型的，为什么呢？很明显用大的化为小的
这个dfs就是不断地尝试，然后看可不可以给这个人赢下来，如果可以赢下来就是这个人，因为你要假设一个人是尝试所有情况后，看可不可以得到最优地，如果得不到，那么就是这个人拼尽全力无法战胜，最终都是对方赢，所以每一句都是固定一个人赢下来的，所以我们用dfs来求解就是不断地尝试，看可不可以得到那个最优的解
#include <bits/stdc++.h> using namespace std; const int N = 100010; int n; int priarr[N]; int val[N]; int num; bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } int dfs(int x) { if (x == 1 || x == 0) return 0; for (int i = 0; i < num; i++) { if (priarr[i] > x) break; // 质数不能比 x 大 if (x - priarr[i] >= 0 && dfs(x - priarr[i]) == 0) { return 1; // 让对手进入必败状态 } } return 0; // 没有办法让对手输，当前玩家输 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &val[i]); } for (int i = 1; i <= n; i++) { num = 0; // 质数清空 for (int j = 2; j <= val[i]; j++) { if (IsPrime(j)) { priarr[num++] = j; } } // 计算当前木头长度的胜负情况 int result = dfs(val[i]); cout << result << endl; } return 0; }这个代码样例的运算结果正确，但是全部不过，因为时间复杂度太高了，可惜了，dfs果然还是不想，那么我们就考虑用记忆化试试，看看能不能过
记忆化搜索
#include <bits/stdc++.h> using namespace std; const int N = 100010; int n; int priarr[N]; int val[N]; int num; int dp[N]; bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } int dfs(int x) { if (x == 1 || x == 0) return 0; if ( dp[x] != -1) return dp[x]; for (int i = 0; i < num; i++) { if (priarr[i] > x) break; // 质数不能比 x 大 if (x - priarr[i] >= 0 && dfs(x - priarr[i]) == 0) { dp[x] = 1; // 让对手进入必败状态 return dp[x]; // 找到必胜策略，立即返回 } } return dp[x] = 0; // 没有办法让对手输，当前玩家输 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &val[i]); } for (int i = 1; i <= n; i++) { num = 0; // 质数清空 memset(dp, -1, sizeof(dp)); // 每次新木头清空记忆化数组 for (int j = 2; j <= val[i]; j++) { if (IsPrime(j)) { priarr[num++] = j; } } // 计算当前木头长度的胜负情况 int result = dfs(val[i]); int first = 0; if(first == 0){ cout << result << endl; } else{ cout << " " << result; } } return 0; }博主大大写了一个记忆化搜索的，但是还是只过了一半
好吧博主大大的动态规划也只过了一半
#include <bits/stdc++.h> using namespace std; const int N = 100010; int n; int priarr[N]; // 质数数组 int val[N]; // 木头长度 int num; // 质数个数 int dp[N]; // 动态规划数组 // 判断是否是质数 bool IsPrime(int n) { if (n <= 1) return false; for (int i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } int main() { // 读取输入 scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &val[i]); } // 处理每个测试用例 for (int i = 1; i <= n; i++) { num = 0; // 每次新木头清空质数数组 memset(dp, 0, sizeof(dp)); // 初始化dp数组，0代表必败，1代表必胜 // 收集所有小于或等于 val[i] 的质数 for (int j = 2; j <= val[i]; j++) { if (IsPrime(j)) { priarr[num++] = j; // 存储当前木头的所有质数 } } // 从 1 到 val[i] 更新动态规划表 for (int x = 1; x <= val[i]; x++) { for (int j = 0; j < num; j++) { if (priarr[j] > x) break; // 质数不能比 x 大 if (dp[x - priarr[j]] == 0) { // 如果 x - priarr[j] 是必败状态 dp[x] = 1; // 则当前状态是必胜状态 break; // 一旦找到必胜状态，立即跳出 } } } // 输出当前木头长度的胜负情况，每个结果单独输出一行 cout << dp[val[i]] << endl; } return 0; }
三 思路的总结
青蛙跳杯子
这个是bfs的升级版本，上面也又思路，那我们要总结可以收获到什么东西
1 移动
这个我们当遇到这种一维的跳跃的时候，就要考虑用for循环，因为我们一般我们都是考虑二维移动嘛，然后for里面就是我们跳跃的步数，也就是方向向量的大小
2 为什么又队列
bfs有一个很标志性的东西就是这个队列的使用，就是我们每次进行移动的时候，都要把这个状态放入栈里面，为什么？因为你是广度不是深度，深度十用递归递下去的，而广度不是，是要把你这个深度的节点全部都遍历完，才到下一个深度，当我们把这个深度遍历完的那段时间，要把下一个深度的节点放入到这个深度的节点的后面，当我们这个深度遍历完的时候就可以紧接着下一个深度的节点
3 状态的设置
首先我们要清除，走过的节点，我们不可以再走了，为什么不可以再走了，你想想，你走了之后，你遇到的情况不是跟之前相同的情况的走法嘛？这个不就是重复了嘛，为了减少时间的开消，所以就设置一个状态数组
砍柴
首先这个题目博主用了三个方法，我们分别来看看这三个方法，我们可以学习到什么？
dfs
首先我们之前学过的dfs就是选择或者不选择，还有就是用一个for循环进行多重地选择，这个就是把这个递归放入if语句了，这个其实跟01背包有点像
首先 我们输入一个数字n，然后利用这个数字n来进行输入每一个柴火地值
然后 我们就要为dfs做准备，就是质数地数组放入，然后我们就用一个for循环进行每一个柴火地遍历，然后再紧接着，把这个柴火质数地数组进行防止，注意放每一个质数地时候，这个质数地有效数字个数地大小要清零
最后 就是进入dfs进行求解了，首先0与1必是0，所以我们直接return，就好了，然后就是我们进入到这个for循环，然后逐步地判断这个可以不可以砍
条件一：当前质数的大小要小于柴火的长度
条件二：判断可不可以砍这个柴火，如果可以的话就尝试去砍这个尝试就交给dfs了，就算不行，也可以进行回溯进行下一个的判读
为什么要把dfs放入到条件里面，因为我们要判断每一次的情况有咩有这个让小蓝赢的，如果没有就是小乔赢
以上是dfs的思路
记忆化搜索
首先我们记忆化搜索就是再dfs的基础上进行记忆化用一个数组存着，也就是判断到这一步的时候，就直接进行返回这个数组里的元素，然后再进行下一步的判断，这个就是再dfs上面把这个return改为这个变量就好了，然后最后返回这个值就好了，十分的简单
以上是记忆化搜索的思路
动态规划
首先这个动态规划就是再dfs基础上少了递归的递的过程，直接进行归，然后我们只需要制作一个动态规划表就好了，行表示对应的这个柴火的长度，列表示的是砍多长，也就是质数
然后我们就先判断，这个质数是不可以比这个柴火要长的，如果长的话直接进行break
然后就是可以不可以砍的问题，如果这个时候是必胜的状态就直接进行砍，一刀切到大动脉，别把这个想成二维，因为我只是好解释说成二维而已
以上是动归的思路