[acwing周赛复盘] 第 94 场周赛20230311

news/2024/2/29 3:28:23

[acwing周赛复盘] 第 94 场周赛20230311

    • 一、本周周赛总结
    • 二、 4870. 装物品
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 三、4871. 最早时刻
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 四、4872. 最短路之和
      • 1. 题目描述
      • 2. 思路分析
      • 3. 代码实现
    • 六、参考链接

一、本周周赛总结

  • 又是笨比的一周,只做出1题。
  • T1 数学
  • T2 单源最短路dijikstra
  • T3 多源最短路floyd
  • 在这里插入图片描述

二、 4870. 装物品

链接: 4870. 装物品

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 所有人都应该知道上取整公式:
  • ceil(a/b) = (a+b-1)//b

3. 代码实现

import sys
import bisectRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')#       ms
def solve():x, = RI()print((x+5-1)//5)if __name__ == '__main__':solve()

三、4871. 最早时刻

链接: 4871. 最早时刻

1. 题目描述

在这里插入图片描述

2. 思路分析

脑子木了,一直在想二分怎么不对;而且还写错变量名。。
  • 是个比较显然的dijkstra,但是多了个限制条件,有的时间点不能出发。
  • 那么可以提前预处理出每个节点位置,所有不能走的时间点,它最早能走的时间。
    • 这里一个倒序dp即可。最后一个时间点能走的时间显然是b[-1]+1.
    • 向前遍历,如果b[i]后边的数不是b[i]+1,则它在b[i]+1能走;否则就是更后边最近的那个能走的时间点。
  • 那么转移的时候出发时间转换一下即可。

  • 注意dijkstra每个节点只会访问一次,要记得写if d>vis[d]:continue因此其实b可以不预处理,直接暴力。

3. 代码实现

# Problem: 最早时刻
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4874/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
from heapq import *
from math import infRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')#    4330   ms
def solve():n, m = RI()g = [[] for _ in range(n)]for _ in range(m):u, v, w = RI()u -= 1v -= 1g[u].append((v, w))g[v].append((u, w))gogo = []for _ in range(n):_, *b = RI()can = {}if b:go = b[-1] + 1can[b[-1]] = gofor i in range(len(b) - 2, -1, -1):if b[i] + 1 != b[i + 1]:go = b[i] + 1can[b[i]] = gogogo.append(can)vis = [inf] * nvis[0] = 0h = [(0, 0)]while h:d, u = heappop(h)if u == n - 1:return print(d)if d > vis[u]:continue  # 巨量优化记得写ban = gogo[u]go = ban.get(d, d)for v, w in g[u]:nd = go + wif vis[v] > nd:vis[v] = ndheappush(h, (nd, v))# if n - 1 in vis:#     return print(vis[n - 1])print(-1)if __name__ == '__main__':solve()

四、4872. 最短路之和

链接: 4872. 最短路之和

1. 题目描述

在这里插入图片描述

2. 思路分析

傻了,想到了floyd,但没做出来。赛后写了2个代码。都应该掌握。
  • 显然这题是个倒序做的题,把x从后一直加到集合里计算即可。

  • 方法1,直观且短。把x作为k(去松弛别人的节点),去遍历松弛。
  • 由于在floyd里,k是最外层的节点,因此这么做完后,k的影响已经结束了,则可以更新当前答案。
  • 实现时,松弛的话是u,v都是全部节点;计算答案只计算已添加的节点。

  • 方法2,助于理解floyd。
  • 依然倒序把x作为k,但是分别计算三种最短路:k到所有已访问的u、所有u到k、所有已访问的u到v。
  • 这里注意计算顺序,由于u->v是已经计算完的最短路,所以必须用它们先去更新k相关的最短路,再返回来计算新的u->v。

3. 代码实现

# Problem: 最短路之和/*-/*-/*-/*-
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4875/
# Memory Limit: 256 MB
# Time Limit: 3000 msimport sysRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')MOD = 10 ** 9 + 7
PROBLEM = """
"""#     6995  ms
def solve():n, = RI()d = []for _ in range(n):d.append(RILST())xs = RILST()ans = []ps = []for x in xs[::-1]:k = x - 1# 注意 上两个循环可以合并(顺序随意),但这个循环必须在最后,否则会wa# 前提是所有其它点到k的最短路(即所有uk/kv)求出来,才可以用k来松弛uv的边。for u in range(n):for v in range(n):d[u][v] = min(d[u][v], d[u][k] + d[k][v])ps.append(k)a = 0for u in ps:for v in ps:a += d[u][v]ans.append(a)print(*(ans[::-1]))#     10039   ms
def solve1():n, = RI()d = []for _ in range(n):d.append(RILST())xs = RILST()ans = []ps = []for x in xs[::-1]:k = x - 1a = 0# 尝试用所有v松弛uk,这里uv已经是最短路,所以可以松弛for u in ps:for v in ps:d[u][k] = min(d[u][k], d[u][v] + d[v][k])a += d[u][k]# 尝试用所有v松弛ku,这里uv已经是最短路,所以可以松弛for u in ps:for v in ps:d[k][u] = min(d[k][u], d[k][v] + d[v][u])a += d[k][u]# 注意 上两个循环可以合并(顺序随意),但这个循环必须在最后,否则会wa# 前提是所有其它点到k的最短路(即所有uk/kv)求出来,才可以用k来松弛uv的边。for u in ps:for v in ps:d[u][v] = min(d[u][v], d[u][k] + d[k][v])a += d[u][v]ps.append(k)ans.append(a)print(*(ans[::-1]))if __name__ == '__main__':solve()

六、参考链接


http://www.ppmy.cn/news/31866.html

相关文章

Tomcat安装及启动

日升时奋斗,日落时自省 目录 1、Tomcat下载 2、JDK安装及配置环境 3、Tomcat配置环境 4、启动Tomcat 5、部署演示 1、Tomcat下载 直接入主题,下载Tomcat 首先就是别下错了,直接找官方如何看是不是广告,或者造假 搜索Tomc…

结构体内存大小

000、前言 要想计算结构体内存大小,就会涉及到一个结构体内存对齐的问题,而不是对其成员进行简单的加运算 (1)在写本博客之前 有位同学和我讨论了一个学校的题目,题目如下: 我借这道题目问了另外一位同…

MyBatis操作数据库

目录 MyBatis 功能架构 学习MyBatis 第一个MyBatis查询 1、创建数据库和表 2、搭建MyBatis开发环境 2.1、在项目中添加MyBatis框架 2.2、配置数据库连接信息 2.3、配置MyBatis中xml的保存路径(规则) 3、添加业务代码 3.1、创建实体类 3.2、构…

Web前端开发--自用

第一章 1.1 时间:1980 人物:Tim Berners-Lee 地点:欧洲核子研究组织中最大的欧洲核子物理实验室 事件:与Robert Cailliau建立ENQUIRE系统 1984年,世界上第一个客户端浏览器(World Wide Web)和第…

Qt读xml文件

QXmlStreamReaderQXmlStreamReader类通过简单的流式API为我们提供了一种快速的读取xml文件的方式。他比Qt自己使用的SAX解析方式还要快。所谓的流式读取即将一个xml文档读取成一系列标记的流,类似于SAX。而QXmlStreamReader类和SAX的主要区别就是解析这些标记的方式…

Go打包附件内容到执行文件

前言 如果我们的应用在启动的时候需要对数据库进行初始化(比如建表等), 可以通过读取.sql文件内容直接执行. 但是, 这样会带出一个问题: 在发送可执行文件的时候, 需要连带着附件文件, 并且相对路径还不能出错. 这样太麻烦了有时我们并不希望附件的内容被使用者看到 处于种种…

为什么程序员喜欢这些键盘?

文章目录程序员的爱介绍个人体验程序员的爱 程序员是长时间使用计算机的群体,他们需要一款高品质的键盘来保证舒适的打字体验和提高工作效率。在键盘市场上,有很多不同类型的键盘,但是对于程序员来说,机械键盘是他们最钟爱的选择…

c# 源生成器

本文概述了 .NET Compiler Platform(“Roslyn”)SDK 附带的源生成器。 通过源生成器,C# 开发人员可以在编译用户代码时检查用户代码。 生成器可以动态创建新的 C# 源文件,这些文件将添加到用户的编译中。 这样,代码可以…

深度学习训练营之yolov5训练自己的数据集

深度学习训练营之训练自己的数据集原文链接环境介绍准备好数据集划分数据集运行voc_train.py遇到问题完整代码创建new_data.yaml文件模型训练时遇到的报错模型训练结果可视化参考链接原文链接 🍨 本文为🔗365天深度学习训练营 中的学习记录博客&#x1f…

Win11的两个实用技巧系列之无法联网怎么办、耳机没声音的多种解决办法

Win11无法联网怎么办? win11安装后设备不能上网的解决办法Win11无法联网怎么办?电脑安装win11系统以后,发现不能上网,连接不上网络,该怎么办呢?下面我们就来看看win11安装后设备不能上网的解决办法Win11安装后&#x…

Python连接es笔记三之es更新操作

这一篇笔记介绍如何使用 Python 对数据进行更新操作。 对于 es 的更新的操作,不用到 Search() 方法,而是直接使用 es 的连接加上相应的函数来操作,本篇笔记目录如下: 获取连接update()update_by_query()批量更新UpdateByQuery()…

ESD静电保护器件分类简介及场景应用

文章目录 1. ESD介绍1.1 ESD简介1.2 ESD产生原理1.3 ESD危害2. 器件级ESD模型2.1 人体模型(HBM)2.2 机器模型(MM)2.3 带电器件模型(CDM)3. 系统级ESD模型3.1 介绍3.2 防护器件分类简介3.2.1 TVS二极管3.2.2 MLCC陶瓷电容3.2.3 ESD抑制管3.2.4 MOV压敏电阻3.2.5 比较4. ES…

【论文阅读】注意力机制与二维 TSP 问题

前置知识 注意力机制 见 这篇 二维 TSP 问题 给定二维平面上 nnn 个点的坐标 S{xi}i1nS\{x_i\}_{i1}^nS{xi​}i1n​,其中 xi∈[0,1]2x_i\in [0,1]^2xi​∈[0,1]2,要找到一个 1∼n1\sim n1∼n 的排列 π\piπ ,使得目标函数 L(π∣s)∥xπ…

第一章:命题与命题公式

1.命题与命题联结词 1.命题与命题的表示 1. 命题 由一个或几个已知的前提,推导出来一个未知的结论的思维过程称为推理,推理的基本要素就是表达这些前提的一些陈述句,可以将这些陈述句理解为命题。 (1)地球是行星 (2)8不是素数 (3)1 + 2 = 22. 命题真值 一个陈述句不…

时间复杂度和空间复杂度的计算

目录 算法的复杂度 时间复杂的的概念 时间复杂度计算方法 大O的渐进表示法 空间复杂的概念 空间复杂的的计算方法 时间和空间复杂度的应用 消失的数字 轮转数组 算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存&…

数据结构-用栈实现队列

前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int…

Qt实用技巧:Qt中浮点数的相等比较方式(包括单精度和双精度)

若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/129464152 红胖子(红模仿)的博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软…

23种设计模式-建造者模式(Android应用场景介绍)

什么是建造者模式 建造者模式是一种创建型设计模式,它允许您使用相同的创建过程来生成不同类型和表示的对象。在本文中,我们将深入探讨建造者模式的Java实现,并通过一个例子来解释其工作原理。我们还将探讨如何在Android应用程序中使用建造者…

九龙证券|直逼1.5万亿!A股融资余额创年内新高,青睐这些行业和个股

2023年以来,A股商场震动重复,商场走势整体先扬后抑,各路资金看法纷歧,但数据显现,融资客在此期间整体持续净买入,未受到商场动摇的明显冲击,融资余额日前已迫临1.5万亿元,创出年内新…

Java Web 实战 07 - 多线程基础之单例模式

大家好 , 这篇文章给大家带来的是单例模式 , 单例模式中分为懒汉模式和饿汉模式 , 懒汉模式是需要用的到的时候才去创建实例 , 而饿汉模式是程序一启动就立刻创建实例 , 在这其中还有很多其他问题需要我们去研究 推荐大家跳转到这里 , 观看效果更加 上一篇文章的链接我也贴在这…
最新文章