京东2025届秋招 算法开发工程师 第2批笔试

目录

  • 1. 第一题
  • 2. 第二题
  • 3. 第三题

⏰ 时间:2024/08/17
🔄 输入输出:ACM格式
⏳ 时长:2h

本试卷还有选择题部分,但这部分比较简单就不再展示。

1. 第一题

村子里有一些桩子,从左到右高度依次为 1 , 1 + 2 , 1 + 2 + 3 , . . . 1,1+2,1+2+3,... 1,1+2,1+2+3,...,每两颗桩子之间的间隔为 1 1 1。现在下了一场大雪,但是不知道雪下了多厚,现在给你两个数字,这是雪后某相邻两个桩子在雪面上的高度,请你通过这两个数字计算雪的厚度。

输入描述

在一行中输入两个正整数 a , b a, b a,b 1 ≤ a < b ≤ 5 ⋅ 1 0 5 1\leq a<b\leq5\cdot10^5 1a<b5105

输出描述

在一行中输出一个整数代表雪的厚度。我们可以证明,答案一定存在。

题解

只需注意到 a k − a k − 1 = k a_k-a_{k-1}=k akak1=k,于是可以用 b − a b-a ba 定位到右边柱子的下标,计算它的高度即可。

#include <bits/stdc++.h>using namespace std;
using i64 = long long;int main() {i64 a ,b;cin >> a >> b;i64 k = b - a;i64 old_h = k * (k + 1) / 2;cout << old_h - b << endl;return 0;
}

2. 第二题

牛牛有一种锯齿状的积木,这种积木比较长,但是每个单位长度的高度是相等的,高度为 1 1 1 或者 2 2 2
现在牛牛拿出了两块长度分别为 n n n m m m 的积木,她现在想把这两块积木拼接在一起,即使中间有空隙也没有关系。但是拼接后的积木的高度要不超过 3 3 3,请你帮助牛牛计算在满足这个前提下拼接后的积木的长度最短可以是多少。
例如有两块形状如下的积木:

输入描述

第一行给出两个正整数 n , m n,m n,m,代表第一块和第二块积木的长度。
第二行给出 n n n 个数字代表第一块积木每个单位的高度。
第三行给出 m m m 个数字代表第二块积木每个单位的高度 1 ≤ n , m ≤ 1000 1\leq n,m \leq 1000 1n,m1000

输出描述

在一行中输出一个正整数代表拼接后积木的最短长度

题解

本题直接模拟即可。

说白了就是给定 a a a b b b 两个数组,初始时先让 a a a b b b 的左端对齐。

  • 先让 a a a b b b 上向右滑动,计算两者重叠部分的按位元素和,只要重叠部分中有一个位置出现了 > 3 >3 >3 的情况,说明当前拼接是无效的,继续右移。我们自然是希望 a a a 右移的距离尽可能地小
  • 再让 b b b a a a 上向右滑动,同样是找到正确的拼接位置,并使得 b b b 右移的距离尽可能小。
  • 还要考虑一种特殊情况就是无法上下拼接,此时需要将 a a a b b b 直接横向连接,长度为 m + n m+n m+n
#include <bits/stdc++.h>using namespace std;int min_len(const string& a, const string& b) {int n = a.length(), m = b.length();// a在b上滑动for (int i = 0; i < m; i++) {bool valid = true;for (int j = i; j < i + n && j < m; j++) {if (a[j - i] - '0' + b[j] - '0' > 3) {valid = false;break;}}if (valid)return max(m, i + n);}return m + n;
}int main() {int n, m;cin >> n >> m;string a, b;cin >> a >> b;cout << min(min_len(a, b), min_len(b, a)) << endl;return 0;
}

3. 第三题

牛牛也是要回家过年的呢。
牛牛所在的国家有 n n n 座城市, m m m 条有向道路,第 i i i 条道路由城市 u i u_i ui 通往城市 v i v_i vi,通行费为 w i w_i wi
作为一头豪气的牛,希望他回家的花费是一个特殊的数字(例如666元)。具体的说,牛牛希望从城市 1 1 1 移动到城市 n n n,并恰好花费 a a a 元。
请你告诉牛牛,他有多少种回家的方案?

输入描述

第一行三个整数 n , m , a ( 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 , 1 ≤ a ≤ 1000 ) n,m,a\,(1\leq n\leq 100,1\leq m\leq 1000,1\leq a\leq1000) n,m,a(1n100,1m1000,1a1000),含义如题面所示。
接下来 m m m 行,第 i i i 行三个整数 u i , v i , w i ( 1 ≤ u i , v i ≤ n , 1 ≤ w i ≤ a ) u_i,v_i,w_i\,(1\leq u_i,v_i\leq n,1\leq w_i\leq a) ui,vi,wi(1ui,vin,1wia),描述了一条道路。

输出描述

如果牛牛回家的方案数大于等于 20220201 20220201 20220201 种,请你在第一行输出 All roads lead to Home!,然后在第二行输出回家的方案数对 20220201 20220201 20220201 取模的结果。
否则只需要输出一行一个整数,表示牛牛回家的方案数。

