周总结博客

周总结博客

这周主要看的是深搜内容，如何用递归实现深搜操作。在初级深搜中一般是处理寻找最短路径问题，这也是我这周主要看博客的重点。大约看了60多篇博客，对搜索类的题目进行了大量的练习。以下是本周看的题目及思考过程

样例输入1：         
4
1 2 4 7
13
样例输出2：
Yes

样例输入2：
4
1 2 4 7
15
样例输出：
No

对于这个题的思路是深搜中一个数是否被选中的情况.并且涉及选中后总和的变化,故采用bool类型的dfs来判断是否选入某数,分为选入何不选入的情况

#include <bits/stdc++.h>
using namespace std;
#define max_N 100000005
int a[max_N];
int n, k;
bool dfs (int i, int sum);
int main () {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}cin >> k;if (dfs(0,0)) {cout << "Yes";} else {cout << "No";}return 0;
}{//循环退出的条件，当i==n时，只需要判断sum是否与k相等即可 if (i == n) {return sum == k;}//a[i]被选 if (dfs(i + 1, sum + a[i])) {return true;}//a[i]不被选 if (dfs(i + 1, sum)) {return true;}//不管选不选用a[i]，都凑不成k，则返回false return false; 
}

int dx = { 0,0,1,-1 };
int dy = { 1,-1,0,0, };//从左上角开始移动
int ans=1000;//确保判断时会取较小的步数step
void dfs(int x, int y, int now_sum, int step)
{if(now_sum=sum)ans=min(ans,step)if (now_sum > =sum)return;for(int i=0;i<4;i++){int now_x = x + dx[i];int now_y = y + dy[i];if (now_x >= 1 && now_x <= n && now_y >= 1 && now_y <= m && !vis[now_x][now_y]){vis[now_x][now_y] = 1;//建立一个标志标识已经访问过dfs(now_x, now_y, now_sum + a[now_x][now_y], step + 1);vis[now_x][now_y] = 0;//回溯}}
}

         选数[NOIP2002 普及组] 选数 - 洛谷

通过选数可以发现在选择时,必须考虑到重复,所以一般运用回溯处理,或者利用via判断.

#include<bits/stdc++.h>
using namespace std;
int n,k,sum=0,ans=0,p=0;
int a[30];
bool prime(int x) {int i;for (i = 2; i <= floor(sqrt(x)); i++) {if (x%i == 0) {return false;}}return true;
}
void bfs(int x)
{ if(p==k&&prime(sum)){ans++;return;}//判断是否满足条件for(int i=x;i<=n;i++){p++;sum+=a[i];bfs(i+1);sum-=a[i];//回溯过程p--;}}int main()
{ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++)
{cin>>a[i];}bfs(1);
cout<<ans;
return 0;
}

 大多数选数问题需要考虑回溯,还有些问题在进行时需要判断是否越界,如马的遍历问题,有时还需要进行插入标识,来标记这个数使用过.

对于深搜问题本周还是做的太少,八皇后和健康的荷斯坦奶牛这类复杂问题也只是看了一下题解并没有成功的ac,这周相对来说博客看的多了,但是对于学到的深搜知识运用还是较少,下周争取最大量的进行例题的训练,使自己可以更好地掌握所学知识,尽可能地ac.