当前位置：首页 > news >正文

题解：AT_abc245_e [ABC245E] Wrapping Chocolate

news 来源：原创 2025/7/13 10:25:52

~~我绝对不会告诉你我打比赛时没做出来这道题。~~

题目简化：给定每个巧克力和盒子的长宽，已知每个盒子只能放一块巧克力，并且必须保证巧克力能放下，求是否所有巧克力都能放入。

思路：贪心、二分、排序、STL。

首先看到这道题，最容易想到的算法就是暴力枚举。当然这是不可能的。所以时间复杂度只能是 $O(n\log_2(n))$ 或 $O (n)$ 的。

$O (n)$ 的我是没想出来，但我一看到 $log_2(n)$ ，瞬间就想到了两个东西：二分和排序。因为二分就需要排序，所以这里肯定两种都用了。

那排序我们只能排序一个量，但题目中有长宽两个变量，我们怎么排序呢？这时，我们就需要 OI 中一个很重要的思想：化二维为一维。

我们可以这么干：首先按照长排序（具体怎么排大家自己想），然后对于每一个巧克力的宽，我们在盒子中找到能包含它的，全部推入一个数组中，接着对这个数组二分找第一个能容下它的。这一步是贪心，想必大家都能想明白。

最后，如果没有能容下这块巧克力的盒子，直接输出 No 就对了。如果能装下，只需要把这个盒子弹出就行了。（这里就需要思考如何排序了。）

问题：二分需要排序，而快排是 $O(n\log_2(n))$ 的，这样一循环不就超时了吗？很简单，只需要用 multiset 就好了，它的排序是 $O(\log_2(n))$ 级别的。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct wc {int x,y;
} a[200006],b[200006];
int n,m;
inline bool cmp(wc x,wc y) {return x.x>y.x;
}
inline bool cmp1(wc x,wc y) {return x.x<y.x;
}
signed main() {cin>>n>>m;for(int i=1; i<=n; i++) {cin>>a[i].x;}for(int i=1; i<=n; i++) {cin>>a[i].y;}for(int i=1; i<=m; i++) {cin>>b[i].x;}for(int i=1; i<=m; i++) {cin>>b[i].y;}sort(a+1,a+n+1,cmp);//具体原因自己想sort(b+1,b+m+1,cmp1);multiset<int>ms;int j=m;for(int i=1; i<=n; i++) {for(; b[j].x>=a[i].x&&j>=1; j--) {ms.insert(b[j].y);}auto it=ms.lower_bound(a[i].y);if(it==ms.end()) {cout<<"No";return 0;}ms.erase(it);//弹出盒子}cout<<"Yes";return 0;
}

题解：AT_abc245_e [ABC245E] Wrapping Chocolate

我绝对不会告诉你我打比赛时没做出来这道题。题目简化：给定每个巧克力和盒子的长宽，已知每个盒子只能放一块巧克力，并且必须保证巧克力能放下，求是否所有巧克力都能放入。思路：贪心、二分、排序、STL。首先看到这…...

编程日记 2025/7/13 10:25:52

Linux 入门：操作系统进程详解（上）

目录一.冯诺依曼体系结构一）. 软件运行前为什么要先加载？程序运行之前在哪里？ 二）.理解数据流动二.操作系统OS(Operator System) 一）.概念二）.设计OS的目的三）.如何理解操作系统…...

编程日记 2025/7/12 19:05:48

文章题目：Global, regional, and national burden and trends of rheumatoid arthritis among the elderly population: an analysis based on the 2021 Global Burden of Disease study DOI：10.3389/fimmu.2025.1547763 中文标题：全球、区域…...

编程日记 2025/7/13 10:22:01

[pdf，epub]292页《分析模式》漫谈合集01-59提供下载

《分析模式》漫谈合集01-59的pdf、epub文件提供下载，地址： umlchina.com/url/ap.html，或查看本账号的CSDN资源。已排版成适合手机阅读，pdf的排版更好一些。...

编程日记 2025/7/13 9:07:56

Spring MVC的工作流程， DispatcherServlet 的工作流程

Spring MVC 是一种基于Java的模型-视图-控制器（MVC）Web框架，它通过清晰的角色划分简化了Web应用开发。下面是Spring MVC的工作流程以及DispatcherServlet的具体工作流程。 Spring MVC 工作流程请求到达：客户端发起一个HTTP请求…...

编程日记 2025/7/13 8:45:24

【Godot】使用 Shader 实现可配置圆角效果