题解

本题使用动态规划求解。

d p [ i ] [ j ] dp[i][j] dp[i][j] 为从城市 1 1 1 到城市 i i i,花费恰好为 j j j 的方案数。由于从 1 1 1 1 1 1 花费为 0 0 0,也算是一种方案,因此 d p [ 1 ] [ 0 ] = 1 dp[1][0]=1 dp[1][0]=1,其他地方为 0 0 0

假设 u → w v u\overset{w}{\to} v uwv,且在城市 u u u 的时候已经花费了 j j j,那么有如下的转移方程

d p [ v ] [ j + w ] = d p [ u ] [ j ] + d p [ v ] [ j + w ] dp[v][j + w]=dp[u][j]+dp[v][j +w] dp[v][j+w]=dp[u][j]+dp[v][j+w]

注意,在计算 v v v 的时候,我们必须要保证 u u u 已经计算完毕,因此要按照拓扑序进行计算。

#include <bits/stdc++.h>using namespace std;const int MOD = 20220201;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m, a;cin >> n >> m >> a;vector<vector<pair<int, int>>> graph(n + 1);vector<int> in(n + 1, 0);for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;graph[u].emplace_back(v, w);in[v]++;}vector<vector<int>> dp(n + 1, vector<int>(a + 1, 0));vector<bool> st(n + 1, 0);dp[1][0] = 1;queue<int> q;for (int i = 1; i <= n; i++) {if (!in[i]) q.push(i);}while (!q.empty()) {auto u = q.front();q.pop();for (auto &[v, w]: graph[u]) {if (!--in[v]) q.push(v);for (int j = 0; j + w <= a; j++) {if (dp[v][j + w] + dp[u][j] >= MOD || st[u]) {st[v] = true;}dp[v][j + w] = (dp[v][j + w] + dp[u][j]) % MOD;}}}if (st[n]) cout << "All roads lead to Home!" << endl;cout << dp[n][a] << endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/403996.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【免费】企业级大模型应用推荐:星环科技无涯·问知

无涯问知是星环科技发布的大模型应用系统&#xff0c;那么我们先简单了解下星环科技吧&#xff01; 星环科技&#xff08;股票代码&#xff1a;688031&#xff09;致力于打造企业级大数据和人工智能基础软件&#xff0c;围绕数据的集成、存储、治理、建模、分析、挖掘和流通等数…

这个是git使用的合集

如果遇到了关于git和github的bug就会写这里 2024/8/16 github一直没有打卡和上传代码是因为感觉除了做项目的情况&#xff0c;普通的学习和普通的笔记没必要记在github里&#xff1b;如果是笔记类的东西为什么不记在csdn上呢&#xff1f;如果是算法题算法网站上回有记录啊&am…

CAD图纸加密软件哪个好?(这六款大众好评度高!)

在CAD图纸加密软件领域&#xff0c;有多款软件因其高效、安全、易用等特点而广受好评。 以下是六款大众好评度较高的CAD图纸加密软件&#xff0c;它们各自具有独特的功能和优势&#xff1a; 1.安企神 特点&#xff1a;它以其强大的透明加密技术和精细化的权限管理功能著称。 …

python爬虫爬取某图书网页实例

文章目录 导入相应的库正确地设置代码的基础部分设置循环遍历遍历URL保存图片和文档全部代码即详细注释 下面是通过requests库来对ajax页面进行爬取的案例&#xff0c;与正常页面不同&#xff0c;这里我们获取url的方式也会不同&#xff0c;这里我们通过爬取一个简单的ajax小说…

MPU6050详细介绍

一、MPU6050介绍 MPU6050是由三个陀螺仪和三个加速度传感器组成的6轴运动处理组件 内部主要结构&#xff1a;陀螺仪、加速度计、数字运动处理器DMP&#xff08;Digital Motion Processor&#xff09; MPU6050有两个IIC接口&#xff0c;第一IIC接口可作为主接口给单片机传输数…

CSP-CCF 202012-1 期末预测之安全指数

一、问题描述 二、解答 #include<iostream> using namespace std; int main() {int n;cin >> n;int w[100001] { 0 };int score[100001] { 0 };for (int i 1; i < n; i){cin >> w[i] >> score[i];}int y 0;for (int i 1; i < n; i){y y …

电脑监控软件有哪些,哪款更好用?一网打尽!电脑监控软件大搜罗,总有一款适合你!

甲&#xff1a;哎&#xff0c;您听说了吗&#xff1f;这年头&#xff0c;电脑监控软件那是五花八门&#xff0c;跟变戏法似的&#xff01; 乙&#xff1a;哦&#xff1f;怎么个五花八门法&#xff1f; 甲&#xff1a;嘿&#xff0c;您还别说&#xff0c;从实时监控到网络追踪…

在HFSS中对曲线等结构进行分割(Split)

在HFSS中对曲线进行分割 我们往往需要把DXF等其他类型文件导入HFSS进行分析&#xff0c;但是有时需要对某一个曲线单独进行分割成两段修改。 如果是使用HFSS绘制的曲线&#xff0c;我们修改起来非常方便&#xff0c;修改参数即可。但是如果是导入的曲线&#xff0c;则需要使用…

