hope实验室预备役第4次测试题解

2024-02-21 02:04

本文主要是介绍hope实验室预备役第4次测试题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.Foreign Exchange

2.Takahashi Gets Lost

3.Sasha and the Beautiful Array

4.Sasha and the Drawing

5.Sasha and the Casino

6.Only one of two

7.村村通

8.传送门


1.Foreign Exchange

 原题链接

Sample 1

InputcopyOutputcopy
4
5 7 0 3
2 2
4 3
5 2
5

Sample 2

InputcopyOutputcopy
10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1
45

这道题给出了有多少每国的货币,让我们求出最多可以拥有多少第n国的货币,又有第i国可以兑换第i+1国的货币的特性,我们直接将所有的第i国的货币换成i+1国的货币便可以求出第n国的货币。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
long long n,a[200010];
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n-1;i++){int in,out;cin>>in>>out;a[i+1]+=(a[i]/in)*out;//看看能换多少份}cout<<a[n]<<endl;return 0;
}

注意:需要long long类型,不然会爆int!

2.Takahashi Gets Lost

 原题链接

Sample 1

InputcopyOutputcopy
6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######
2

Sample 2

InputcopyOutputcopy
13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################
6

按照给出的字符串(只含L,R,D,U),L为向左走一步,R为向右走一步,D为向下走一步,U为向上走一步。

我们可以遍历地图的每一个位置(这个位置本身要是陆地),看看执行字符串的操作会不会走到海洋,如果完成所以操作也没有走到海洋,那么此位置为一个可能落地位置,答案计数加1。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
string mp[600],t;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};//下,上,右,左 
bool check(int x,int y)
{if(mp[x][y]=='#') return false;for(int i=0;i<k;i++){if(t[i]=='D')x+=dx[0],y+=dy[0];else if(t[i]=='U')x+=dx[1],y+=dy[1];else if(t[i]=='R')x+=dx[2],y+=dy[2];else x+=dx[3],y+=dy[3];if(mp[x][y]=='#')//若发现当前位置不合理,直接返回错误 return false;}return true;//这个位置可以完成操作 
}
int main()
{cin>>n>>m>>k>>t;for(int i=0;i<n;i++) cin>>mp[i];for(int i=1;i<n-1;i++){//因为四周固定都是海洋,所以从1到n-2(m-2)就行 for(int j=1;j<m-1;j++){if(check(i,j))ans++;}}cout<<ans<<endl;return 0;
}

3.Sasha and the Beautiful Array

原题链接

Sample 1

InputcopyOutputcopy
5
3
2 1 3
3
69 69 69
5
100 54 80 43 90
4
3 4 3 3
2
2 1
2
0
57
1
1

这道题没什么好讲的,直接排序,累加后一个元素减去前一个元素就是最大美丽度。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
long long n,a[200];
int main()
{int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);long long ans=0;for(int i=2;i<=n;i++){ans+=(a[i]-a[i-1]);}cout<<ans<<endl;}return 0;
}

4.Sasha and the Drawing

原题链接

Sample 1

InputcopyOutputcopy
7
3 4
3 3
3 10
3 9
4 7
7 11
2 3
2
2
6
5
4
6
2

纯思路题,当然我也搞不懂原理,但是我根据图片和输入样例发现,一个着色单元格最多可以包含两条对角线,当对角线满时(也就是对角线的数量为4n-2),只需要将方形矩阵的上下两条边的单元格全部着色即可,也就是n*2个单元格。

根据上面和分析样例,于是出现了下面AC代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{int t;cin>>t;while(t--){long long n,k;cin>>n>>k;if(k==4*n-2)cout<<n*2<<endl;else{long long ans=(k+1)/2;cout<<ans<<endl;}}return 0;
}

5.Sasha and the Casino

原题链接

Sample 1

InputcopyOutputcopy
9
2 1 7
2 1 1
2 3 15
3 3 6
4 4 5
5 4 7
4 88 1000000000
25 69 231
13 97 18806
YES
NO
YES
NO
NO
YES
NO
NO
NO

