无锡网站建设咨询,php仿百度网站源码,东莞做网站建设,丽水品牌网站设计蓝桥杯C大学B组一个月冲刺记录2024/3/18
规则:每日三题 昨天因为前妻姐emo上了,静下来思考了点东西,就没做题啦.今日补上! 另外:博客浏览量破万了,写的东西有人看还是很开心的 1.母亲的牛奶 农夫约翰有三个容量分别为 A,B,C升的挤奶桶。 最开始桶 A和桶 B都是空的#xff0c;…蓝桥杯C大学B组一个月冲刺记录2024/3/18
规则:每日三题 昨天因为前妻姐emo上了,静下来思考了点东西,就没做题啦.今日补上! 另外:博客浏览量破万了,写的东西有人看还是很开心的 1.母亲的牛奶 农夫约翰有三个容量分别为 A,B,C升的挤奶桶。 最开始桶 A和桶 B都是空的而桶 C里装满了牛奶。 有时约翰会将牛奶从一个桶倒到另一个桶中直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。 这一过程中间不能有任何停顿并且不会有任何牛奶的浪费。 请你编写一个程序判断当 A桶是空的时候C桶中可能包含多少升牛奶找出所有的可能情况。 bfs 状态转移 主要思想: (1)是如何记录被遍历的状态,任何字符串(或是多数据)的状态,都可以通过各元素元素编码得到一个longlong值.然后通过哈希进行记录 (2)状态转移:穷举即可
#includeiostream
#includecstring
#includequeue
#includevector
#includealgorithmusing namespace std;const int N 25;int A,B,C;struct state{int a,b,c;
};bool st[N * N * N];vectorintans;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;queuestateq;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,求最短路
#includeiostream
#includequeue
#includecstdiousing namespace std;const int M 105;typedef pairint,intPII;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;queuePIIq;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
#includeiostream
#includequeue
#includecstringusing 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;queuestringq;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 简单的染色法前后计算岛屿的个数,然后做差值是错误的. 原因:可能存在岛屿被水淹没后,形成了两个岛屿,让岛屿的数量增加. 主要思想: 在染色过程中,计算在该岛屿是否存在土地四周没有海洋,即该土地不会被水淹没,即该岛屿不会被淹没.
#includeiostream
#includequeueusing namespace std;typedef pairint,intPII;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 ;queuePIIq;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] 的对应关系,我第一次交这里就错了
#includeiostream
#includequeue
#includecstringusing 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;queuestringq;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)排除等效冗余:如果第一次尝试拼入木棍就失败的话,那么这个分治必然也是失败的,因为在拼入这些木棍前,面对的原始木棍都是还没有拼接的,他们都是等效的.
#includecstdio
#includealgorithm
#includecstring
#includeiostreamusing 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;}
