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

ACM题解|牛客周赛 Round 37

article 2025/1/11 4:25:45

在这里插入图片描述

🔥博客介绍`： EvLast

🎥系列专栏： <<数据结构与算法>> << 算法入门>> << C++项目>>

🎥 当前专栏: << 牛客周赛>>

专题 : 数据结构帮助小白快速入门算法
👍👍👍👍👍👍👍👍👍👍👍👍
☆*: .｡. o(≧▽≦)o .｡.:*☆

❤️感谢大家点赞👍收藏⭐评论✍️

在这里插入图片描述

学习目标：

今日学习打卡
在这里插入图片描述

  • ACM题解

❤️学习时间：

  • 周一至周五晚上 7 点—晚上9点
  • 周六上午 9 点-上午 11 点
  • 周日下午 3 点-下午 6 点

🥰学习内容：

在这里插入图片描述

  1. 雾之湖的冰精
  2. 博丽神社的巫女
  3. 红魔馆的馆主
  4. 迷途之家的大贤者
  5. 魔法之森的蘑菇
  6. 三途川的摆渡人

😎内容详细：

雾之湖的冰精

题目考点: 语言题
在这里插入图片描述

解题思路: 输入 n, m 如果 n + m 大于 9 输出 NO 小于 9 输出 YES

#include<bits/stdc++.h>
#define Run 0
#define endl "\n"
using ll = long long;

class Solution {
public: 
    void solve() {
       int n,m;std::cin >> n >> m;
        if (n + m > 9) {
            std::cout << "No\n";
            return ;
        }
        std::cout << "Yes\n";
    }
};

signed main() {
    std::cin.tie(0) -> std::ios::sync_with_stdio(false);
    std::cout.tie(0) -> std::ios::sync_with_stdio(false);
    
#if Run
    int _;std::cin>>_;while(_--) Solution().solve();
#else
    Solution().solve();
#endif
    return 0;
}

博丽神社的巫女

在这里插入图片描述

解题思路: 将数组排序,然后逐步比较当数组a[i]大于 x 时 则前面的数据为满足魔女的最大数,注意下标从 0 开始 数量为 j + 1

#include<bits/stdc++.h>
#define Run 0
#define endl "\n"
using ll = long long;

class Solution {
public: 
    void solve() {
        int n,x; std::cin >> n >> x;
        std::vector<ll> a(n);
        for (auto & x: a) std::cin >> x;
        std::sort(a.begin(),a.end());  // 排序
        ll j = -1; 
        for (int i = 0; i < n; i++) {
            if (x >= a[i]) { //比交大小只要大于输出下标 + 1即最大魔女数
                j = i;
            }
        }
        if (j == -1) {
            std::cout << 0 <<" "<< x << endl;
        } else {
            std::cout << j + 1 << " " << x - a[j] << endl;
        }
    }
};

signed main() {
    std::cin.tie(0) -> std::ios::sync_with_stdio(false);
    std::cout.tie(0) -> std::ios::sync_with_stdio(false);
    
#if Run
    int _;std::cin>>_;while(_--) Solution().solve();
#else
    Solution().solve();
#endif
    return 0;
}

红魔馆的馆主

在这里插入图片描述

思路: 对 n 取模, 然后将取模数的当成前缀,去 495 的倍数中找与之相等前缀的公倍数,这样就能找到答案,然后输出后面的几个数即答案

#include<bits/stdc++.h>
#define Run 0
#define endl "\n"
#define mod 495
using ll = long long;
using namespace std;

class Solution {
public: 
    void solve() {
        ll n; std::cin >> n; 
        if (n % mod == 0) {
            std::cout << -1 << endl;
        }
        std::string t = to_string(n % mod); // 取模,这个什么神器的思路?
        ll b = t.size();
        for (ll i = 1; ; i++) {
            ll m = mod * i;
            std::string k = std::to_string(m);
            if (k.substr(0,b) == t) {
                std::cout << k.substr(b) << endl;
                return ;
            }
        }
    }
};

signed main() {
    std::cin.tie(0) -> std::ios::sync_with_stdio(false);
    std::cout.tie(0) -> std::ios::sync_with_stdio(false);
    
#if Run
    int _;std::cin>>_;while(_--) Solution().solve();
#else
    Solution().solve();
#endif
    return 0;
}

思路2 : 深度优先搜索

#include<bits/stdc++.h>
#define Run 0
#define endl "\n"
using ll = long long;
using namespace std;
class Solution {
public: 
    void solve() {
        ll n; std::cin >> n;
        if (n % 495 == 0) {
            std::cout << -1 << endl;
            return ;
        }
        ll tmp = n;
        for (ll i = 1; i <= 4; i++) {
            if (dfs(i,0,n)) break; 
        }
        std::cout << path << "\n";
       
    } // dfs遍历查找区间
    bool dfs(ll cur, ll depth, ll t) {
        if (cur == depth) {
            if (t % 495 == 0) return true;
            
            return false;
        }
        for (ll i = 0; i <= 9; i++) {
            path += to_string(i);
            ll tm = ((t % 495 * 10 % 495) + i ) % 495;
            if (dfs(cur, depth + 1, tm)) return true;
            path.pop_back();
        }
        return false;
    }
private:
    std::string path = ""; 
};

signed main() {
    std::cin.tie(0) -> std::ios::sync_with_stdio(false);
    std::cout.tie(0) -> std::ios::sync_with_stdio(false);
    
#if Run
    int _;std::cin>>_;while(_--) Solution().solve();
#else
    Solution().solve();
#endif
    return 0;
}

迷途之家的大贤者

在这里插入图片描述

思路: 每次都取最优,上次最大的然后留下边界最小的让后面没有办法操作

#include<bits/stdc++.h>
#define Run 0
#define endl "\n"
#define N 1000
using ll = long long;

int dp[10]; // 0 - 9的下标

class Solution {
public: 
     void solve() {
        std::string s; ll n;
        std::cin>>n>>s;
        std::cout << std::max(s[0],s.back());
        return ;
    }
};


signed main() {
    std::cin.tie(0) -> std::ios::sync_with_stdio(false);
    std::cout.tie(0) -> std::ios::sync_with_stdio(false);
    
#if Run
    int _;std::cin>>_;while(_--) Solution().Solve();
#else
    Solution().solve();
#endif
    return 0;
}

魔法之森的蘑菇

在这里插入图片描述

思路: 创建3位数组,进行 bfs遍历, 每一层数组只能往一个方向运动, 当遇到 ‘#’ 时 进入到对应的层 进行运动

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int N = 1010;

char g[N][N][4];

int px[4] = {-1,0,1,0};
int py[4] = {0,1,0,-1};

int dp[N][N][4];

void solve()
{
    int n,m; cin >> n >> m;
    int sx,sy,ex,ey;
    memset(dp,0x3f,sizeof dp);
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++)
        {
            char c; cin >> c;
            for(int p = 0 ; p < 4 ; p ++)
                g[i][j][p] = c;
            if(g[i][j][1] == 'S')
                sx = i,sy = j;
            if(g[i][j][1] == 'T')
                ex = i,ey = j;
        }
    for(int i = 0 ; i < 4 ; i ++)
        dp[sx][sy][i] = 0;
    queue<vector<int>> q;
    for(int i = 0 ; i < 4 ; i ++)
        q.push({sx,sy,i});
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int x = t[0],y = t[1],p = t[2];
        int xx = x + px[p] ,yy = y + py[p];
        if(xx <= 0 || xx > n || yy <= 0 || yy > m || g[xx][yy][p] =='#')
            continue;
        if(g[xx][yy][p] == '.')
        {
            if(dp[xx][yy][p] > dp[x][y][p] + 1)
            {
                dp[xx][yy][p] = dp[x][y][p] + 1;
                q.push({xx,yy,p});
            }
        }
        else 
        {
            for(int i = 0 ; i < 4 ; i ++)
            {
                //if((i ^ p) == 0) continue;
                if(dp[xx][yy][i] > dp[x][y][p] + 1)
                {
                    dp[xx][yy][i] = dp[x][y][p] + 1;
                    q.push({xx,yy,i});
                }
            }
        }
    }
    int res = 0x3f3f3f3f;
    for(int i = 0 ; i < 4 ; i ++)
        res = min(dp[ex][ey][i],res);
    if(res != 0x3f3f3f3f) cout << res << '\n';
    else cout << -1 << '\n';
}

int main()
{
    int t; cin >> t; 
    while( t --)
    {
        solve();
    }
}

三途川的摆渡人

在这里插入图片描述

思路: 用桶的思想存储每个数据,然后对数据进行类背包dp , 当然也可以回溯算法进行解决

#include<bits/stdc++.h>
#define Run 1
#define endl "\n"
#define mod 495
using ll = long long;
using namespace std;

class Solution {
public: 
    void solve()  // 类背包dp 某值区较小
    {
        int n,x; std::cin >> n;
        std::memset(tong, 0, sizeof tong);
        for (int i = 0; i < n; i++) std::cin >> x,tong[x]++;
        std::memset(dp,0x3f,sizeof dp);
        for (int i = 0; i <= 200; i++) {
            if (tong[i]) {
                dp[i][1] = 1;
                for (int j = 0; j <= 200; j++) {
                    dp[i & j][1] = std::min(dp[i & j][1],dp[j][0] + 1);
                }
                for (int j = 0; j <= 200; j++) {
                    dp[j][0] = dp[j][1];
                }
            }
        }
        if (dp[0][0] > n) std::cout << -1 << '\n';
        else std::cout << n - dp[0][0] << '\n';
    }
private:
    int tong[202];
    int dp[202][2];
};

signed main() {
    std::cin.tie(0) -> std::ios::sync_with_stdio(false);
    std::cout.tie(0) -> std::ios::sync_with_stdio(false);
    
#if Run
    int _;std::cin>>_;while(_--) Solution().solve();
#else
    Solution().solve();
#endif
    return 0;
}

😘学习产出：

  • 技术笔记 2 遍
  • CSDN 技术博客 3 篇
  • 习的 vlog 视频 1 个

在这里插入图片描述

  • 周赛视频教学: 牛客周赛 Round 37
  • 相关周赛代码仓库: 牛客周赛 Round 37 代码

重磅消息:

GTP - 4 最新版接入服务他来了 点击链接即可查看详细

GTP - 4 搭建教程

🔥如果此文对你有帮助的话，欢迎💗关注、👍点赞、⭐收藏、✍️评论，支持一下博主~


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

相关文章：

  • Windows11环境下设置MySQL8字符集utf8mb4_unicode_ci
  • （二十八）Flask之wtforms库【上手使用篇】
  • 【Unity3D】Text文本文字掉落效果
  • 汽车信息安全 -- S32K1如何更新BOOT_MAC
  • 【竞技宝】CS2:HLTV2024职业选手排名TOP8-broky
  • 基于MATLAB的汽车热管理模型构建
  • 解释MVC和MVVM架构模式
  • How to manage Python environment based on virtualenv in Ubuntu 22.04
  • 算法沉淀——贪心算法二（leetcode真题剖析）
  • 【JavaScript】变量的解构赋值
  • HandyControl PropertyGrid及自定义编辑器
  • C++提高笔记（六）---STL函数对象、STL常用算法（遍历、查找）
  • 基于Spring Boot家政服务系统
  • MediaBox音视频终端SDK已适配鸿蒙星河版（HarmonyOS NEXT）
  • wsl ubuntu 安装cuda nvcc环境
  • 使用 Python 编写网络爬虫：从入门到实战
  • 【数据库】数据库语言
  • mudo服务器测试二
  • Visual Studio配置libtorch(cuda安装一步到位)
  • camelot pdf提取表格实践（记录）
  • 计算机网络拓扑结构
  • 通过spring boot/redis/aspect 防止表单重复提交【防抖】
  • 一键制作iOS上架App Store描述文件教程
  • 从SQL质量管理体系来看SQL审核(2) - SQL质量标准
  • 优化选址问题 | 粒子群算法求解物流选址问题含Matlab源码
  • Transformer的前世今生 day03（Word2Vec