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

【学习笔记】CF704B Ant Man

智商不够啊,咋想到贪心的😅

非常经典的贪心模型🤔

首先,从小到大将每个 i i i插入到排列中,用 D P DP DP记录还有多少个位置可以插入,可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注意分 i i i s , t s,t s,t的大小关系讨论。这个做法的时间复杂度是 O ( n 2 ) O(n^2) O(n2),并且转移的情况比较多,估计要调半天。

但是注意到,我们可以 直接贪心 。发现本质上就是每次加入两个固定的数,然后将原来的一个数替换掉,并且一个数只能被替换一次。因此每次贪心的选最优的位置插入即可。

代码可以在 5 min ⁡ 5\min 5min内完成。

另一道直接贪心的题:CF573E Bear and Bowling

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
int n,s,t,to[N];
ll a[N],b[N],c[N],d[N],X[N],res;
ll calc(int i,int j){if(i>j)return X[i]-X[j]+c[i]+b[j];return X[j]-X[i]+d[i]+a[j];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>s>>t;for(int i=1;i<=n;i++)cin>>X[i];for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++)cin>>c[i];for(int i=1;i<=n;i++)cin>>d[i];to[s]=t;for(int i=1;i<=n;i++){if(i==s||i==t)continue;pair<ll,int>tmp={inf,0};for(int j=s;j!=t;j=to[j]){tmp=min(tmp,{calc(j,i)+calc(i,to[j])-calc(j,to[j]),j});}to[i]=to[tmp.se],to[tmp.se]=i;}for(int i=s;i!=t;i=to[i])res+=calc(i,to[i]);cout<<res;
}

相关文章:

【学习笔记】CF704B Ant Man

智商不够啊&#xff0c;咋想到贪心的&#x1f605; 非常经典的贪心模型&#x1f914; 首先&#xff0c;从小到大将每个 i i i插入到排列中&#xff0c;用 D P DP DP记录还有多少个位置可以插入&#xff0c;可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注…...

SQLines数据迁移工具

Data and Analytics Platform Migration - SQLines Tools SQLines提供的工具可以帮助您在不同的数据库平台之间传输数据、转换数据库模式(DDL)、视图、存储过程、包、用户定义函数(udf)、触发器、SQL查询和SQL脚本。 SQLines SQL Converter OverviewCommand LineConfigurati…...

pkl文件与打开(使用numpy和pickle)

文章目录 1. 什么是pkl文件2. 如何打开&#xff1f;Reference 1. 什么是pkl文件 1&#xff09;python中有一种存储方式&#xff0c;可以存储为.pkl文件。 2&#xff09;该存储方式&#xff0c;可以将python项目过程中用到的一些暂时变量、或者需要提取、暂存的字符串、列表、…...

3d渲染农场全面升级,好用的渲染平台值得了解

什么是渲染农场&#xff1f; 渲染农场是专门从事 3D 渲染的大型机器集合&#xff0c;称为渲染节点&#xff0c;这些机器组合在一起执行一项任务&#xff08;渲染 3D 帧和动画&#xff09;。通过将渲染工作分配给数百台机器&#xff0c;可以显着减少渲染时间&#xff0c;从而使…...

1.5 JAVA程序运行的机制

**1.5 Java程序的运行机制** --- **简介&#xff1a;** Java程序的运行涉及两个主要步骤&#xff1a;编译和运行。这种机制确保了Java的跨平台特性。 **主要内容&#xff1a;** 1. **Java程序的执行过程**&#xff1a; - **编译**&#xff1a;首先&#xff0c;扩展名为.jav…...

基于FPGA的拔河游戏设计

基于FPGA的拔河游戏机 设计内容: (1)拔河游戏机需要11个发光二极管排成一行,开机 后只有中间一个亮点,作为拔河的中间线。 游戏双方 各持一个按键,迅速且不断地按动产生脉冲,哪方按 得快,亮点就向哪方移动, 每按一次,亮点移动一次。 移到任一方二极管的终端,该方就…...

关联规则挖掘(下):数据分析 | 数据挖掘 | 十大算法之一

⭐️⭐️⭐️⭐️⭐️欢迎来到我的博客⭐️⭐️⭐️⭐️⭐️ &#x1f434;作者&#xff1a;秋无之地 &#x1f434;简介&#xff1a;CSDN爬虫、后端、大数据领域创作者。目前从事python爬虫、后端和大数据等相关工作&#xff0c;主要擅长领域有&#xff1a;爬虫、后端、大数据…...

8、【Qlib】【主要组件】预测模型:模型训练和预测

8、【主要组件】预测模型:模型训练和预测 简介基本类Example简介 预测模型(Forecast Model)旨在对股票做出预测评分。用户可以通过 qrun 在自动化工作流中使用预测模型。 由于 Qlib 中的组件设计成了松耦合方式,预测模型也可以作为一个独立模块使用。 基本类 Qlib 提供了…...

kettle安装

