当前位置： 首页 > article >正文

蓝桥杯C++大学B组一个月冲刺记录2024/3/18

article 2025/1/11 0:53:21

蓝桥杯C++大学B组一个月冲刺记录2024/3/18

规则:每日三题

昨天因为前妻姐emo上了,静下来思考了点东西,就没做题啦.今日补上!
另外:博客浏览量破万了,写的东西有人看还是很开心的

1.母亲的牛奶

农夫约翰有三个容量分别为 A,B,C升的挤奶桶。
最开始桶 A和桶 B都是空的，而桶 C里装满了牛奶。
有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。
这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。
请你编写一个程序判断，当 A桶是空的时候，C桶中可能包含多少升牛奶，找出所有的可能情况。

bfs + 状态转移
主要思想:
(1)是如何记录被遍历的状态,任何字符串(或是多数据)的状态,都可以通过各元素元素编码得到一个longlong值.然后通过哈希进行记录
(2)状态转移:穷举即可

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>

using 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<iostream>
#include<queue>
#include<cstdio>

using 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<iostream>
#include<queue>
#include<cstring>

using 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<iostream>
#include<queue>

using 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<iostream>
#include<queue>
#include<cstring>

using 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<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using 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;

}

http://www.kler.cn/a/273836.html

相关文章：

  • Effective C++读书笔记——item13（使用对象管理资源）
  • P10424 [蓝桥杯 2024 省 B] 好数
  • kubernetes第五天
  • 代码随想录day38 动态规划6
  • 外驱功率管电流型PWM控制芯片CRE6281B1
  • 121 买入股票的最佳时机
  • 【DL经典回顾】激活函数大汇总（二十一）（BReLU附代码和详细公式）
  • 身份证文字识别ocr免费-身份证实名认证接口-护照识别-Java调用代码
  • 【ADF4351】使用FPGA进行SPI寄存器配置、使用FPGA计算各个频率的频点，ADF4351配置程序
  • Games101课程笔记1--图形学简介
  • SpringBoot 集成RabbitMQ，简单示例（附源码）
  • 渔业安全生产综合管理指挥系统-航迹数据优化方案
  • XML语言的学习记录3-解析
  • MybatisPlus逆向工程
  • C#类型转换
  • 文件批量管理利器，一键复制备份安全删除原文件，让文件管理更高效！
  • 华岳M9制造企业管理软件业务流程 1/4
  • spring boot 运行mongodb sql
  • 使用 C 或 C++ 扩展 Python
  • 【WEEK3】学习目标及总结【SpringMVC】【中文版】
  • 二维数组_计算矩阵边缘元素之和
  • 「Linux系列」聊聊vi/vim的3种命令模式
  • 聚合音乐网-播放器网站源码
  • 简单来说依赖注入 Unity (c#)
  • 代码随想录算法训练营第14天 part01 | 二叉树理论基础篇
  • JeecgBoot 3.6.1中MyBatisPlus IService接口深度解析与应用场景实战