蓝桥杯C++大学B组一个月冲刺记录2024/3/18
规则:每日三题
昨天因为前妻姐emo上了,静下来思考了点东西,就没做题啦.今日补上!
另外:博客浏览量破万了,写的东西有人看还是很开心的
1.母亲的牛奶
农夫约翰有三个容量分别为 A,B,C升的挤奶桶。
最开始桶 A和桶 B都是空的，而桶 C里装满了牛奶。
有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。
请你编写一个程序判断，当 A桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。
bfs + 状态转移
主要思想:
(1)是如何记录被遍历的状态,任何字符串(或是多数据)的状态,都可以通过各元素元素编码得到一个longlong值.然后通过哈希进行记录
(2)状态转移:穷举即可
#include#include#include#include#includeusing namespace std;const int N = 25;int A,B,C;struct state{int a,b,c;};bool st[N * N * N];vector<int>ans;int query_k(int a, int b, int c){return a * 21 * 21 + b * 21 + c;}void bfs(int a,int b,int c){int k = query_k(a,b,c);st[k] = true;queue<state>q;q.push({a,b,c});while(q.size() != 0){auto t = q.front();q.pop(); if(t.a == 0) ans.push_back(t.c); if(t.a != 0){state New;New.a = t.a - min(t.a,B - t.b);New.b = t.b + min(t.a,B - t.b);New.c = t.c;k = query_k(New.a,New.b,New.c);if(!st[k]) q.push(New),st[k] = true;New.a = t.a - min(t.a,C - t.c);New.b = t.b;New.c = t.c + min(t.a,C - t.c);;k = query_k(New.a,New.b,New.c);if(!st[k]) q.push(New),st[k] = true;}if(t.b != 0){state New;New.a = t.a + min(t.b,A - t.a);New.b = t.b - min(t.b,A - t.a);New.c = t.c;k = query_k(New.a,New.b,New.c);if(!st[k]) q.push(New),st[k] = true;New.a = t.a;New.b = t.b - min(t.b,C - t.c);New.c = t.c + min(t.b,C - t.c);;k = query_k(t.a,t.b,t.c);if(!st[k]) q.push(New),st[k] = true;}if(t.c != 0){state New;New.a = t.a + min(t.c,A - t.a);New.b = t.b;New.c = t.c - min(t.c,A - t.a);k = query_k(New.a,New.b,New.c);if(!st[k]) q.push(New),st[k] = true;New.a = t.a;New.b = t.b + min(t.c,B - t.b);New.c = t.c - min(t.c,B - t.b);;k = query_k(New.a,New.b,New.c);if(!st[k]) q.push(New),st[k] = true;}}return;}int main(){cin >> A >> B >> C;bfs(0,0,C);sort(ans.begin(),ans.end());for(int i = 0;i < ans.size();++i) cout << ans[i] << ' ';return 0;}2.走迷宫
给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0
或 1，其中 0表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。
数据保证 (1,1)处和 (n,m)处的数字为 0，且一定至少存在一条通路。
bfs
简单的bfs,求最短路
#include#include#includeusing namespace std;const int M = 105;typedef pair<int,int>PII;int p[M][M];int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};bool st[M][M];int dist[M][M];int m,n;void bfs(int x,int y){st[x][y] = true;queue<PII>q;q.push({x,y});while(q.size() != 0){auto t = q.front();q.pop();if(t.first == m && t.second == n) break;for(int i = 0;i < 4; ++i){ int xx = t.first + dx[i];int yy = t.second + dy[i];if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && p[xx][yy] == 0 && !st[xx][yy]){st[xx][yy] = true;dist[xx][yy] = dist[t.first][t.second] + 1;q.push({xx,yy});}}}return;}int main(){cin >> m >> n;for(int i = 1;i <= m;++i){for(int j = 1;j <= n;++j){cin >> p[i][j];}}bfs(1,1);cout << dist[m][n] << endl;return 0;}3.八数码(1)
经典的华容道问题:不贴了.
求的是到达最终形态的最小操作数
bfs + 状态转移
更经典的状态记录:各元素加权求和然后哈希
这个哈希可以直接使用unorder_map数据结构来做.
但是为了锻炼手写哈希散列表的能力:我选择手写
(手写哈希的耗时只有unorder_map的三分之一,unorder_map的底层是红黑树)
手写哈希耗时1608ms
unorder_map耗时:2312ms
#include#include#includeusing namespace std;const int N = 1e6 + 3;typedef long long LL;LL h[N];int dist[N];int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};LL query_k(string s){LL t = 0;for(int i = 0;i < s.size(); ++i) t = t * 10 + s[i] - '0';return t;}int find(string s){LL t = query_k(s);int k = (t % N + N) % N;while(h[k] != -1 && h[k] != t){k++;if(k >= N) k = 0;}return k;}int bfs(string first){string end = "123456789";queue<string>q;q.push(first);h[find(first)] = query_k(first); while(q.size() != 0){int old_k,new_k;auto t = q.front();q.pop();old_k = find(t);if(t == end) return dist[old_k];int id = t.find('9');int x = id / 3,y = id % 3; for(int i = 0; i < 4; ++i){int xx = x + dx[i];int yy = y + dy[i];if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3){swap(t[xx * 3 + yy],t[id]);new_k = find(t);if(h[new_k] == -1){q.push(t);h[new_k] = query_k(t);dist[new_k] = dist[old_k] + 1;}swap(t[xx * 3 + yy],t[id]);}}}return -1;}int main(){memset(h,-1,sizeof(h));string first;for(int i = 1;i <= 9;++i){char c;cin >> c;if(c == 'x') first += '9';else first += c;}cout << bfs(first) << endl;return 0;}4.全球变暖
你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
…
.##…
.##…
…##.
…####.
…###.
…
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…
…
…
…
…#…
…
…
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
染色法+bfs
简单的染色法前后计算岛屿的个数,然后做差值是错误的. 原因:可能存在岛屿被水淹没后,形成了两个岛屿,让岛屿的数量增加.
主要思想: 在染色过程中,计算在该岛屿是否存在土地四周没有海洋,即该土地不会被水淹没,即该岛屿不会被淹没.
#include#includeusing namespace std;typedef pair<int,int>PII;const int M = 1005;char p[M][M];bool st[M][M];bool f[M * M];int dx[4] = {1, 0, -1, 0};int dy[4] = {0, 1, 0, -1};int n,cnt;void bfs(int i,int j){st[i][j] = true;cnt ++;queue<PII>q;q.push({i,j});while(q.size() != 0){auto t = q.front();q.pop();bool flag = false;for(int k = 0;k < 4; ++k){int xx = t.first + dx[k];int yy = t.second + dy[k];if(xx >= 0 && xx < n&& yy >= 0&& yy < n){if(p[xx][yy] == '#' && !st[xx][yy]){st[xx][yy] = true;q.push({xx,yy});}if(p[xx][yy] == '.') flag = true;}}if(!flag) f[cnt] = true;}return;}int main(){cin >> n;for(int i = 0;i < n;++i) cin >> p[i];for(int i = 0;i < n; ++i){for(int j = 0;j < n; ++j){if(p[i][j] == '#' && !st[i][j]) bfs(i,j);}}int ans = 0;for(int i = 1;i <= cnt;++i){if(!f[i]) ans ++;}cout << ans << endl;}5.八数码(2)
和上面那道八数码一样,不过是求到达最终态的方案
bfs + 状态转移
y总的代码耗时106ms
我图方便,在上一道八数码的代码修改了下,耗时3601ms
后面得拜读一下别人的代码
主要思想:想清楚:dx[i] , dy[i] 和 pos[i] 的对应关系,我第一次交这里就错了
#include#include#includeusing namespace std;const int N = 1e6 + 3;typedef long long LL;LL h[N];string ans[N];int dx[4] = {1, 0, -1, 0},dy[4] = {0, -1, 0, 1};char op[4] = {'d', 'l', 'u', 'r'};LL query_k(string s){LL t = 0;for(int i = 0;i < s.size(); ++i) t = t * 10 + s[i] - '0';return t;}int find(string s){LL t = query_k(s);int k = (t % N + N) % N;while(h[k] != -1 && h[k] != t){k++;if(k >= N) k = 0;}return k;}bool bfs(string first){string end = "123456789";queue<string>q;q.push(first);h[find(first)] = query_k(first); while(q.size() != 0){int old_k,new_k;auto t = q.front();q.pop();old_k = find(t);if(t == end){cout << ans[old_k];return true;}int id = t.find('9');int x = id / 3,y = id % 3; for(int i = 0; i < 4; ++i){int xx = x + dx[i];int yy = y + dy[i];if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3){swap(t[xx * 3 + yy],t[id]);new_k = find(t);if(h[new_k] == -1){q.push(t);h[new_k] = query_k(t);ans[new_k] = ans[old_k] + op[i];}swap(t[xx * 3 + yy],t[id]);}}}return false;}int main(){memset(h,-1,sizeof(h));string first;for(int i = 1;i <= 9;++i){char c;cin >> c;if(c == 'x') first += '9';else first += c;}if(!bfs(first)) cout << "unsolvable" << endl;return 0;}6.木棍
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
dfs + 剪枝
剪枝方案:
(1)优化搜索序列:优先选择较长的木棍,这样后面穷举的木棍数量就会变少
(2)排除等效冗余:要求先后加入的木棍有单调性,因为先来一根长度为x的木棍,再来一个长度为y的木棍,其实他们反过来是一样的,既然如此当然要有单调性.(在凑len长木棍时让编号从小到大放置,避免重复判断)
(3)排除等效冗余:对于当前木棍,记录最近一次尝试拼接失败的木棍,因为它失败了,那么肯定之后不能尝试再次凭借和他长度一模一样的木棍.因为他们是一模一样,没有任何差别,那么A死了,后面的A自然也得死,虽然他们下标不一样.
(4)排除等效冗余:如果第一次尝试拼入木棍就失败的话,那么这个分治必然也是失败的,因为在拼入这些木棍前,面对的原始木棍都是还没有拼接的,他们都是等效的.
#include#include#include#includeusing namespace std;const int N = 100;int p[N];bool st[N];int n;int sum,len;bool cmp(int a,int b){return a > b;}bool dfs(int pos,int cur,int start){if(pos * len == sum) return true;if(cur == len) return dfs(pos + 1, 0, 1);for(int i = start;i <= n; ++i){if(st[i]) continue;if(cur + p[i] <= len){st[i] = true;if(dfs(pos,cur + p[i],i + 1)) return true;st[i] = false;} if(!cur||cur + p[i] == len) return false;int j = i + 1;while(p[i] == p[j] && j <= n) j++;i = j - 1;}return false;}int main(){while(cin >> n,n){sum = 0,len = 0;for(int i = 1; i <= n; ++i){cin >> p[i];sum += p[i];len = max(p[i],len); }sort(p + 1,p + n + 1,cmp);memset(st,0,sizeof(st));while(true){if(sum % len == 0 && dfs(0,0,1)){cout << len << endl;break;}len ++;}}return 0;}