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

ABC393E/F简要题解

news 来源：原创 2025/5/9 13:33:53

ABC393E

给定数组 $A$ ,求包含元素 $A_i$ 的大小为 $k$ 的子集中最大的最大公约数。

题解：

首先思考对于整个数组所有包含 $k$ 个元素的子集中最大的GCD是多少，可以怎么求。

我们发现，如果一个数 $x$ ,数组中如果存在至少 $k$ 个数是它的倍数，那么我们一定可以找到一个大小为 $k$ 的子集，使得 $x$ 是这个集合的公约数。

因为总的值域比较小，所以我们可以使用一个桶统计所有数字的出现次数，然后使用调和级数枚举的方式求出对于每个数 $i$ ,数组当中有多少数是它的倍数。

如果一个数 $i$ ，满足它的倍数个数在数组 $A$ 中的出现次数大于 $k$ ，那么对于所有 $i$ 的倍数，我们一定都能找到一个大小为 $k$ 的集合使得公约数是 $i$ 。所以我们可以维护一个ans数组， $ans_i$ 表示如果选择了一个值为 $i$ 的数，最大的答案是多少。对于所有的 $A_i$ ，直接输出对应的ans即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,k;
int a[2000005];
int cnt[1000005];
int sum[1000005];
int ans[2000005];
void solve(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];cnt[a[i]]++;}for(int i=1;i<=1e6;i++){for(int j=i;j<=1e6;j+=i){sum[i]+=cnt[j];}}for(int i=1;i<=1e6;i++){if(sum[i]>=k)for(int j=i;j<=1e6;j+=i){ans[j]=max(ans[j],i);//ans[j]=i;}}for(int i=1;i<=n;i++){cout<<ans[a[i]]<<endl;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

ABC393F

给定数组 $A$ , $q$ 次询问前缀 $r_i$ 中所有小于 $x_i$ 的数组成的最长上升子序列是多少。

考虑二分栈求最长上升子序列做法，栈中元素表示对应LCS为 $i$ 时最后一个数字的最小值，所以我们可以直接将所有询问离线之后在对应的栈上二分找到答案即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
int n,q;
int a[200005];
vector<pii>ask[200005];
void solve(){cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=q;i++){int x,y;cin>>x>>y;ask[x].push_back({y,i});}vector<int>st(1,0);vector<int>ans(q+1,0);for(int i=1;i<=n;i++){int l=0,r=st.size()-1;while(l<=r){int mid=l+r>>1;if(st[mid]<a[i])l=mid+1;else r=mid-1;}if(l==st.size())st.push_back(a[i]);else st[l]=a[i];// cout<<i<<" "<<l<<"??\n";for(auto [y,id]:ask[i]){l=0,r=st.size()-1;while(l<=r){int mid=l+r>>1;if(st[mid]<=y)l=mid+1;else r=mid-1;}ans[id]=r;}}for(int i=1;i<=q;i++)cout<<ans[i]<<endl;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

ABC393E/F简要题解

ABC393E 给定数组 A A A,求包含元素 A i A_i Ai的大小为 k k k的子集中最大的最大公约数。题解： 首先思考对于整个数组所有包含 k k k个元素的子集中最大的GCD是多少，可以怎么求。我们发现，如果一个数 x x x,数组中如果存在至少 k k …...

编程日记 2025/5/9 13:33:53

什么是Mustache

Mustache 是一种轻量级模板引擎，用于将变量插入到模板中生成最终的文本输出。它的设计简单且易于使用，适用于多种编程语言，包括 JavaScript、Python、Ruby、Java 等。 Mustache 的模板语法使用双大括号 {{}} 包裹变量或表达式，用…...

编程日记 2025/5/9 12:08:42

GGUF格式的DeepSeek-R1-Distill-Qwen-1.5B模型的字段解析

在将GGUF文件转换为PyTorch格式之前，先要读取文件并了解模型中都有什么字段，会遇到了各种参数不匹配的问题。现在，我们先读取GGUF文件的元数据字段，并希望将这些字段中的内存映射（mmap）数据转换为字符串显示…...

编程日记 2025/5/9 12:33:30

Java和SQL测试、性能监控中常用工具

下面我会详细列举一些在Java和SQL测试、调试、性能监控中常用的工具，并结合项目中提到的各个技术点说明如何选择合适的工具和方法。一、Java项目常用的测试、调试与性能监控工具单元测试与集成测试： JUnit/TestNG： 用于编写单元测试和集成测…...

编程日记 2025/5/9 13:32:51

CAS单点登录（第7版）13.票务

如有疑问，请看视频：CAS单点登录（第7版） 票务概述票务有两个核心的可配置工单组件： TicketRegistry - 提供持久票证存储。ExpirationPolicy - 提供票证过期语义的策略框架。工单注册部署环境和技术专业知识…...

编程日记 2025/5/9 13:15:03

大语言模型入门 1 大语言模型步骤1.1 pre-training 预训练1.1.1 从网上爬数据1.1.2 tokenization1.1.2.1 tokenization using byte pair encoding 1.3 预训练1.3.1 context1.3.2 training1.3.3 输出 1.2 post-training1.2.1 token 1.2 SFT监督微调1.3 人类反馈强化学习1.3.1 人…...

编程日记 2025/5/9 13:01:24

从ARM官方获取自己想要的gcc交叉编译工具链接(Arm GNU Toolchain),并在Ubuntu系统中进行配置

前言本文是博文 https://blog.csdn.net/wenhao_ir/article/details/145547974 的分支博文。在本博文中我们完成gcc交叉编译工具gcc-arm-9.2-2019.12-x86_64-arm-none-linux-gnueabihf.tar.xz的下载、配置、测试。下载自己想要的gcc交叉编译工具的源码目标文件的名字及说…...

编程日记 2025/5/9 12:28:26

LDR6500：重塑充电与数据传输的新篇章

在当今快速发展的数字时代，电子设备对充电速度、数据传输效率和兼容性提出了更高要求。LDR6500，作为一款专为USB Type-C Bridge设备设计的USB-C DRP（Dual Role Port，双角色端口）接口USB PD（Power Delivery&…...

编程日记 2025/5/9 12:24:19

Matlab 机器人雅可比矩阵

工业机器人运动学与Matlab正逆解算法学习笔记（用心总结一文全会）（四）——雅可比矩阵_staubli机器人正逆向运动学实例验证matlab-CSDN博客 matlab求雅可比矩阵_六轴机械臂矢量积法求解雅可比矩阵-CSDN博客 (63 封私信 / 80 条消息…...

编程日记 2025/5/9 13:27:42

网络安全防护：开源WAF雷池SafeLine本地部署与配置全流程

文章目录前言1.关于SafeLine2.安装Docker3.本地部署SafeLine4.使用SafeLine5.cpolar内网穿透工具安装6.创建远程连接公网地址7.固定Uptime Kuma公网地址前言对于建站新手来说，无论你选择创建的是个人博客、企业官网还是各类应用平台来推广自己的内容或是产品&am…...

编程日记 2025/5/9 12:13:50

vue框架生命周期详细解析

Vue.js 的生命周期钩子函数是理解 Vue 组件行为的关键。每个 Vue 实例在创建、更新和销毁过程中都会经历一系列的生命周期阶段，每个阶段都有对应的钩子函数，开发者可以在这些钩子函数中执行特定的操作。 Vue 生命周期概述 Vue 的生命周期可以分为以下几…...

编程日记 2025/5/9 9:17:14

Ollama 安装使用指南

rootdeepseek-1:/home/zgq/.ollama# lsof -i :11434 COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME ollama 29005 root 3u IPv4 47359 0t0 TCP localhost:11434 (LISTEN) 从以上提供的 lsof 输出来看，Ollama 服务正在监听 localhost:11434…...

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

力扣 38. 外观数列打表迭代阅读理解

Problem: 38. 外观数列 🧑‍🏫 参考题目补充说明 🧑‍🏫 参考题解迭代法 class Solution {public String countAndSay(int n) {String str "1";for (int i 2; i < n; i) {StringBuilder sb new StringBuild…...

编程日记 2025/5/9 13:24:28

文心一言4月起全面免费，6月底开源新模型：AI竞争进入新阶段？

名人说：莫听穿林打叶声，何妨吟啸且徐行。—— 苏轼 Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊） 目录一、文心一言免费化的背后：AI成本与应用的双重驱动1️⃣成本下降，推动文心一言普及2…...

编程日记 2025/5/9 12:01:25

基于LSTM+前向均值滤波后处理的癫痫发作检测(包含数据集)

引言癫痫是一种常见的神经系统疾病，患者会经历反复的癫痫发作。早期检测和预警对于改善患者的生活质量至关重要。近年来，深度学习技术，尤其是长短期记忆网络（LSTM），在时间序列数据分析中表现出色&#xf…...

编程日记 2025/5/9 13:02:30

Window下Redis的安装和部署详细图文教程（Redis的安装和可视化工具的使用）

文章目录 Redis下载地址：一、zip压缩包方式下载安装 1、下载Redis压缩包2、解压到文件夹3、启动Redis服务4、打开Redis客户端进行连接5、使用一些基础操作来测试二、msi安装包方式下载安装 1、下载Redis安装包2、进行安装3、进行配置4、启动服务5、测试能否正常工…...

编程日记 2025/5/3 11:25:59

什么是交叉熵

交叉熵定义公式针对离散变量x的概率分布 p ( x ) p(x) p(x) , q ( x ) q(x) q(x) x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4… x n x_n xnp( x 1 x_1 x1)p( x 2 x_2 x2)p( x 3 x_3 x3)p( x 4 x_4 x4)…p( x n x_n xn)q( x 1 x_1 x1)q( x 2 x_2 …...

编程日记 2025/5/6 8:24:52

虚拟机安装k8s集群

环境准备 - 主节点（Master Node）: IP地址: 192.168.40.100主机名: k8s-master - 工作节点（Worker Node）: IP地址: 192.168.40.101主机名: k8s-node1 步骤 1: 配置虚拟机环境 1.1 设置主机名在每台虚拟机上设置唯一的主机名…...

编程日记 2025/5/9 12:36:40

【mysql部署】在ubuntu22.04上安装和配置mysql教程

一.安装mysql 1. 更新软件包列表: sudo apt-get update2.安装 MySQL 服务器： sudo apt-get install mysql-server3.设置 MySQL 安全性： sudo mysql_secure_installation按照提示输入相关问题的回答，例如删除匿名用户、禁止 root 远程登录…...

编程日记 2025/5/9 12:50:57

机器学习实战(3)：线性回归——预测连续变量

第3集：线性回归——预测连续变量在机器学习的世界中，线性回归是最基础、最直观的算法之一。它用于解决回归问题，即预测连续变量（如房价、销售额等）。尽管简单，但线性回归却是许多复杂模型的基石。今天我们…...

编程日记 2025/5/8 3:12:33

烧结银在 DeepSeek 中的关键作用与应用前景

烧结银在 DeepSeek 中的关键作用与应用前景在科技飞速发展的当下，DeepSeek 作为前沿科技领域的重要参与者，正以其独特的技术和创新的应用，在众多行业掀起变革的浪潮。而在 DeepSeek 的核心技术体系中，烧结银这一材料的应用&#…...

编程日记 2025/5/9 13:00:22

C++效率掌握之STL库：string底层剖析

文章目录 1.学习string底层的必要性2.string类对象基本函数实现3.string类对象的遍历4.string类对象的扩容追加5.string类对象的插入、删除6.string类对象的查找、提取、大小调整7.string类对象的流输出、流提取希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力…...

编程日记 2025/5/9 12:19:03

计算机组成原理—— 总线系统（十一）

在追求梦想的旅途中，我们常常会遇到崎岖的道路和难以预料的风暴。然而，正是这些挑战塑造了我们的坚韧和毅力，使我们能够超越自我，触及那些看似遥不可及的目标。不要因为一时的困境而气馁，也不要因为他人的质疑而动摇自…...

编程日记 2025/5/9 12:02:25

电子制造企业数字化转型实战：基于Odoo构建MES平台的深度解决方案

作者背景拥有8年乙方项目经理经验、8年甲方信息化管理经验，主导过12个Odoo制造业项目落地，服务客户涵盖消费电子、汽车电子、工业设备等领域。本文基于华东某电子企业（以下简称"A公司"）的实战案例，解析行业…...

编程日记 2025/5/8 17:14:57

【Python爬虫(4)】揭开Python爬虫的神秘面纱：基础概念全解析

【Python爬虫】专栏简介：本专栏是 Python 爬虫领域的集大成之作，共 100 章节。从 Python 基础语法、爬虫入门知识讲起，深入探讨反爬虫、多线程、分布式等进阶技术。以大量实例为支撑，覆盖网页、图片、音频等各类数据爬取&#xff…...

编程日记 2025/5/5 5:20:02

kafka为什么这么快？

前言 Kafka的高效有几个关键点，首先是顺序读写。磁盘的顺序访问速度其实很快，甚至比内存的随机访问还要快。Kafka在设计上利用了这一点，将消息顺序写入日志文件，这样减少了磁盘寻道的时间，提高了吞吐量。与传统数据库的…...

编程日记 2025/5/9 12:33:30

书籍推荐：《书法课》林曦

记得樊登老师说过，如果你想了解一个事物，就去读5本相关的书，你会比大部分人都更了解它。这是我读的第4本和“书法”有关的书，作为一个零基础的成年人，林曦这本《书法课》非常值得一读。（无论你是否写字&…...

编程日记 2025/5/9 8:20:04

位图（C语言版）

文章目录位图模型基本操作实现代码运行结果应用存储只有两种状态的数据排序并去重位图模型位图是“位”的数组。为什么需要构建一个专门的数据结构来表示位的数组？：因为计算机最小的寻址单位是字节，而不是位。位图是一种内存紧凑的…...

编程日记 2025/5/9 12:32:29

使用C#元组实现列表分组汇总拼接字段

文章目录使用C#元组实现列表分组汇总拼接字段代码运行结果使用C#元组实现列表分组汇总拼接字段代码 string message string.empty; var tupleList new List<Tuple<string, string, string>>(); tupleList.Add(new Tuple<string, string, string>("…...

编程日记 2025/5/6 23:59:01

淘宝API数据采集接口||调用步骤详解

### 一、注册与认证 1. **注册淘宝开发者账号**： * 访问淘宝开放平台官网，点击“立即入驻”按钮，按照提示完成注册流程。注册过程中需要提供企业名称、联系人信息等基本信息。 2. **创建应用**： * 注册成功后，登录淘…...

编程日记 2025/5/9 12:26:22

C# 调用 C++ 动态库接口

在 C# 中调用 C 动态库接口，通常需要通过 P/Invoke (Platform Invocation Services) 来与 C 代码交互 1. 准备 C 动态库假设你有一个 C 动态库，其中包含如下函数： extern "C" char* getLocationURL(const char* package_name, …...

编程日记 2025/5/9 7:51:32

fastadmin 接口请求提示跨域

问题描述小程序项目，内嵌h5页面，在h5页面调用后端php接口，提示跨域。网上查找解决方案如下： 1，设置header // 在入口文件index.php直接写入直接写入 header("Access-Control-Allow-Origin:*"); header(&q…...

编程日记 2025/5/9 12:30:29

C#_文件写入读取操作

文件写入操作:--------------------------------------------------------------------------- 读取文件:---------------------------------------------------------------------------...

编程日记 2025/5/9 12:13:50

redis的哨兵模式和集群模式

Redis 的哨兵模式（Sentinel Mode） 和集群模式（Cluster Mode） 是两种常见的高可用部署方式，它们各有优缺点，适用于不同的场景。以下是它们的比较： 1. 哨兵模式（Sentinel Mode&#…...

编程日记 2025/5/6 20:25:31

《open3d +pyqt》凸包计算

《open3d +pyqt》凸包计算一、效果展示二、qt设置2.1界面设置2.2 py文件生成三、核心代码一、效果展示二、qt设置 2.1界面设置添加动作Qhull：布局参数： 2.2 py文件生成更新Mainwindow.py 生成py文件三、核心代码代码如下： main.py文件...

编程日记 2025/5/6 1:53:27

数据库报错1045-Access denied for user ‘root‘@‘localhost‘ (using password: YES)解决方式

MySQL 报错 1045 表示用户root从localhost连接时被拒绝访问，通常是因为密码错误、权限问题或配置问题。以下是解决该问题的常见方法： 方法一：检查用户名和密码 • 确认用户名和密码是否正确： 确保输入的用户名和密码完全正确&am…...

编程日记 2025/5/3 17:00:24

ThreadLocal为什么会内存溢出

每个线程（Thread 对象）内部维护一个 ThreadLocalMap，用于存储该线程的所有 ThreadLocal 变量的键值对： ThreadLocalMap虽然是ThreadLocal的静态内部类，但是Thread 对象的属性，当线程存活时ThreadLocalMap不会被回收。 Key：ThreadLocal 实例的弱引用（WeakReference）。…...

编程日记 2025/5/5 3:46:56

数据结构------单向链表。

一.实现单向链表的头插，头删，尾插，尾删，按位置插，按位置删，按位置修改，按元素查找，按元素修改，按元素删除，单链表的逆置，查找倒数第几个元素&…...

编程日记 2025/5/5 17:26:00

Python的那些事第二十二篇：基于 Python 的 Django 框架在 Web 开发中的应用研究

基于 Python 的 Django 框架在 Web 开发中的应用研究摘要 Django 是一个基于 Python 的高级 Web 框架，以其开发效率高、安全性和可扩展性强等特点被广泛应用于现代 Web 开发。本文首先介绍了 Django 的基本架构和核心特性，然后通过一个实际的 Web 开发项目案例，展示了 Dj…...

编程日记 2025/5/6 14:42:51

在 PyCharm 中接入deepseek的API的各种方法

在 PyCharm 中接入 DeepSeek 的 API，通常需要以下步骤： 1. 获取 DeepSeek API 密钥首先，确保你已经在 DeepSeek 平台上注册并获取了 API 密钥（API Key）。如果没有，请访问 DeepSeek 的官方网站注册并申请 …...

编程日记 2025/5/6 7:05:28

当扩展屏显示【输入不支持】怎么解决？！

1、why? 当你遇到这个问题的时候，那就表示您的扩展屏偏老旧，这时候需要进行一些参数设置 2、直接改变桌面模式解决不了问题你是不是尝试过直接在缩放和布局这里设置？在这里直接设置的话，设置的是桌面模式,屏幕大小是会变化但…...

编程日记 2025/5/8 1:52:28

深入剖析 Python 类属性与对象的底层创建与内存分析

各类资料学习下载合集 https://pan.quark.cn/s/8c91ccb5a474 在 Python 中，类和对象是面向对象编程（OOP）的核心组成部分。类属性与实例属性的存储和管理方式，以及类和对象在内存中的分布和结构，对于深入理解 Python 的底层机制至关重要。本文将带你详细解析 P…...

编程日记 2025/5/9 8:28:05

pdf文件的读取，基于深度学习的方法

需要安装一些依赖解析 PDF 文件的详细指南_unstructured.partition.pdf-CSDN博客文章浏览阅读1.3k次，点赞13次，收藏9次。通过 unstructured.partition.pdf 函数，可以方便地解析 PDF 文件并提取其中的文本和表格内容。尽管在使用过程中可能会遇…...

编程日记 2025/5/5 13:29:25

【指令集】Nginx

本文作者： slience_me 【指令集】Nginx 1. 目录结构 Nginx 的基础目录结构通常包括以下几个主要目录： Nginx的目录结构大致如下（以Linux系统为例）： /etc/nginx/ # Nginx的配置文件目录 ├── ngin…...

编程日记 2025/5/2 10:33:14

蓝耘云智算|使用 Deepseek R1 模型优化 BERT 在 NLP 任务中的表现

在自然语言处理（NLP）领域，BERT（Bidirectional Encoder Representations from Transformers）已成为许多文本分类任务的基准模型。然而，随着新模型的出现和技术的不断进步，BERT在某些情况下可能不…...

编程日记 2025/5/8 8:08:25

LINUX常用命令学习

查看系统版本使用hostnamectl命令检查。hostnamectl显示了CentOS的版本以及操作系统的相关信息，非常方便设置linux机器别名称 hostnamectl set-hostname 机器别名 --static 华为云 centos 命令：lsb_release -a linux:cat /proc/version 查看进程路…...

编程日记 2025/5/3 13:16:25

【java面向对象的三大特性】封装、继承和多态

目录标题一、封装（Encapsulation）：二、继承（Inheritance）：三、多态（Polymorphism）：1. 多态的三个必要条件：2.多态的具体实现：3.多态的使用场景&a…...

编程日记 2025/5/1 1:49:57

【开源免费】基于SpringBoot+Vue.JS校园商铺管理系统（JAVA毕业设计）

本文项目编号 T 191 ，文末自助获取源码 \color{red}{T191，文末自助获取源码} T191，文末自助获取源码目录一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程四、功能截图五、文案资料5.1 选题背景5.2 国内…...

编程日记 2025/4/28 22:49:28

日常故障排查 - Java程序故障排查

Java程序故障无论对于任何的故障而言，恢复可用性都是首要目标。但作为一个技术匠人，不能让同一个问题导致多次故障，因此故障的根因剖析以及解决也是很重要的。但是故障根因剖析是需要现场数据来进行分析，因此在故障恢复之前要尽…...

编程日记 2025/5/4 19:48:08

ai数字人分身系统开发源码saas化

#数字人分身系统# #数字人系统源码# #ai数字人123 123# 云罗抖去推数字人分身系统是一款融合了形象克隆、声音克隆、AI数字人分身、AI智能剪辑、智能文案等各种AI技术一体化的短视频营销工具，其核心功能优势主要体现在以下几方面： 真实度高&#xf…...

编程日记 2025/5/8 10:26:59

ABC393E

ABC393F

相关文章：