文章目录效果预览实现原理完整Shader代码关键参数详解1. 半径参数（radius）2. 角开关参数（hide_*）数学原理圆形区域判定公式坐标映射性能优化使用示例编辑器操作代码控制进阶技巧1. 添加抗锯齿2. 外发光效果3. 动画效果常见问题解决方案问题1：圆角边缘锯齿问题2：圆形变形…...

编程日记 2025/7/13 9:07:10

【翻译、转载】MCP 提示 (Prompts)

原文地址：https://modelcontextprotocol.io/docs/concepts/prompts#python 提示 (Prompts) 创建可重用的提示模板和工作流提示 (Prompts) 使服务器能够定义可重用的提示模板和工作流，客户端可以轻松地将其呈现给用户和 LLM。它们提供了一种强大的方式来…...

编程日记 2025/7/13 8:59:13

论快乐的学习和学习的快乐

目录一、背景二、过程1.快乐的学习：理念与实践快乐学习的理念溯源快乐学习在教育实践中的体现 2.学习的快乐：内涵与价值学习的快乐的多维内涵学习的快乐对个人成长的价值 3.快乐的学习与学习的快乐的相互关系快乐的学习是学习快乐的重要前提学习的快乐是…...

编程日记 2025/7/10 10:17:33

Git 命令

参考文献： Git 教程 | 菜鸟教程Git 使用教程：最详细、最正宗手把手教学（万字长文）git忽略某个目录或文件不上传文章目录工作原理基本命令配置使用其他命令日志分支回退标签忽略指定文件远程仓库工作原理 Git 是由 Linus To…...

编程日记 2025/7/13 9:58:40

365打卡第R6周: LSTM实现糖尿病探索与预测

🍨 本文为🔗365天深度学习训练营中的学习记录博客 🍖 原作者：K同学啊 🏡 我的环境： 语言环境：Python3.10 编译器：Jupyter Lab 深度学习环境：torch2.5.1 torchvision0…...

编程日记 2025/7/13 9:27:12

新能源实验室电磁兼容设计优化方案论述

摘要：本文旨在进行新能源核心部件/系统测试实验室电磁兼容情况设计及优化方案进行论述，通过系统化梳理实验室的主流设备仪器，试验搭建典型方案。识别不同设备的电磁兼容现状，实验室基于设备布局常见设计方案不足点，故障…...

编程日记 2025/7/13 9:31:20

计算机图形学中的深度学习

文章目录零、前言0.课程考核1.课程大纲2.前置知识3.教材4.课程大纲5.相关课程 Relevant Courses 一、计算机图形学1.本章学习目标2.图形学的应用3.SIG Graph papers 二、基本图形生成算法1.本章学习目标2.图形API3.OpenGL(1)什么是OpenGL(2)OpenGL 的基本组件：顶点…...

编程日记 2025/7/13 9:01:42

RockyLinux9.3-24小时制

在 RockyLinux 9.3 中，默认时间格式为 12 小时制，调整为 24 小时制案例一：在 RockyLinux 9.3 中，默认时间格式为 12 小时制，调整为 24 小时制案例二：时间显示英文调整为中文endl 案例一：在 Roc…...

编程日记 2025/7/13 9:33:09

25.2linux中外置RTC芯片的PCF8563实验(测试)_csdn

1、硬件原理图分析知道了这些引脚我们还是按照老习惯！ 配置镜像和设备树文件！ 2、修改设备树 2.1、添加或者查找 PCF8563 所使用的 IO 的 pinmux 配置打开stm32mp15-pincrtl.dtsi 文件，查找节点I2C4: 也就是中断引脚并不需要配置pinctrl…...

编程日记 2025/7/13 10:24:17

高性能 WEB 服务器 Nginx：多虚拟主机实现！

Nginx 配置多虚拟主机实现多虚拟主机是指在一台 Nginx 服务器上配置多个网站在 Nginx 中，多虚拟主机有三种实现方式： 基于IP地址实现多虚拟主机基于端口号实现多虚拟主机基于域名实现多虚拟主机 1 基于域名实现多虚拟主机在 Nginx 中配置多个…...

编程日记 2025/7/13 10:05:35

C++ 的类型排序

0.前言在 C 中，我编写了一个 tuple-like 模板，这个模板能容纳任意多且可重复的类型： template<typename... Ts> struct TypeList {};// usage: using List1 TypeList<int, double, char, double>; using List2 TypeList<…...

编程日记 2025/7/13 9:02:33

[计算机网络]拓扑结构

拓扑结构一般会在计网教材或课程的第一章计网的分类那里接触到，但实际上计网的拓扑结构并不只是第一章提到的总线型、星型、树型、网状、混合型那几种类型那么简单，学完了后面的数链层以后对拓扑结构会有新的体会，所以特别单独总结成一篇博客…...

