当前位置: 首页 > 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以上 为什么…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...