2023.10.18 信息学日志
1. CF1689D Lena and Matrix
题目描述
- n ⋅ m n \cdot m n⋅m 的矩阵,求矩阵上任意一点坐标使得到矩阵上的关键点曼哈顿距离最大值最小。
- 数据范围: ∑ n ⋅ m ≤ 1 0 6 \sum n \cdot m \leq 10^6 ∑n⋅m≤106
题目概况
来源:Codeforces
洛谷难度:蓝题
CF难度: 1900 1900 1900
标签:枚举 最短距离
思路点拨
考虑每个点,只需要关注它到其他点曼哈顿距离的最大值,而实际上全局只会有 4 4 4 个点真正会影响最大值。
d i s = ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ dis = |x_1-x_2|+|y_1-y_2| dis=∣x1−x2∣+∣y1−y2∣ 将绝对值拆开分为4种情况,如下:
-
d i s = x 1 − x 2 + y 1 − y 2 dis = x_1-x_2+y_1-y_2 dis=x1−x2+y1−y2
-
d i s = x 1 − x 2 + y 2 − y 1 dis = x_1-x_2+y_2-y_1 dis=x1−x2+y2−y1
-
d i s = x 2 − x 1 + y 1 − y 2 dis = x_2-x_1+y_1-y_2 dis=x2−x1+y1−y2
-
d i s = x 2 − x 1 + y 2 − y 1 dis = x_2-x_1+y_2-y_1 dis=x2−x1+y2−y1
设定 ( x 1 , y 1 ) (x_1,y_1) (x1,y1) 为关键点,若使 d i s dis dis 最大,推广一下 ( x 2 , y 2 ) (x_2,y_2) (x2,y2) 作为四至点(地理)需要满足以下 4 4 4 点之一:
-
min ( x 2 + y 2 ) \min(x_2+y_2) min(x2+y2)
-
min ( x 2 − y 2 ) \min(x_2-y_2) min(x2−y2)
-
max ( x 2 − y 2 ) \max(x_2-y_2) max(x2−y2)
-
max ( x 2 + y 2 ) \max(x_2+y_2) max(x2+y2)
先预处理出四至点,再暴力每个点到四至点的曼哈顿距离最大值的最小值(打擂台).
预处理时间复杂度: O ( 4 ⋅ n ) O(4 \cdot n) O(4⋅n)
打擂台时间复杂度: O ( 4 ⋅ n ) O(4 \cdot n) O(4⋅n)
A C AC AC.
题目收获
将关键式分解压缩解空间。
2. CF1380D Berserk And Fireball
题目描述
CF1380D 传送门
题目概况
来源:Codeforces
洛谷难度:蓝题
CF难度: 2000 2000 2000
标签:双指针 ST表 贪心
思路点拨
-
毋庸置疑的是因为每个人的战力不同,所以通过双指针直接判定 a 、 b a、b a、b 数组是否一一对应.不对应直接 − 1 -1 −1.
-
此时 a a a 数组已经被 b b b 数组元素切成了 [ l , r ] [l,r] [l,r] 的区间,只需要考虑这样的区间该如何处理.
-
设 p = r − l + 1 p=r-l+1 p=r−l+1 以下分为 2 2 2 种情况:
- p < k p<k p<k。处理区间内最大值,若最大值大于 2 2 2 端点 b b b 数组数值,则 − 1 -1 −1 ; 否则该区间代价为 p ⋅ y p \cdot y p⋅y (y为狂暴术代价,x为火球术代价)
- k ≤ p k \leq p k≤p
- 火球术代价比狂暴术代价优
⌊ p k ⌋ ⋅ x + p m o d k ⋅ y \lfloor \frac{p}{k}\rfloor \cdot x + p \mod k \cdot y ⌊kp⌋⋅x+pmodk⋅y - 反之
x + ( p − k ) ⋅ y x+(p-k)\cdot y x+(p−k)⋅y
- 火球术代价比狂暴术代价优
-
完善, a a a 数组区间最值用 S T ST ST 表预处理维护
时间复杂度: O ( n ⋅ l o g 2 ( n ) ) O(n \cdot log2(n)) O(n⋅log2(n))
A C AC AC.
题目收获
将题目分区间缩小范围。
3. P2568 GCD
题目描述
P2568 传送门
题目概况
来源:Codeforces
洛谷难度:蓝题
标签:数论 欧拉函数 gcd \gcd gcd 前缀和
思路点拨
题目显而易见,先推一下式子。
- 原始: ∑ p ∈ p r i m e ∑ i = 1 n ∑ j = 1 n [ gcd ( i , j ) = = p ] \sum _{p∈prime}\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)==p] ∑p∈prime∑i=1n∑j=1n[gcd(i,j)==p]
- ①: ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ n p ⌋ [ gcd ( i , j ) = = 1 ] \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{p}\rfloor}[\gcd(i,j)==1] ∑p∈prime∑i=1⌊pn⌋∑j=1⌊pn⌋[gcd(i,j)==1]
- ②: ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ( ( 2 ⋅ ∑ j = 1 i [ gcd ( i . j ) = = 1 ] ) − 1 ) \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot \sum_{j=1}^{i}[\gcd(i.j)==1])-1) ∑p∈prime∑i=1⌊pn⌋((2⋅∑j=1i[gcd(i.j)==1])−1)
- ③: ∑ p ∈ p r i m e ∑ i = 1 ⌊ n p ⌋ ( ( 2 ⋅ φ ( i ) − 1 ) \sum _{p∈prime}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}((2 \cdot\varphi(i) -1) ∑p∈prime∑i=1⌊pn⌋((2⋅φ(i)−1)
- ④: ∑ p ∈ p r i m e 2 ⋅ ( ∑ i = 1 ⌊ n p ⌋ φ ( i ) ) − 1 \sum _{p∈prime}2 \cdot(\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i))-1 ∑p∈prime2⋅(∑i=1⌊pn⌋φ(i))−1
所以可以使用线性筛预处理 φ \varphi φ 函数, 在预处理 φ \varphi φ 函数的前缀和.
O ( n ) O(n) O(n)时间复杂度求解.
A C AC AC.
相关文章:
2023.10.18 信息学日志
1. CF1689D Lena and Matrix 题目描述 n ⋅ m n \cdot m n⋅m 的矩阵,求矩阵上任意一点坐标使得到矩阵上的关键点曼哈顿距离最大值最小。数据范围: ∑ n ⋅ m ≤ 1 0 6 \sum n \cdot m \leq 10^6 ∑n⋅m≤106 题目概况 来源:Codeforces …...
Modbus封装库(Com,tcp,udp一应俱全)
自行封装在用的Modbus通迅库,集成了com,tcp,udp, 做个笔记吧, 以下头文件, #pragma once #include <functional> #include <vector> #include <string> #include <memory> #ifdef LIBMODBUS_EXPORTS #define LIBMODBUS_EXPORT_…...

专访HuggingFace CTO:开源崛起、创业故事和AI民主化丨智源独家
导读 HuggingFace CTO Julien Chaumond认为,在大模型时代,AI民主化至关重要。随着大语言模型和复杂人工智能系统的崛起,持续提升AI技术的可及性有助于确保这些技术的获取和控制不集中在少数强大实体手中。技术民主化促进了机会均等࿰…...

C++常用格式化输出转换
在C语言中可以用printf以一定的格式打印字符,C当然也可以。 输入输出及命名空间还不太了解的小伙伴可以看一看C入门讲解第一篇。 在C中,可以用流操作符(stream manipulators)控制数据的输出格式,这些流操作符定义在2…...

如何使用 Loadgen 来简化 HTTP API 请求的集成测试
引言 在编写 HTTP 服务的过程中,集成测试 1 是保证程序正确性的重要一环,如下图所示,其基本的流程就是不断向服务发起请求然后校验响应的状态和数据等: 为大量的 API 和用例编写测试是一件繁琐的工作,而 Loadgen 2 正…...

软件测试面试大家是不是一问到项目就不会了?
软件测试面试中,介绍做过的项目,可以说是必不可少的一道面试题了,对于面试的同学来说,该自己发挥呢? 把项目的所有功能噼里啪啦说一遍就完事了?当然不是,我们要搞清楚,面试官问这个…...

伐木猪小游戏
欢迎来到程序小院 伐木猪 玩法:控制小猪点击屏幕左右砍树,不能碰到树枝,考验手速与眼力,记录分数,快去挑战伐木吧^^。开始游戏https://www.ormcc.com/play/gameStart/199 html <script type"text/javascript…...

0007Java安卓程序设计-ssm基于Android的校园新闻管理系统
文章目录 **摘** **要**目 录开发环境 编程技术交流、源码分享、模板分享、网课教程 🐧裙:776871563 摘 要 网络的广泛应用给生活带来了十分的便利。所以把校园新闻管理与现在网络相结合,利用java技术建设校园新闻管理系统app,实…...

git增加右键菜单
有次不小心清理系统垃圾,把git右击菜单搞没了,下面是恢复方法 将下面代码存为.reg文件,双击后导出生效,注意,你安装的git必须是默认C盘的,如果换了地方要改下面注册表文件中相关的位置 Windows Registry …...

openGauss学习笔记-117 openGauss 数据库管理-设置数据库审计-查看审计结果
文章目录 openGauss学习笔记-117 openGauss 数据库管理-设置数据库审计-查看审计结果117.1 前提条件117.2 背景信息117.3 操作步骤 openGauss学习笔记-117 openGauss 数据库管理-设置数据库审计-查看审计结果 117.1 前提条件 审计功能总开关已开启。需要审计的审计项开关已开…...
学习代码20231106
解释代码:os.environ[“OMP_NUM_THREADS“] “1“ 这行代码涉及到 Python 的 os 模块和环境变量。它的作用是设置名为 “OMPNUMTHREADS” 的环境变量的值为 “1”。让我解释一下各部分的含义: 1.os.environ: 这是 Python 中的一个字典,包含…...

turtle绘制分形树-第10届蓝桥杯省赛Python真题精选
[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和厚爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第5讲。 turtle绘制分形树&…...
【大厂招聘试题】__硬件工程师_2021年“美团”校招
目录 匹配职位:硬件工程师 1.(多选题)单处理系统中,进程P1,P2,P3处于就绪队列,进程P4,P6处于等待队列,P5正占用处理器运行,以下对接下来的运行合理的分析是( ÿ…...
算法通关村第七关|黄金挑战|迭代实现二叉树的前、中、后序遍历
1.迭代实现前序遍历 public List<Integer> preOrderTraversal(TreeNode root) {List<Integer> res new ArrayList<Integer>();if (root null) {return res;}Deque<TreeNode> stack new LinkedList<TreeNode>();TreeNode node root;while (!…...

了解高防服务器的工作原理
在当今互联网时代,网络安全问题日益突出,各种网络攻击层出不穷。为了保护企业的网络安全,高防服务器应运而生。那么,你是否了解高防服务器的工作原理呢?下面就让我们一起来探索一下。 高防服务器是一种能够有效抵御各种网络攻击的…...

AVL树性质和实现
AVL树 AVL是两名俄罗斯数学家的名字,以此纪念 与二叉搜索树的区别 AVL树在二叉搜索树的基础上增加了新的限制:需要时刻保证每个树中每个结点的左右子树高度之差的绝对值不超过1 因此,当向树中插入新结点后,即可降低树的高度&…...

出口贸易媒体发稿推广6个技巧提升品牌知名度-华媒舍
1. 出口贸易媒体介绍 出口贸易媒体是指专注于报道国际贸易、跨境业务和进出口市场的媒体平台。这些媒体对于企业发展来说至关重要,可以帮助品牌扩大影响力、提升知名度,促进商业合作。下面介绍6个出口贸易媒体发稿推广技巧,帮助企业更好地利…...

学习笔记:CANOE模拟LIN主节点和实际从节点进行通信测试
先写点感想,在LIN开发阶段,我一般用图莫斯USB工具来进行模拟主机节点发送数据。后来公司买了CANOE工具就边学习边搭建了LIN的测试工程,网上的资料真的很少,主要是靠自己一点点摸索前进,总算入门。几个月后的今天&#…...

模型可解释性
模型可解释性 前言导读Background1、为什么需要可解释性?2、诞生背景3、研究现状4、常见的模型可解释性方法4.1 基于模型自身的可解释性1)Explanation Generation2)Prototype Network 4.2 基于结果的可解释性 5、应用前景6、面临挑战 前言导读…...

Django初窥门径-自定义用户模型
前言 自定义用户模型在Django应用中是一个重要的话题,它涉及到如何根据您的项目需求以及特定的用户身份验证和授权需求来调整用户模型。在以下前言中,我将讲述为什么自定义用户模型是如此重要以及其潜在的优势: 随着Web应用的不断发展&…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...

wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...