kettle安装 安装java环境 mkdir /data/java ln -s /data/java/ /opt/ cd /opt/javatar zxvf jdk-8u171-linux-x64.tar.gz#java export JAVA_HOME/opt/java/jdk1.8.0_171 export JRE_HOME$JAVA_HOME/jre export CLASSPATH$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH export PATH$J…...

基于生物地理学优化的BP神经网络(分类应用) - 附代码

基于生物地理学优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于生物地理学优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码1.鸢尾花iris数据介绍2.数据集整理3.生物地理学优化BP神经网络3.1 BP神经网络参数设置3.2 生物地理学算法应用 4…...

第二证券:买基金1w一个月能赚多少?

跟着经济的开展和出资观念的改动&#xff0c;越来越多的人开始出资基金&#xff0c;购买基金已成为普遍且盛行的出资方式之一。在这个商场中&#xff0c;人们最重视的问题莫过于“买基金1w一个月能赚多少&#xff1f;”本文将从多个角度分析这一问题&#xff0c;协助出资者更全…...

蓝桥杯每日一题2023.10.7

跑步锻炼 - 蓝桥云课 (lanqiao.cn) 题目描述 题目分析 简单枚举&#xff0c;对于2的情况特判即可 #include<bits/stdc.h> using namespace std; int num, ans, flag; int m[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool is_ren(int n) {if((n %…...

Linux 系统为何产生大量的 core 文件?

Author&#xff1a;rab 目录 一、问题分析二、解决方案扩展 一、问题分析 上一篇刚讲到《Docker 配置基础优化》&#xff0c;这里再补充一下。就在中秋国庆这段小长假里&#xff0c;接收到了线上服务器磁盘告警通知&#xff0c;线上服务器架构是一个 Docker Swarm 集群&#x…...

Web_python_template_injection SSTI printer方法

这题挺简单的 就是记录一下不同方法的rce python_template_injection ssti了 {{.__class__.__mro__[2].__subclasses__()}} 然后用脚本跑可以知道是 71 {{.__class__.__mro__[2].__subclasses__()[71]}} 然后直接 init {{.__class__.__mro__[2].__subclasses__()[71].__i…...

TCP/IP网络江湖——江湖导航(网络层上篇)

目录 一、引言 二、IP地址与路由 三、IP协议与数据包转发 3.1 IP协议:网络江湖的规矩...

数据结构——AVL树(详解 + C++模拟实现)

文章目录 前言AVL树的概念AVL树节点的定义AVL树类框架AVL树的插入AVL树的旋转新节点插入较高子树的左侧 —— 左左: 右单旋新节点插入较高右子树的右侧——右右: 左单旋新节点插入较高左子树的右侧 —— 左右&#xff1a; 先左单旋然后再有单旋新节点插入较高右子树的左侧&…...

redis 雪崩,穿透,击穿及解决方案

一、缓存雪崩&#xff1a; 1. 原因: 缓存雪崩是指在我们设置缓存时大量采用了相同的过期时间&#xff0c;导致缓存在某一时刻同时失效&#xff0c;请求全部转发到DB&#xff0c;DB瞬时压力过重雪崩。 2. 解决方案: 将失效时间分散&#xff0c;通过生成随机数使得key的过期时间…...

Flutter环境搭建及新建项目

一、下载安装压缩包 https://storage.flutter-io.cn/flutter_infra_release/releases/stable/windows/flutter_windows_3.10.6-stable.zip 二、解压缩 解压之后&#xff0c;将里面的flutter整体拿出来 三、配置环境变量 将flutter/bin全路径配置到系统环境变量里面 四、运行…...

【面试题精讲】深拷贝和浅拷贝区别了解吗?什么是引用拷贝?

“ 有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top ” 首发博客地址[1] 面试题手册[2] 系列文章地址[3] 深拷贝和浅拷贝的区别&#xff1a; 深拷贝&#xff08;Deep Copy&#xff09;和浅拷贝&#…...

CentOS7.9中使用packstack安装train版本

这里写目录标题 材料准备为什么选择packstack安装静态ip系统配置使用阿里云yum源安装packstack部署openstack 材料准备 ecs云服务器8核心16g内存一台&#xff0c;系统盘100GB&#xff0c;系统CentOS7.9vpc网段&#xff1a;192.168.0.1/24eip一个&#xff0c;带宽5M以上 为什么…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

AxureRP-Pro-Beta-Setup_114413.exe (6.0.0.2887)

Name&#xff1a;3ddown Serial&#xff1a;FiCGEezgdGoYILo8U/2MFyCWj0jZoJc/sziRRj2/ENvtEq7w1RH97k5MWctqVHA 注册用户名&#xff1a;Axure 序列号&#xff1a;8t3Yk/zu4cX601/seX6wBZgYRVj/lkC2PICCdO4sFKCCLx8mcCnccoylVb40lP...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...

深度解析:etcd 在 Milvus 向量数据库中的关键作用

目录 &#x1f680; 深度解析&#xff1a;etcd 在 Milvus 向量数据库中的关键作用 &#x1f4a1; 什么是 etcd&#xff1f; &#x1f9e0; Milvus 架构简介 &#x1f4e6; etcd 在 Milvus 中的核心作用 &#x1f527; 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...