编程日记 2025/7/13 9:34:53

C#方法返回值全解析：从基础语法到实战技巧

摘要：方法返回值是C#编程的核心概念之一。本文将带你彻底掌握返回值声明、void方法特性，以及如何通过返回值实现优雅的流程控制（文末附完整示例代码）。返回值的基础法则类型声明原则有返回值：必须在方法名前声明…...

编程日记 2025/7/13 9:26:23

修复笔记：SkyReels-V2 项目中的 torch.cuda.amp.autocast 警告和错误

#工作记录一、问题描述在运行项目时，出现以下警告和错误： FutureWarning: torch.cuda.amp.autocast(args...) is deprecated. Please use torch.amp.autocast(cuda, args...) instead.with torch.cuda.amp.autocast(dtypepipe.transformer.dtype), …...

编程日记 2025/7/13 8:35:42

【TF-BERT】基于张量的融合BERT多模态情感分析

不足：1. 传统跨模态transformer只能处理2种模态，所以现有方法需要分阶段融合3模态，引发信息丢失。2. 直接拼接多模态特征到BERT中，缺乏动态互补机制，无法有效整合非文本模态信息改进方法：1. 基于张量的跨模…...

编程日记 2025/7/13 0:01:50

SONiC-OTN代码详解（具体内容待续）

SONiC-OTN代码详解 （具体内容待续） 基于AI的源代码解析工具的产生使得代码阅读和解析变得越来越高效和简洁，计划通过这样的工具对SONiC在OTN领域的应用做一个全自动的解析，大部分内容会基于AI工具的自动解析结果。这样做的目的是…...

编程日记 2025/7/13 8:45:23

牛客周赛90 C题- Tk的构造数组题解

原题链接 https://ac.nowcoder.com/acm/contest/107500/C 题目描述解题思路数组a是不可以动的，所以我们可以把a[i]*b[i]*i分成两组，分别为a[i]*i以及b[i] 然后策略就很明显了，让更大的b[i]匹配更大的a[i]*i 详细实现见代码。代码&am…...

编程日记 2025/7/13 9:13:09

[ML]通过50个Python案例了解深度学习和神经网络

通过50个Python案例了解深度学习和神经网络摘要：机器学习 (Machine Learning, ML)、深度学习 (Deep Learning, DL) 和神经网络 (Neural Networks, NN) 是人工智能领域的核心技术。Python 是学习和实践这些技术的首选语言，因为它提供了丰富的库（如 scikit-learn、Te…...

编程日记 2025/7/12 13:25:42

vue3 - keepAlive缓存组件

在Vue 3中，<keep-alive>组件用于缓存动态组件或路由组件的状态，避免重复渲染，提升性能。我们新建两个组件，在每一个组件里面写一个input，在默认情况下当组件切换的时候，数据会被清空，但…...

编程日记 2025/7/13 8:56:55

自由学习记录（58）

Why you were able to complete the SpringBoot MyBatisPlus task smoothly: Clear logic flow: Database → Entity → Service → Controller → API → JSON response. Errors are explicit, results are verifiable — you know what’s broken and what’s fixed. Sta…...

编程日记 2025/7/13 10:16:30

短信侠 - 自建手机短信转发到电脑上并无感识别复制验证码，和找手机输验证码说再见！

自建手机短信转发到电脑上并无感识别复制验证码一、前言项目开发语言：本项目使用PythonRedisC#开发你是否也遇到过这样的场景： 正在电脑上操作某个网站，需要输入短信验证码手机不在身边，或者在打字时来回切换设备很麻烦验证码…...

编程日记 2025/7/13 9:52:56

课程10. 聚类问题

课程10. 聚类问题聚类此类表述的难点K 均值法让我们推广到几个集群的情况如果我们选择其他起始近似值会怎样？ 结论在 sklearn 中的实现如何处理已发现的问题？层次聚类Lance-Williams 算法Lance-Williams 公式在Scipy中实现示例DBSCANDBSCAN 算法聚类…...

编程日记 2025/7/13 9:00:56

深度学习中的数据增强：提升食物图像分类模型性能的关键策略

深度学习中的数据增强：提升食物图像分类模型性能的关键策略在深度学习领域，数据是模型训练的基石，数据的数量和质量直接影响着模型的性能表现。然而，在实际项目中，获取大量高质量的数据往往面临诸多困难，…...

编程日记 2025/7/13 9:04:47

QT设计权限管理系统

Qt能够简单实现系统的权限设计首先我们需要一个登陆界面例如这样然后一级权限，可以看到所有的内容，不设置菜单栏的隐藏。然后其他权限，根据登陆者的身份进行菜单栏不同的展示。菜单栏的隐藏代码如下： ui->actionuser-…...