js实现图片以鼠标为中心滚轮缩放-vue

功能背景 实现以鼠标在图中的位置为中心进行图片的滚轮缩放&#xff0c;现在是无论鼠标位置在哪都以图片中心进行缩放&#xff0c;这不符合预期&#xff1b; 关键点 缩放前鼠标在的位置是 A&#xff08;clinetX,clientY&#xff09; 点&#xff0c;缩放后鼠标的位置是 A’&a…

技术分享-商城篇-订单支付微信篇(十二)

B2C商城微信支付全解析&#xff1a;H5支付、小程序支付、JSAPI支付与APP支付 引言 在之前的文章中&#xff0c;我们聊了B2B2C的商城相关功能模块&#xff0c;如&#xff1a;首页布局、商品、购物车、购物结算、订单支付等&#xff0c;但是B2C商城的订单支付方式的选择&#x…

【Docker】Centos系统没有Vpn时候安装Docker

【Docker】没有Vpn时候安装Docker 背景1.安装docker之前先卸载2.基础配置3.安装docker5. 问题解决6.配置docker镜像源&#xff0c;解决网络超时 背景 工作中习惯VPN或者服务器节点为国外或者香港节点&#xff0c;最近买了一台国内服务器网络受到各种限制。 1.安装docker之前先…

uniapp/vue个性化单选、复选组件

个性化单选和复选组件在网页设计中非常常见&#xff0c;它们不仅能够提升用户界面的美观度&#xff0c;还能改善用户体验。此组件是使用vue uniapp实现的个性化单选复选组件。设计完成后&#xff0c;点击生成源码即可。 拖动组件过设计区 每行显示数量 默认支持每行三个&#…

扎心“我学了六个月 Python,怎么还是会找不到工作”

前言 &#x1f449; 小编已经为大家准备好了完整的代码和完整的Python学习资料&#xff0c;朋友们如果需要可以扫描下方CSDN官方认证二维码或者点击链接免费领取【保证100%免费】 在编程界&#xff0c;Python是一种神奇的存在。有人认为&#xff0c;只有用Python才能优雅写代码…

等保测评中的安全需求分析:构建精准的信息安全防护体系

在数字化转型的时代背景下&#xff0c;信息安全成为企业发展的关键因素之一。等保测评&#xff0c;作为我国信息安全等级保护制度的重要组成部分&#xff0c;要求企业进行详细的安全需求分析&#xff0c;以构建精准、有效的信息安全防护体系。本文旨在探讨等保测评中的安全需求…

ThreeJs学习笔记--坐标系,光源,相机控件

坐标系 一、创建添加坐标系 给场景添加坐标系THREE.AxesHelper()的参数表示坐标系坐标轴线段尺寸大小&#xff0c;你可以根据需要改变尺寸 const axesHelper new THREE.AxesHelper(200)//数值是坐标的尺寸 scene.add(axesHelper)//添加到场景里 坐标系包含三个坐标轴&…

本地ComfyUI安装全记录

资料 先看我写的stable diffusion全记录 ComfyUI 完全入门&#xff1a;安装部署 ComfyUI 完全入门&#xff1a;图生视频 ComfyUI【强烈推荐】 秋葉aaaki comfy UI整合包 可以使用stable diffusion的大模型&#xff0c;通过修改文件重新指向 修改路径即可 下载秋叶大佬的…

python之matplotlib (3 坐标轴设置)

写在前面 在说明坐标轴设置之前&#xff0c;我有必要和大家说清楚图像设置的一些方法&#xff0c;避免陷入困扰模糊的地步。前面我们说过&#xff0c;画图的三种方法&#xff08;python之matplotlib &#xff08;1 介绍及基本用法&#xff09;-CSDN博客&#xff09;。而设置也…

yolov8目标检测与速度估计

我们可能都见过限速路牌。我们中的一些人甚至可能收到过通过邮寄或电子邮件发送的自动限速违规通知。人工智能&#xff08;AI&#xff09;交通管理系统可以利用计算机视觉技术自动标记超速违规行为。路灯和高速公路上的摄像头拍摄的实时画面可用于估算车速和加强道路安全。 车速…

博世(BOSCH)× Milvus:智能驾驶领域的数据挖掘革新

01.博世智能驾控&#xff1a;智能驾驶技术的领航者 博世&#xff08;BOSCH&#xff09;智能驾控是全球汽车技术领域的领导者&#xff0c;以其在自动驾驶技术上的创新和深厚历史而闻名。博世的自动驾驶解决方案&#xff0c;包括先进的驾驶辅助系统&#xff08;ADAS&#xff09;…

【数据结构与算法】归并排序

归并排序目录 一.归并排序的原理二.有序的归并实现三.无序的归并实现(分治法)四.归并排序的实现五.完整代码 一.归并排序的原理 如何将这两个数组排序? 二.有序的归并实现 将一个数组分为两段,那边的值小就加入到新数组中,直到一边已经加完了. 有一种情况就是一边已经加入…