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

F. Valuable Cards D. Smithing Skill

D题

F题

F题:

        因为是连续的且都要选,我们直接从左到右去取每个区间到不合法的情况即可,可以在n+1的位置添加一个x来结束区间判断。因为是要乘积为x,那么我们只需要放x的因子进去,不然会超时,同时也可以用vis数组来标记,可以不放重复的元素,在找到不合法区间的时候要清空vector且将vector里有的元素的vis值重新置0.记得判断元素大小,不然会re,或者用map。

        代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);int n,x;
int vis[N],a[N];void solve(){cin>>n>>x;for(int i=0;i<=x;i++)vis[i]=0;for(int i=1;i<=n;i++){cin>>a[i];}a[n+1]=x;int ans=0;vector<int> t;for(int r=1;r<=n+1;r++){if((((x%a[r])==0)&&vis[x/a[r]])||a[r]==x){ans++;for(auto &y:t)vis[y]=0;t.clear();if(a[r]<=x&&!vis[a[r]]&&x%a[r]==0){t.push_back(a[r]);vis[a[r]]=1;}}else{vector<int> u;for(auto &y:t){if(y*a[r]<=x&&!vis[y*a[r]]&&((x%(y*a[r]))==0)){vis[y*a[r]]=1;//t.push_back(a[r]*y);u.push_back(a[r]*y);}}for(auto &y:u)t.push_back(y);if(a[r]<=x&&!vis[a[r]]&&x%a[r]==0){vis[a[r]]=1;t.push_back(a[r]);}}}cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin>>t;while(t--){solve();}return 0;
}

D题:

        容易想到贪心,如果a【i】-b【i】很小我们肯定贪心的选这个武器,因为这样花费的金属少。

又因为每次铸造的base cost是a【i】,所以我们需要给每个a【i】-b【i】一个可选的前提条件,就是base cost大于等于a【i】时才可以选,我们可以在读入的时候每次更新f【a【i】】的值,f【a【i】】就表示从a【i】cost以上都可以使用这个最小值a【j】-b【j】。读入好了之后,我们就可以从1到1e6来更新每个base cost可选的最优花费,从小到大更新可以保证后面的每个cost都是大于等于这个a【j】-b【j】的基础花费的(前缀最小值)。

        处理完每个cost的最优选择后,我们考虑dp(我们有m种武器,每次都会用到相同的贪心策略,其实就是预处理这些贪心策略,然后o(1)查询,比如a【i】-b【i】==1的时候每次都是o(n)的复杂度,再乘m就tle了)。因为前面处理完了每个cost的最优选择,也就是说只要有cost,那么一定是选f【cost】这个武器方案,那么也就是说dp【cost】是从dp【cost-f【cost】】+1转移过来的,+1是因为这里我们花费了f【cost】铸造了一个武器。

        当cost大于1e6的时候,我们根据a【i】的范围可知cost一定可以使用f【1e6】的最优选择将cost降到1e6以下,然后直接输出之前算出来的dp值即可。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const int inf=0x3f3f3f3f;
const int N=2e5+10;
const int mod=1e9+7;
const ll INF=2e9+10;
mt19937_64 rd(23333);
uniform_real_distribution<double> drd(0.000001,0.99999);void solve(){int n,m,b,c;cin>>n>>m;vector<int>a(n);for(int i=0;i<n;++i){cin>>a[i];}vector<int> f(1e6+10,INT_MAX);for(int i=0;i<n;++i){cin>>b;f[a[i]]=min(f[a[i]],a[i]-b);//记录从当前base cost值开始的最小花费(会损坏值) }for(int i=1;i<=1e6;++i){f[i]=min(f[i-1],f[i]);}vector<int> dp(1e6+10,0);for(int i=1;i<=1e6;++i){if(f[i]<=i){dp[i]=dp[i-f[i]]+1;}}int ans=0;for(int i=0;i<m;++i){cin>>c;if(c>1e6){int t=(c-1e6)/f[1e6]+1;ans+=t;c-=t*f[1e6];}ans+=dp[c];}cout<<ans*2<<endl;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--){solve();}return 0;
}

相关文章:

F. Valuable Cards D. Smithing Skill

D题 F题 F题&#xff1a; 因为是连续的且都要选&#xff0c;我们直接从左到右去取每个区间到不合法的情况即可&#xff0c;可以在n1的位置添加一个x来结束区间判断。因为是要乘积为x&#xff0c;那么我们只需要放x的因子进去&#xff0c;不然会超时&#xff0c;同时也可以用v…...

【电子通识】IPC-A-600中对验收标准的定义

在文章【电子通识】IPC-A-610标准对产品的四种验收条件都是什么意思&#xff1f;中我们讲到IPC-A-610标准&#xff08;电子组件的可接受性&#xff09;对于产品的四种验收条件。本文中我们同理讲一讲IPC-A-600中对验收标准的定义。 IPC-A-600文件中的多数示意图和照片同时表示每…...

MyBatis(初阶)

1.什么是MyBtis MyBatis是持久层框架&#xff0c;⽤于简化JDBC的开发。 2.准备工作 2.1 创建⼯程 数据库: 2.2 配置数据库连接字符串 以application.yml⽂件为例: 2.3 写持久层代码 Data public class UserInfo {private Integer id;private String username;private Stri…...

KDP数据平台:以实战案例验证技术领先力

本文由智领云 LeetTools 工具自动生成 申请试用&#xff1a; https://www.leettools.com/feedback/ 在当今快速发展的技术环境中&#xff0c;数据平台的选择对企业的数字化转型和业务发展至关重要。智领云开源KDP&#xff08;Kubernetes Data Platform&#xff09;在数据处理和…...

[Linux] 什么是 Shell?

一、什么是 shell ? shell在英语中的意思就是外壳&#xff0c;所以我们习惯称shell程序为壳程序。那为什么又会被叫做壳程序呢&#xff1f;那是因为shell程序是在内核上面的&#xff0c;属于操作系统的外壳部分&#xff0c;因此我们就称之为壳程序(shell)。 在 Linux 中&#…...

大模型学习应用 2:快速上手大模型基于langchain实现RAG检索应用

快速上手大模型基于langchain实现RAG检索应用 - 项目作业 目录 准备工作镜像选择算力选择安装包数据说明提示参考链接 Task1 申请 api 后&#xff0c;使用 langchain 导入大模型&#xff0c;并打印出大模型信息Task2 使用 langchian 加载数据&#xff0c;并把数据打印出来Task…...

python环境安装之后,cmd输入python回车会打开微软商店

坑爹&#xff01;python环境安装之后&#xff0c;cmd输入python回车会打开微软商店 最近发现&#xff0c;安装python环境成功之后&#xff0c;可能会出现cmd输入python验证是否安装成功老会打开微软商店&#xff01; 解决&#xff0c;打开系统环境配置&#xff0c;找到刚安装…...

USB Type-C如何取9V、12V、15V、20V电压-PD快充协议芯片ECP5701

相信大家在生活中也发现了&#xff0c;现在越来越多的设备都改用这种type-C接口的母座进行取电了。 因为欧盟决议 &#xff1a;自2024年起部分消费电子产品必须提供单一的USB-C充电接口。 那么这种type-C接口相比之前的Micro-B接口有着一个很大的优势就是可以有更高的电压&…...

Go 语言 Map 17

Go 语言提供了一个强大的 Map 结构体&#xff0c;用于存储键值对。Map 可以用来存储数据&#xff0c;快速查找和修改数据。下面是 Go 语言 Map 的使用教程。 什么是 Map&#xff1f; Map 是一个键值对的集合&#xff0c;它可以存储任意类型的键和值。Map 中的每个键都是唯一的…...

移植bash到openharmony

1.交叉工具链 下载地址&#xff1a; http://ci.openharmony.cn/workbench/cicd/dailybuild/dailylist 进入ohos-sdk-full&#xff0c;下载一个sdk版本&#xff0c;这里下载的版本是version-Master_Version-OpenHarmony_5.0.0.35-20240805_020232-ohos-sdk-full.tar.gz。 解…...

git stash详细教程

git stash详细教程 基本命令: git stash: 保存当前未提交的更改&#xff0c;并恢复到干净的工作目录。git stash list: 列出所有的 stash。git stash show: 显示最新 stash 的简要内容。git stash show -p: 显示最新 stash 的详细内容。 应用和删除: git stash apply: 应用最新…...

UDP网络攻击

UDP&#xff08;User Datagram Protocol&#xff09;作为一种无连接的网络传输协议&#xff0c;以其速度快和资源消耗小的特点&#xff0c;在多种网络服务中发挥着重要作用&#xff0c;UDP的无连接特性也使其成为DDoS攻击的优选协议。 UDP攻击概念 UDP攻击是一种网络攻击手段…...

漏洞扫描的重要性,如何做好漏洞扫描服务

随着互联网技术的飞速发展&#xff0c;网络安全问题已成为不容忽视的重大挑战。其中&#xff0c;系统漏洞威胁作为最常见且严重的安全危险之一&#xff0c;对组织和个人的信息资产构成了巨大威胁。下面我们就来了解下漏洞扫描的好处、漏洞扫描的操作方法以及如何做好网络安全。…...

unity程序简易框架

1. 框架基本结构 2. 单例模式基类模块 2.1 BaseManager.cs using System.Collections; using System.Collections.Generic; using UnityEngine;public class BaseManager<T> where T:new() {private static T instance;public static T GetInstance(){if (instance == …...

Go小技巧易错点100例(十六)

本期看点&#xff1a; 正文开始&#xff1a; 切片的长度和容量 在Go语言中&#xff0c;切片&#xff08;slice&#xff09;是一个引用类型&#xff0c;它是对底层数组的抽象表示&#xff0c;提供了动态长度的、灵活的序列类型。切片包含三个重要的属性&#xff1a;指向底层数…...

通过Golang实现中间人攻击,查看和修改https流量包

要查看和修改 HTTPS 流量包&#xff0c;需要使用一个能够执行 中间人攻击&#xff08;Man-in-the-Middle, MITM&#xff09; 的代理工具。这个工具将拦截并解密 HTTPS 流量&#xff0c;然后允许查看和修改流量包的内容&#xff0c;再将其重新加密并发送到目标服务器。 完整的 …...

MySQL 安装与配置指南

MySQL 是一种广泛使用的关系型数据库管理系统&#xff0c;为各种应用程序提供高效的数据存储和管理解决方案。本文将介绍如何在不同的操作系统中安装 MySQL&#xff0c;以及如何进行基本的配置&#xff0c;以确保数据库系统的最佳性能和稳定性。 一、环境准备 1.1 系统要求 …...

android13布局查看工具 无源码查看布局 在线查找ui布局id

总纲 android13 rom 开发总纲说明 目录 1.前言 2.工具介绍 2.1工具1 2.2工具2 2.3工具3 2.4工具4 3.彩蛋 1.前言 Android 13提供了一些工具来帮助开发人员查看和优化应用的布局。方便的让我们找到具体应用的布局文件等信息。 2.工具介绍 2.1工具1 老版本DDMS&#x…...

【自动化测试必学语言】python:UnitTest框架

目录 介绍 框架 什么是UnitTest框架&#xff1f; 为什么使用UnitTest框架? UnitTest核心要素&#xff08;unitest 的组成部分&#xff09; 1.TestCase&#xff08;最核心的模块&#xff09; 2.TestSuite 3.TestRunner 4.TestLoader 5.Fixture TestCase&#xff08…...

大话LLM之向量数据库

向量数据库是一种专门设计的存储系统&#xff0c;旨在高效处理和查询高维向量数据&#xff0c;通常用于人工智能和机器学习应用中&#xff0c;以实现快速准确的数据检索。 好的&#xff0c;今天我们就来聊聊人工智能和向量数据库的事儿。现在人工智能发展得特别快&#xff0c;特…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...