编程日记 2025/7/13 9:50:07

从上帝视角看文件操作

1.为什么使用文件？如果没有文件，我们写的程序中的数据是存储在电脑的内存中，当程序退出时，内存被回收后，数据就丢失了，等下次运行程序，是无法看到上次程序的数据的。(比如我们在程序中写通讯录时，联系人的相关数据都是放在内存中的，当程序退出时，这些数据也会随之消…...

编程日记 2025/7/13 9:31:20

【51单片机6位数码管显示时间与秒表】2022-5-8

缘由数码管 keil proteus 为什么出现这种情况呢？-编程语言-CSDN问答 #include "reg52.h" unsigned char code smgduan[]{0x3f,0x06,0x5b,0x4f,0x66,0x6d,0x7d,0x07,0x7f,0x6f,0x77,0x7c,0x39,0x5e,0x79,0x71,0,64}; //共阴0~F消隐减号 unsigned char cod…...

编程日记 2025/7/13 9:27:52

从头训练小模型: 4 lora 微调

1. LoRA (Low-Rank Adaptation) LoRA是一种高效的参数高效微调（Parameter-Efficient Fine-Tuning, PEFT）方法，原理是通过低秩分解的方式对预训练模型进行微调。相比于全参数微调（Full Fine-Tuning），LoRA…...

编程日记 2025/7/13 9:07:55

前端开发，文件在镜像服务器上不存在问题：Downloading binary from...Cannot download...

问题与处理策略问题描述在 Vue 项目中，执行 npm i 下载依赖时，报如下错误 Downloading binary from https://npm.taobao.org/mirrors/node-sass//v4.14.1/win32-x64-72_binding.node Cannot download "https://npm.taobao.org/mirrors/node-sa…...

编程日记 2025/7/13 9:14:44

Debezium Binlog协议与事件转换详解

Debezium Binlog协议与事件转换详解 1. MySQL Binlog通信机制 1.1 连接建立流程 #mermaid-svg-eE88YFqcTG9kUWaZ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-eE88YFqcTG9kUWaZ .error-icon{fill:#552222;}#mer…...

编程日记 2025/7/13 9:38:46

【PostgreSQL数据分析实战：从数据清洗到可视化全流程】4.1 日期时间标准化（时区转换/格式统一）

👉 点击关注不迷路 👉 点击关注不迷路 👉 点击关注不迷路文章大纲 PostgreSQL数据分析实战：数据清洗之日期时间标准化（时区转换/格式统一）4.1 日期时间标准化：从混乱到有序4.1.1 数据乱象&…...

编程日记 2025/7/13 9:43:22

基于Hive + Spark离线数仓大数据实战项目（视频+课件+代码+资料+笔记）

精品推荐：基于Hive Spark离线数仓大数据实战项目，共23节课，供学习参考。项目介绍项目中 docker 使用项目环境搭建项目数仓分层项目业务分析sqoop 数据采集python 数据采集项目 ODS 层创建DWD 层构建DWS 层构建项目回顾（一&…...

编程日记 2025/7/13 8:39:25

【深入浅出MySQL】之数据类型介绍

【深入浅出MySQL】之数据类型介绍 MySQL中常见的数据类型一览为什么需要如此多的数据类型数值类型BIT（M）类型INT类型TINYINT类型BIGINT类型浮点数类型float类型DECIMAL(M,D)类型区别总结字符串类型CHAR类型VARCHAR(M)类型日期和时间类型enum和set类型 …...

编程日记 2025/7/13 9:24:55

从入门到登峰-嵌入式Tracker定位算法全景之旅 Part 4 ｜IMU 死算与校正：惯性导航在资源受限环境的落地

Part 4 ｜IMU 死算与校正：惯性导航在资源受限环境的落地本章聚焦 ESP32-S3 平台上如何利用 LSM6DS3 IMU 实现死算(Dead Reckoning)，并结合零速更新(ZUPT) 或磁力计辅助进行漂移校正，最终通过 EKF/UKF 融合提升定位精度。一、传感器简介与校准 LSM6DS3 主要参数加速…...

编程日记 2025/7/13 9:48:23

【iOS】方法交换

【iOS】方法交换 method-swizzling 文章目录【iOS】方法交换 method-swizzling前言什么是method-swizzling相关API方法交换的风险在load方法中保证只加载一次要在当前类的方法中进行交换如果方法依赖于cmd 方法交换的应用前言之前看过有关于消息转发的内容,这里我们可以简…...

编程日记 2025/7/13 9:43:22

PostgreSQL 的 ANALYZE 命令

PostgreSQL 的 ANALYZE 命令 ANALYZE 是 PostgreSQL 中用于收集数据库对象统计信息的关键命令，这些统计信息对于查询优化器生成高效执行计划至关重要。一 ANALYZE 命令 1.1 基本语法 ANALYZE [ ( option [, ...] ) ] [ table_and_columns [, ...] ] ANALYZE [ …...

编程日记 2025/7/13 9:24:14

初识 iOS 开发中的证书固定

引言在移动应用安全领域，HTTPS/TLS 是数据传输的第一道防线，但仅依赖系统默认的证书验证仍有被中间人（MITM）攻击的风险。Certificate Pinning（证书固定）通过将客户端信任“钉”在指定的服务器证书或公钥上…...

编程日记 2025/7/13 8:55:23

2025 年如何使用 Pycharm、Vscode 进行树莓派 Respberry Pi Pico 编程开发详细教程（更新中）

micropython 概述 micropython 官方网站：https://www.micropython.org/ 安装 Micropython 支持固件树莓派 Pico 安装 Micropython 支持固件下载地址：https://www.raspberrypi.com/documentation/microcontrollers/ 选择 MicroPython 下载 RPI_PIC…...

编程日记 2025/7/13 9:53:40

设计模式每日硬核训练 Day 17：中介者模式（Mediator Pattern）完整讲解与实战应用

🔄 回顾 Day 16：责任链模式小结在 Day 16 中，我们学习了责任链模式（Chain of Responsibility Pattern）： 将请求沿链传递，节点可选择处理或传递下一节点。实现了请求发送者与多个处理者的解耦…...

编程日记 2025/7/13 8:43:50

文章记单词 | 第63篇（六级）

一，单词释义 vegetable [ˈvedʒtəbl] n. 蔬菜；植物人；生活单调乏味的人；adj. 蔬菜的；植物的faint [feɪnt] adj. 模糊的；微弱的；虚弱的；v. 昏倒，昏厥；n. 昏…...

编程日记 2025/7/13 9:19:26

ES类的索引轮换

通过以下请求方法创建一个名为 “tiered-storage-policy” 的 ISM policy： PUT _plugins/_ism/policies/tiered-storage-policy {"policy": {"description": "Changes replica count and deletes.","schema_version": 1,…...

编程日记 2025/6/29 5:41:19

小白机器人假想：分布式关节控制——机器人运动的未来模式？

引言在机器人技术快速发展的今天，控制架构的创新往往能带来突破性进展。作为一名机器人爱好者，我最近思考了一个大胆的设想：如果机器人的每个关节都配备独立的动作存储器和处理器，并通过高速光纤网络与中央"驱动总脑"…...

编程日记 2025/6/29 6:34:03

LangChain4j +DeepSeek大模型应用开发——9 优化硅谷小鹿

1.预约业务的实现这部分我们实现硅谷小鹿的查询订单、预约订单、取消订单的功能创建MySQL数据库表 CREATE DATABASE xiaolu; USE xiaolu; -- 创建预约表 appointment CREATE TABLE appointment (id BIGINT NOT NULL AUTO_INCREMENT COMMENT 主键ID，自增, -- 主…...

编程日记 2025/6/29 5:10:14

Oracle VirtualBox 在 macOS 上的详细安装步骤

Oracle VirtualBox 在 macOS 上的详细安装步骤一、准备工作1. 系统要求2. 下载安装包二、安装 VirtualBox1. 挂载安装镜像2. 运行安装程序3. 处理安全限制（仅限首次安装）三、安装扩展包（增强功能）四、配置第一个虚拟机1. 创建新虚拟机2. 分配内存3. 创建虚拟硬盘4. 加载系…...

编程日记 2025/6/29 6:36:05

Day110 | 灵神 | 二叉树 | 根到叶路径上的不足节点

Day110 | 灵神 | 二叉树 | 根到叶路径上的不足节点 1080.根到叶路径上的不足节点 1080. 根到叶路径上的不足节点 - 力扣（LeetCode） 思路： 笔者一开始没看懂，只能通过部分的例子，原因是把路径和小于limit的都给删了…...

编程日记 2025/6/29 5:51:04

超详细讲解C语言转义字符\a \b \r \t \? \n等等

转义字符 C语言有一组字符很特殊，叫做转义字符，顾名思义，改变原来的意思的字符。 1 \? ??)是一个三字母词，在以前的编译器它会被编译为] (??会被编译为[ 因此在以前输入(are you ok ??)就会被编译为are you ok ] 解决这个…...

编程日记 2025/7/12 21:02:05

相关文章：