预习 笔记 复习 做题
专注 效率 记忆

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
　
文章字体风格：
红色文字表示：重难点★✔
蓝色文字表示：思路以及想法★✔
　
如果大家觉得有帮助的话，感谢大家帮忙
点赞！收藏！转发！

双向bfs

原题链接

题意分析

就是把
字符串A 根据规则 变成字符串B

普通算法

把字符串的每一位 都遍历一遍 然后根据 变化规则 进行变化然后bfs

但是这样会非常复杂，

优化算法

如果 A开始 变化 并且 B 也开始变化

如果出现相同的字符串了

那么说明 A 可以根据 规则 变到B

代码块 内容

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>using namespace std;const int N = 6;int n;
string A, B;
string a[N], b[N];int extend(queue<string>& q, unordered_map<string, int>&da, unordered_map<string, int>& db, string a[N], string b[N])
{int d = da[q.front()];while (q.size() && da[q.front()] == d){auto t = q.front();q.pop();for (int i = 0; i < n; i ++ )for (int j = 0; j < t.size(); j ++ )if (t.substr(j, a[i].size()) == a[i]){string r = t.substr(0, j) + b[i] + t.substr(j + a[i].size());if (db.count(r)) return da[t] + db[r] + 1;if (da.count(r)) continue;da[r] = da[t] + 1;q.push(r);}}return 11;
}int bfs()
{
在bfs中
1. 把A，B入队列，并且分别放到 unordered_map中
2. A，B其中一个进行一层遍历，哪一层遍历呢？还是一起同步一
层遍历？ 没必要，因为需要对比 unordered_map 所以还是一
层遍历后，另一个再遍历，那么哪一层先遍历呢？为了减小时间复
杂度，先选队列中 元素少的进行 遍历比较好
3. 每遍历完一层，得到一个最小步数（可能进行了会师，也可能
没还会师，那么如果没会师那么继续，但是如果步数超过了10，那么
直接终止）
4.如何遍历一层？首先得到一层的元素个数，只遍历这么多，然后
根据每个元素进行 规则遍历，如果出现过unordered_map中，说明
会师了，直接返回int值，或者说明，之前出现过数据，不再更新
int，具体看出现在哪个unordered_map中if (A == B) return 0;queue<string> qa, qb;unordered_map<string, int> da, db;qa.push(A), qb.push(B);da[A] = db[B] = 0;int step = 0;while (qa.size() && qb.size()){int t;if (qa.size() < qb.size()) t = extend(qa, da, db, a, b);else t = extend(qb, db, da, b, a);if (t <= 10) return t;if ( ++ step == 10) return -1;}return -1;
}int main()
{cin >> A >> B;while (cin >> a[n] >> b[n]) n ++ ;int t = bfs();if (t == -1) puts("NO ANSWER!");else cout << t << endl;return 0;
}

双向dfs

送礼物

原题链接

1. 本题是背包问题，但是背包问题的时间复杂度是 N*V所以这道题，不能用背包去解
2. 那我们就用dfs暴搜，时间复杂度是2⁴⁶,也会超时。那么如何去解呢？我们可以dfs一半的数据 时间复杂度是 2²³，不会超时，然后呢，再dfs后一半的数据，与前面记录下来的数据进行比较
3. dfs前一半的数据，保留所有可能凑出来的重量，然后记录在数据中（需要排序并去重）
4. dfs后一半的数据，然后在 已知重量中 和 已经遍历出的后一半可能凑出的重量中，ans = max(ans,sum) 具体看代码就能明白
5. 总而言之就是 dfs前一半 然后 dfs后一半，就能把时间复杂度降低

#include<iostream>
#include<algorithm>using namespace std;const int N = 1 << 24;long long a[50];
long long n;long long state[N],k;
long long W;
long long ans = 0;
long long kk = 0;
void dfs1(long long u,long long n,long long sum)
{if(u-1==n){ans = max(ans,sum);state[k++] = sum;return;}if(sum+a[u]<=W){// state[k++] = sum+a[u];dfs1(u+1,n,sum+a[u]);}dfs1(u+1,n,sum);
}void dfs2(long long u,long long n,long long sum)
{if(u-1==n){int l = 0,r = kk-1;while(l<r){int mid = l + r + 1 >> 1;if(state[mid]+sum<=W)l = mid;else r = mid-1;}// cout << sum << ' ' << state[s] << endl;ans = max(ans,sum);if(state[l]+sum<=W){ans = max(ans,state[l]+sum);}return;}if(sum+a[u]<=W){// state[k++] = sum+a[u];dfs2(u+1,n,sum+a[u]);}dfs2(u+1,n,sum);
}int main()
{cin >> W >> n;for(int i = 1; i <= n; i++) cin >> a[i];dfs1(1,n/2,0);sort(state,state+k);for(int i = 0; i < k; i++){if(state[i]==state[i+1])continue;state[kk++] = state[i];}dfs2(n/2+1,n,0);cout << ans;}