ACM题解|牛客周赛 Round 37

在这里插入图片描述

🔥博客介绍`： 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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

算法沉淀——贪心算法二（leetcode真题剖析）

算法沉淀——贪心算法二（leetcode真题剖析）

算法沉淀——贪心算法二 01.最长递增子序列02.递增的三元子序列03.最长连续递增序列04.买卖股票的最佳时机 01.最长递增子序列 题目链接&#xff1a;https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子…
阅读更多...
HandyControl PropertyGrid及自定义编辑器

HandyControl PropertyGrid及自定义编辑器

前提条件 项目引入对应HandyControl对应版本包。 使用案例 UI部分 <Window xmlns:hc"https://handyorg.github.io/handycontrol"><hc:TabControl><hc:TabItem Header"默认样式"><hc:PropertyGrid Width"380" SelectedO…
阅读更多...
基于Spring Boot家政服务系统

基于Spring Boot家政服务系统

摘 要 相比于以前的传统手工管理方式&#xff0c;智能化的管理方式可以大幅降低家政公司的运营人员成本&#xff0c;实现了家政服务的标准化、制度化、程序化的管理&#xff0c;有效地防止了家政服务的随意管理&#xff0c;提高了信息的处理速度和精确度&#xff0c;能够及时、…
阅读更多...
MediaBox音视频终端SDK已适配鸿蒙星河版（HarmonyOS NEXT）

MediaBox音视频终端SDK已适配鸿蒙星河版（HarmonyOS NEXT）

2024年1月&#xff0c;HarmonyOS NEXT 鸿蒙星河版系统开发者预览版开放申请&#xff0c;该系统将只能安装为鸿蒙开发的原生应用&#xff0c;而不再兼容安卓应用。对此&#xff0c;阿里云MediaBox音视频终端SDK产品已实现功能的鸿蒙化迁移和重构&#xff0c;全面适配鸿蒙系统Har…
阅读更多...
wsl ubuntu 安装cuda nvcc环境

wsl ubuntu 安装cuda nvcc环境

wsl ubuntu 安装cuda环境&#xff1a; CUDA Toolkit 11.6 Downloads | NVIDIA DeveloperDownload CUDA Toolkit 11.6 for Linux and Windows operating systems.https://developer.nvidia.com/cuda-11-6-0-download-archive?target_osLinux&target_archx86_64&Distri…
阅读更多...
使用 Python 编写网络爬虫：从入门到实战

使用 Python 编写网络爬虫：从入门到实战

网络爬虫是一种自动化获取网页信息的程序&#xff0c;通常用于数据采集、信息监控等领域。Python 是一种广泛应用于网络爬虫开发的编程语言&#xff0c;具有丰富的库和框架来简化爬虫的编写和执行过程。本文将介绍如何使用 Python 编写网络爬虫&#xff0c;包括基本原理、常用库…
阅读更多...
mudo服务器测试二

mudo服务器测试二

目录 业务处理超时测试 测试代码 客户端 服务端 同时多条请求测试 测试代码 客户端 服务端 大文件传输测试 测试代码 客户端 服务端 服务器性能压力测试说明 客户端 服务端 业务处理超时测试 测试代码 ​ /* 业务处理超时&#xff0c;查看服务器的处理情况当服…
阅读更多...
Visual Studio配置libtorch(cuda安装一步到位)

Visual Studio配置libtorch(cuda安装一步到位)

Visual Studio配置libtorch visual Studio安装cuDNN安装CUDAToolkit安装libtorch下载Visual Studio配置libtorch(cuda版本配置) visual Studio安装 visual Studio点击安装 具体的安装和配置过程这里就不进行细讲了&#xff0c;可以参考我这篇博客Visual Studio配置OpenCV(保姆…
阅读更多...
camelot pdf提取表格实践（记录）

camelot pdf提取表格实践（记录）

参考&#xff1a; 巧用Python的camelot库批量提取PDF发票信息 关于文本pdf的表格抽取 AttributeError: module ‘camelot‘ has no attribute ‘read_pdf‘及类似问题解决办法 camelot 参数 https://blog.csdn.net/INTSIG/article/details/123000010 报错解决&#xff1a; Mod…
阅读更多...
通过spring boot/redis/aspect 防止表单重复提交【防抖】

通过spring boot/redis/aspect 防止表单重复提交【防抖】

一、啥是防抖 所谓防抖&#xff0c;一是防用户手抖&#xff0c;二是防网络抖动。在Web系统中&#xff0c;表单提交是一个非常常见的功能&#xff0c;如果不加控制&#xff0c;容易因为用户的误操作或网络延迟导致同一请求被发送多次&#xff0c;进而生成重复的数据记录。要针…
阅读更多...
一键制作iOS上架App Store描述文件教程

一键制作iOS上架App Store描述文件教程

目录 摘要 引言 正文 1. 登陆软件并创建描述文件 3. 提取iOS已上架描述文件 总结 摘要 本篇博文详细介绍了在iOS上架过程中所需的基础项目&#xff0c;包括IOS生产环境证书、APPID包名制作以及APP的描述文件。通过使用appuploader进行证书制作和上传IPA到App Store&…
阅读更多...
优化选址问题 | 粒子群算法求解物流选址问题含Matlab源码

优化选址问题 | 粒子群算法求解物流选址问题含Matlab源码

目录 问题代码问题 粒子群优化（Particle Swarm Optimization, PSO）算法是一种基于群体智能的优化算法，它通过模拟鸟群捕食行为中的信息共享机制来求解优化问题。在物流选址问题中，我们可以使用PSO算法来寻找最优的物流中心位置，以最小化总的运输成本或最大化服务效率等目…
阅读更多...
Transformer的前世今生 day03（Word2Vec

Transformer的前世今生 day03（Word2Vec

前情回顾 由上一节&#xff0c;我们可以得到&#xff1a; 任何一个独热编码的词都可以通过Q矩阵得到一个词向量&#xff0c;而词向量有两个优点&#xff1a; 可以改变输入的维度&#xff08;原来是很大的独热编码&#xff0c;但是我们经过一个Q矩阵后&#xff0c;维度就可以控…
阅读更多...
内盘期货交易系统的全开源代码

内盘期货交易系统的全开源代码

内盘期货交易系统全开源代码是一款专为期货交易者设计的软件&#xff0c;它基于开源理念&#xff0c;允许用户自由访问、修改和扩展其功能&#xff0c;以满足不同交易者的个性化需求。以下是对该软件的详细功能介绍&#xff1a; 一、实时行情展示 系统能够实时获取期货市场的…
阅读更多...
代码随想录算法训练营第day31|455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

代码随想录算法训练营第day31|455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和

什么是贪心 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 这么说有点抽象&#xff0c;来举一个例子&#xff1a; 例如&#xff0c;有一堆钞票&#xff0c;你可以拿走十张&#xff0c;如果想达到最大的金额&#xff0c;你要怎么拿&#xff1f; 指定每…
阅读更多...
安装vcenter管理esxi

安装vcenter管理esxi

安装vcenter管理esxi虚拟化操作系统 文章目录 安装vcenter管理esxi虚拟化操作系统1.安装vcenter2.vcenter的应用 1.安装vcenter esxi虚拟机具体安装步骤请参考上一篇文章&#xff0c;vcenter软件包需自己到网上下 2.vcenter的应用
阅读更多...
SD卡RAW故障解析与数据恢复全攻略

SD卡RAW故障解析与数据恢复全攻略

一、SD卡RAW现象解析 SD卡作为现代电子设备中常见的存储介质&#xff0c;其稳定性和可靠性直接关系到我们日常工作和生活的数据安全。然而&#xff0c;有时我们会遇到SD卡突然变成RAW格式的情况&#xff0c;这通常意味着SD卡的文件系统出现了严重的问题&#xff0c;导致无法正…
阅读更多...
24计算机考研调剂 | 【官方】山东师范大学（22自命题）

24计算机考研调剂 | 【官方】山东师范大学（22自命题）

山东师范大学2024年拟接收调剂 考研调剂信息 调剂专业目录如下&#xff1a; 计算机技术&#xff08;085404&#xff09;、软件工程&#xff08;085405&#xff09; 补充内容 我校2024年硕士研究生调剂工作将于4月8日教育部“中国研究生招生信息网”&#xff08;https://yz.ch…
阅读更多...
C#，图论与图算法，图（Graph）广度优先遍历（BFS，Breadth First Search）算法与源代码

C#，图论与图算法，图（Graph）广度优先遍历（BFS，Breadth First Search）算法与源代码

1 深度优先算法与 宽度优先遍历 深度优先算法（DFS，Deep First Search）与 宽度优先遍历（BFS，Breadth First Search） 是树、图数据结构的基础性、标准性的遍历算法。 2 深度优先算法（DFS，Deep First Search） 深度优先搜索（DFS）是一种用于搜索图形或树数据结构的算法…
阅读更多...
Linux docker1--环境及docker安装

Linux docker1--环境及docker安装

一、基础环境要求 Docker分为ce版本&#xff08;免费&#xff0c;试用7个月&#xff09;和ee版本&#xff08;收费&#xff09;。 最低配置要求&#xff1a;64位操作系统&#xff0c;centOS 7及以上&#xff0c;内核版本不低于3.10 二、部署docker 1、查看服务的基础环境是否满…
阅读更多...
最新文章

Copyright @ 2022~2023