加工零件C++
题目:

样例解释:
样例#1:
编号为 1 的工人想生产第 1 阶段的零件,需要编号为 2 的工人提供原材料。
编号为 2 的工人想生产第 1 阶段的零件,需要编号为 1 和 3 的工人提供原材料。
编号为 3 的工人想生产第 1 阶段的零件,需要编号为 2 的工人提供原材料。
编号为 1 的工人想生产第 2 阶段的零件,需要编号为 2 的工人生产第 1 阶段的零件,需要为编号 1 和 3 的工人提供原材料。
编号为 2 的工人想生产第 2 阶段的零件,需要编号为 1 和 3 的工人生产第 1 阶段的零件,他/她们都需要编号为 2 的工人提供原材料。
编号为 3 的工人想生产第 2 阶段的零件,需要编号为 2 的工人生产第 1 阶段的零件,需要编号为 1 和 3 的工人提供原材料。
样例#2:
编号为 1 的工人想生产第 1 阶段的零件,需要编号为 2 和 5 的工人提供原材料。
编号为 1 的工人想生产第 2 阶段的零件,需要编号为 2 和 5 的工人生产第 1 阶段的零件,需要编号为 1,3,4 的工人提供原材料。
编号为 1 的工人想生产第 3 阶段的零件,需要编号为 2 和 5 的工人生产第 2 阶段的零件,需要编号为 1,3,4 的工人生产第 1 阶段的零件,需要编号为 2,3,4,5 的工人提供原材料。
编号为 1 的工人想生产第 4 阶段的零件,需要编号为 2 和 5 的工人生产第 3 阶段的零件,需要编号为 1,3,4 的工人生产第 2 阶段的零件,需要编号为 2,3,4,5 的工人生产第 1 阶段的零件,需要全部工人提供原材料。
编号为 1 的工人想生产第 5 阶段的零件,需要编号为 2 和 5 的工人生产第 4 阶段的零件,需要编号为 1,3,4 的工人生产第 3 阶段的零件,需要编号为 2,3,4,5 的工人生产 第 2 阶段的零件,需要全部工人生产第 1 阶段的零件,需要全部工人提供原材料。
代码1:(40-60分算法 )
思路:
设求第3点为第3阶段时,点1是否需要提供原材料。
【3,3】 => 【2,2】,【4,2】
【2,2】 => 【1,1】,【3,1】
【4,2】 => 【3,1】,【5,1】【1,1】 => 【2,0】,【5,0】
【3,1】 => 【2,0】,【4,0】
【5,1】 => 【1,0】,【4,0】 # 此处1需要提供原材料比较容易想到对于每个询问进行暴搜,若点1为0,则Yes
时间复杂度很高,必然超时。
#include <bits/stdc++.h>
using namespace std;const int MAXN=1005;
int vex[MAXN],k,n,m,q;
struct edge {int u,v,next;
}e[MAXN*2];int vis[MAXN][MAXN];void add(int u,int v){k++;e[k].u=u;e[k].v=v;e[k].next=vex[u];vex[u]=k;
}void dfs(int u,int s){if(s==-1||vis[u][s]) return;vis[u][s]=1;for(int i=vex[u];i;i=e[i].next){int v=e[i].v;dfs(v,s-1);}return;
}int main(){cin>>n>>m>>q;while(m--){int u,v;cin>>u>>v;add(u,v);add(v,u);}while(q--){int u,L;memset(vis,0,sizeof(vis));cin>>u>>L;dfs(u,L);if(vis[1][0]) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
代码2:(满分算法)
思路:
观察发现,由于1->2的路径长度为1,只要点2的阶段为奇数,则点1一定要提供原材料(1->2->1->2->...)
观察发现,由于1->2->3的路径长度为2,只要点3的阶段为偶数,则点1一定要提供原材料
从1到v,路径很多,长度不尽相同。如果1到v的路径长度存在4时,v在阶段4、6、8、10…时,1肯定可以为0。当v的路径长度存在3时,v在3、5、7、9…阶段,1肯定可以为0。
因此要求的就是1到v的最短奇数路径和最短偶数路径。
若v的阶段为偶数x,存在v的最短偶数路径y,满足x>=y,1即可为0。
若v的阶段为奇数x,存在v的最短奇数路径y,满足x>=y,1即可为0。
设dis[v][0]为1到v的最短偶数路径,设dis[v][1]为1到v的最短奇数路径,
则有:
dis[v][0] = min(dis[v][0],dis[u][1]+1)
dis[v][1] = min(dis[v][1],dis[u][0]+1)对于初始点1,dis[1][0]显然等于0,dis[1][1]显然不可能,设为无穷大。
代码:
#include <bits/stdc++.h>
using namespace std;const int MAXN=1e5+5;
int vex[MAXN],k,n,m,q;
struct edge {int u,v,next;
} e[MAXN*2];int vis[MAXN][2],dis[MAXN][2],que[MAXN*10],q2[MAXN*10],head,rear;void add(int u,int v) {k++;e[k].u=u;e[k].v=v;e[k].next=vex[u];vex[u]=k;
}void SPFA() {for(int i=1; i<=n; i++) dis[i][0]=dis[i][1]=1e9;dis[1][0]=0;head=1;rear=0;que[++rear]=1;while(head<=rear) {int u=que[head];int t=q2[head];head++;vis[u][t]=0;for(int i=vex[u]; i; i=e[i].next) {int v=e[i].v;if(dis[v][0]>dis[u][1]+1) {dis[v][0]=dis[u][1]+1;if(!vis[v][0]) {vis[v][0]=1;que[++rear]=v;q2[rear]=0;}}if(dis[v][1]>dis[u][0]+1) {dis[v][1]=dis[u][0]+1;if(!vis[v][1]) {vis[v][1]=1;que[++rear]=v;q2[rear]=1;}}}}return;
}int main() {freopen("work.in","r",stdin);freopen("work.out","w",stdout);cin>>n>>m>>q;while(m--) {int u,v;cin>>u>>v;add(u,v);add(v,u);}SPFA();if(vex[1]==0) dis[1][0]=1e9; //补丁,若1点没有连接边,则1的偶数路径没有。while(q--) {int u,L;cin>>u>>L;if(L>=dis[u][L%2]) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
相关文章:
加工零件C++
题目: 样例解释: 样例#1: 编号为 1 的工人想生产第 1 阶段的零件,需要编号为 2 的工人提供原材料。 编号为 2 的工人想生产第 1 阶段的零件,需要编号为 1 和 3 的工人提供原材料。 编号为 3 的工人想生产第 1 阶段的零件&#x…...
Etcd 是一个分布式的键值存储系统,用于共享配置和服务发现
Etcd 是一个分布式的键值存储系统,用于共享配置和服务发现。它最初由 CoreOS 开发,并已成为许多分布式系统中的关键组件之一,特别是在 Kubernetes 中扮演着核心角色。Etcd 的设计目标是简单、可靠、安全,并且易于使用。 Etcd 的特…...
如何帮助我们改造升级原有架构——基于TDengine 平台
一、简介 TDengine 核心是一款高性能、集群开源、云原生的时序数据库(Time Series Database,TSDB),专为物联网IoT平台、工业互联网、电力、IT 运维等场景设计并优化,具有极强的弹性伸缩能力。同时它还带有内建的缓存、…...
MySQl查询分析工具 EXPLAIN ANALYZE
文章目录 EXPLAIN ANALYZE是什么Iterator 输出内容解读EXPLAIN ANALYZE和EXPLAIN FORMATTREE的区别单个 Iterator 内容解读 案例分析案例1 文件排序案例2 简单的JOIN查询 参考资料:https://hackmysql.com/book-2/ EXPLAIN ANALYZE是什么 EXPLAIN ANALYZE是MySQL8.…...
RestClientException异常
什么情况下会抛出RestClientException异常 RestClientException 异常通常在使用 Spring 的 RestTemplate 进行 RESTful API 调用时抛出。以下是一些常见的情况: 网络问题:当无法连接到目标服务器时,例如网络中断或服务器不可达。 HTTP 状态…...
poi如何实现自定义导出Excel-纵向横向合并单元格,自定义填充数据列
前情提要 首先需要明确自己需要导出的excel构成是如何的,比如我需要导出一个自定义表头的excel表格,第一行A到X是标题需要横向合并单元格,第二行和第三行是表头,A到J需要第二行和第三行纵向合并单元格,K到N的第二行需…...
6--苍穹外卖-SpringBoot项目中菜品管理 详解(二)
目录 菜品分页查询 需求分析和设计 代码开发 设计DTO类 设计VO类 Controller层 Service层接口 Service层实现类 Mapper层 功能测试 删除菜品 需求设计和分析 代码开发 Controller层 Service层接口 Service层实现类 Mapper层 功能测试 修改菜品 需求分析和设…...
游戏怎么录制?王者荣耀游戏录制指南:iOS与电脑端全面教程
在王者荣耀的战场上,每一个五杀、每一次极限逃生都可能成为你游戏生涯中的高光时刻。但这些瞬间往往转瞬即逝,如何将它们永久保存,成为你游戏历程中不可磨灭的印记呢?本文将为你揭晓答案。无论你是手持iPhone的iOS用户,…...
Vue.js组件开发指南
Vue.js组件开发指南 Vue.js 是一个渐进式的 JavaScript 框架,用于构建用户界面。它的核心是基于组件的开发模式。通过将页面分解为多个独立的、可复用的组件,开发者能够更轻松地构建复杂的应用。本文将深入探讨 Vue.js 组件开发的基础知识,并…...
【流计算】流计算概论
前言 作者在之前写过一个大数据的专栏,包含GFS、BigTable、MapReduce、HDFS、Hadoop、LSM树、HBase、Spark,专栏地址: https://blog.csdn.net/joker_zjn/category_12631789.html?fromshareblogcolumn&sharetypeblogcolumn&sharerI…...
20230819盘锦锦州葫芦岛自驾
2023年08月19日,上午带娃和老人驾车前往朝阳,逛凤凰山,中午吃了免费的素面味道不错。下午开车去鸟化石公园单独买儿童票43元。晚上驾车到盘锦,住红海滩民宿95元。 2023年08月20日,逛盘锦红海滩一天,有稻田画…...
Unity 与虚幻引擎对比:两大游戏开发引擎的优劣分析
在游戏开发领域,Unity 和虚幻引擎(Unreal Engine)是两款最为知名且广泛使用的引擎。它们各有特点,适合不同类型的开发者和项目。在这篇博客中,我们将深入探讨这两大引擎的核心功能、适用场景、优缺点,以及如…...
UDS_4_传输存储的数据功能单元
目录 一. DTC 二. 0x14服务 三. 0x19服务 3.1 0x19服务 3.2 0x01子功能 3.3 0x02子功能 3.4 0x04子功能 3.5 0x06子功能 3.6 0x0A子功能 一. DTC 》DTC-Diagnostic Trouble Code J1939-73 DTCFormat DTC SPN FMI CM OC 8-1位 8-1位 8-6位 5-1位 8位 7-1位 字节1 字节…...
第二百五十八节 JPA教程 - JPA查询选择两个实体示例
JPA教程 - JPA查询选择两个实体示例 以下JPQL从两个实体中选择。 List l em.createQuery("SELECT d, m FROM Department d, Professor m WHERE d m.department").getResultList();例子 以下代码来自Professor.java。 package cn.w3cschool.common;import java.…...
数据库三级模式结构
三级模式结构 1. 外模式(External Schema)——“用户看到的楼层”2. 概念模式(Conceptual Schema)——“图书馆的核心”3. 内模式(Internal Schema)——“图书馆的地下室”举例1. 概念模式的例子2. 外模式的…...
【小程序websocket最佳实践,有心跳和断线重连】
小程序websocket最佳实践,有心跳和断线重连 封装了WebSocketHandler类,用于管理websocket链接,保证链接的稳定和可靠,该类主要适用于小程序,但其设计思想和方法也适用于其他平台。 export default class WebSocketHa…...
自然资源部最新Nature正刊!!!
2024年8月21日,国际顶级期刊《Nature》发表了自然资源部第二海洋研究所李家彪院士为通讯作者,张涛为第一作者的论文“超慢速扩张加克洋中脊的高变化岩浆增生”。这一成果颠覆了国际海洋学术界半个多世纪以来一直认为的超慢速扩张洋中脊岩浆供给极度贫瘠的…...
git分支-创建、合并、删除
Git会将每次提交串成一条时间线,这条时间线就是一个分支。在最初,只有一个master分支 在目录下创建项目 对目录进行输入 项目被修改 创建dev分支 合并分支 删除dev分支...
Python:Spoonfed - (2-10) 激励选择脚本(搬砖)
https://www.patreon.com/posts/python-spoonfed-31572219 2019年11月15日 利用上一课的选择函数,我们现在可以拼凑出一些脚本(有一些事情我们还没有解释,但应该很容易理解)。以下代码将允许您选择当前所选对象的父对象、顶级对…...
VS Code Python 文件导入提示 xxx Module 不存在解决方式
VS Code Python 文件导入提示 xxx Module 不存在解决方式 引言正文如何打开 setting.json 文件引言 之前在 https://blog.csdn.net/u011699626/article/details/142612579?spm=1001.2014.3001.5501 一文中我们介绍了如何配置 VS code 中 Jupyter Notebook 的文件导入环境,这…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Nuxt.js 中的路由配置详解
Nuxt.js 通过其内置的路由系统简化了应用的路由配置,使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...