既然需要保证他能在某个时刻拥有任意个硬币,那么就要考虑连续输到下一次不会输的情况。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ll t;cin>>t;while(t--){ll k,x,a;cin>>k>>x>>a;ll f1,f2,flag=0;f1=1;for(int i=0;i<x-1;i++){f2=(f1)/(k-1)+1;f1+=f2;if(f1>a)//要是一直输,钱不够输 {flag=1;break;} }if(flag||(a-f1)*k<=a) cout<<"NO"<<endl;//输完,保底的本钱比原来还少也不能某个时刻达到任意钱 else cout<<"YES"<<endl;}return 0;
}

6.Only one of two

原题链接

 

Sample 1

InputcopyOutputcopy
2 3 5
9

Sample 2

InputcopyOutputcopy
1 2 3
5

Sample 3

InputcopyOutputcopy
100000000 99999999 10000000000
500000002500000000

题目要求我们找出只能被n和m其中一个整除的第k个数。

第一个样例很好解释题目的要求,是不是想暴力求解,但是看这数据范围,估计算到开学也算不完。

所以我们可以想到使用二分去解决它,首先把left~right的范围定义得大一些,我们需要的答案就在这个范围里面,记得里面的数据都需要用long long类型哦!

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,l=1,r=2e18;
int gc(long long a,long long b) //找最大公约数 
{    if(b) while((a%=b) && (b%=a));    return a+b;
}
int main()
{cin>>n>>m>>k;long long f=n*m/gc(n,m);//最大公倍数,用于减去这个数可以同时被n和m整除的情况 while(l<r){long long mid=(l+r)/2;if(mid/n+mid/m-mid/f*2>=k)//mid/n代表有多少个数被n整除,mid/f*2为有多少数同时被n和m整除, r=mid;// 如果mid/n+mid/m-mid/f*2大于我们要找的第k个数,什么当前的mid大于我们要找的答案,压缩边界 else l=mid+1;}cout<<l<<endl;return 0;
}

7.村村通

原题链接

Sample 1

InputcopyOutputcopy
4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0
1
0
2
998

一个最小生成树的模板题,直接将有的边先建入,再看看还需要建多少边才能串通全部村子。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,pre[1001];
int find(int x)
{if(pre[x]==x) return x;return pre[x]=find(pre[x]);
}int main()
{while(scanf("%d",&n)){if(n!=0) cin>>m;//输入停止标志 else break;int ans=0;for(int i=1;i<=n;i++) pre[i]=i;while(m--){int a,b;cin>>a>>b;pre[find(a)]=find(b);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(find(i)!=find(j)){ans++;//建入一个边,答案+1 pre[find(i)]=find(j);}}}cout<<ans<<endl;}return 0;
}

8.传送门

原题链接

Sample 1

InputcopyOutputcopy
4 5
1 2 3
1 3 6
2 3 4
2 4 7
3 4 2
14

对于这道题我一直在想,传送门应该要怎么建立,后面才看到这数范围(n<=100),所以是需要对任意两个教学楼都建立一次传送门,看哪个的最短路径和最小。

那就使用全源最短路径Floyd 算法来暴力求解,但是我们试想一下,这样就有5层for循环,还是会超时,所以我们需要缩减到4层。

因为只有使用了传送门才会影响最短路径,所有有了下面代码。

            for(int x=1;x<=n;x++){for(int y=1;y<=n;y++){if(mp2[x][j]<inf&&mp2[j][y]<inf)mp2[x][y]=min(mp2[x][y],mp2[x][j]+mp2[j][y]);}}for(int x=1;x<=n;x++){for(int y=1;y<=n;y++){if(mp2[x][i]<inf&&mp2[i][y]<inf)mp2[x][y]=min(mp2[x][y],mp2[x][i]+mp2[i][y]);}}

i,j是建传送门的教学楼,会影响最短路径,所以只需要分别对这两个教学楼的最短路径的计算更新即可。

下面是AC代码:

#include<bits/stdc++.h>
#define inf 1234567890
using namespace std;
int n,m,mp1[120][120],mp2[120][120],ans=inf;
void back()//返回原图 
{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){mp2[i][j]=mp1[i][j];}}
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp1[i][j]=inf;for(int i=1;i<=m;i++){int x,y,z;cin>>x>>y>>z;mp1[x][y]=mp1[y][x]=z;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(mp1[i][k]<inf&&mp1[k][j]<inf)//先计算没有建立传送门的最短路径 mp1[i][j]=min(mp1[i][j],mp1[i][k]+mp1[k][j]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){back();//每次返回原图 mp2[i][j]=mp2[j][i]=0;//建立传送门 for(int x=1;x<=n;x++){for(int y=1;y<=n;y++){if(mp2[x][j]<inf&&mp2[j][y]<inf)mp2[x][y]=min(mp2[x][y],mp2[x][j]+mp2[j][y]);}}for(int x=1;x<=n;x++){for(int y=1;y<=n;y++){if(mp2[x][i]<inf&&mp2[i][y]<inf)mp2[x][y]=min(mp2[x][y],mp2[x][i]+mp2[i][y]);}}int cnt=0;for(int x=1;x<=n;x++){for(int y=x+1;y<=n;y++){cnt+=mp2[x][y];//计算最短路径和 }}ans=min(ans,cnt);//更新最小 }}cout<<ans<<endl;return 0;
}

这篇关于hope实验室预备役第4次测试题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/730253

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

基于JSP的实验室管理系统

你好呀,我是计算机学姐码农小野!如果有相关需求,可以私信联系我。 开发语言:Java 数据库:MySQL 技术:JSP技术 + Spring Boot框架 工具:IDEA/Eclipse、Navicat、Tomcat 系统展示 首页 用户个人中心 实验室管理 设备报备管理 摘要 随着社会的发展和科学技术的进步,互联网技术越来越受欢迎。网络计算机

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

2025年25届计算机毕业设计:如何实现高校实验室Java SpringBoot教学管理系统

✍✍计算机毕业编程指导师** ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java、Python、微信小程序、大数据实战项目集 ⚡⚡文末获取源码 文章目录 ⚡⚡文末获取源码高校实验室教学管理系统-研究背景高校实验室教学管理系