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

Codeforces Round 852 (Div. 2)

A

Yet Another Promotion

题意:要买n千克物品,第一天的价格为a,第二天的价格为b。第一天有促销活动,每买m千克物品,可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。

思路:分类讨论,当a<=b时,肯定全在第一天买掉。当a>b时,又可能第二天的价格特别低,因此全在第二天买;或者第一天的平均价格比较低,先尽可能用第一天去买,没凑齐的用第二天买

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int, int>
typedef long long ll;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;using namespace std;
ll a, b, n, m;
void solve()
{cin >> a >> b >> n >> m;if (a <= b)cout << a * (n - n / (m + 1)) << '\n';else{cout << min(n * b, n / (m + 1) * a * m + (n - n / (m + 1) * (m + 1)) * b) << '\n';}
}
signed main()
{// ios;int _t = 1;cin >> _t;while (_t--)solve();system("pause");return 0;
}

B

Fedya and Array

题意:环形数组,定义ai为局部最大值时满足ai大于左右两边的元素;局部最小值同理。现给你局部最大值的总和x,局部最小值的总和y,构造环形数组且要满足数组相邻元素差值等于1.

思路:构造一个v型的即可,从x减到y,再从y加到x-1

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int x,y;
void solve()
{cin>>x>>y;vector<int>ans;int t=x;while(t>y) ans.push_back(t--);while(y<x) ans.push_back(y++);cout<<ans.size()<<'\n';for(int i=0;i<ans.size();i++)cout<<ans[i]<<" \n"[i==ans.size()-1];
}
signed main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

C

Dora and Search

题意:给定长度为n的排列,求l,r,满足 a[l] != min(a[l~r]),  a[l] != max(a[l~r]) , a[r] != min(a[l~r]), a[r] != max(a[l~r])

思路:从两端将数组剥开,当两端是极值时,就向内部移动。直到移到两端都不是极值即可。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int a[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int mi=1,ma=n;int l=1,r=n;while(l<r){if(a[l]==mi) mi++,l++;else if(a[l]==ma) ma--,l++;else if(a[r]==mi) mi++,r--;else if(a[r]==ma) ma--,r--;else break;}if(l<r) cout<<l<<' '<<r<<'\n';else cout<<-1<<'\n';
}
signed main()
{//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

D

Moscow Gorillas

题意:给定两个长度为n的排列a和排列b,问有多少对l,r满足mex(a[l~r])=mex(b[l~r])

mex为数组中没出现的最小正整数。

思路:枚举mex,区间mex=i时,此时区间不含i

当mex=1时,我们找到1在a和b中出现的位置,记为L和R,那么左右端点可以在[1,L) 和(L,R)和(R,n]中选。若区间长度为x,那么对答案的贡献就是x*(x+1)/2

当mex>1时,我们找到mex在a和b中出现的位置记为pa,pb;接下来分情况讨论即可。①pa <L <R< pb时,左端点可以在(pa,L]中选,右端点可以在[R,pb)中选。②pa<pb<L<R ③L<R<pa<pb ④L<pa<R || L<pb<R

注意当mex=n+1时,此时l=1,r=n也是满足的。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ios cin.sync_with_stdio(false)
#define PII pair<int,int>
#define int long long
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n;
int a[N],b[N];
int posa[N],posb[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i],posa[a[i]]=i;for(int i=1;i<=n;i++) cin>>b[i],posb[b[i]]=i;ll ans=0;int L=posa[1],R=posb[1];if(L>R) swap(L,R);ans+=(L-1)*(L)/2+(n-R)*(n-R+1)/2+max(0ll,(R-L-1)*(R-L)/2);for(int mex=2;mex<=n;mex++){int pa=posa[mex],pb=posb[mex];if(pa>pb) swap(pa,pb);if((pa>=L&&pa<=R)||(pb>=L&&pb<=R)) {}else if(L>pa&&pb>R) //pa L R pb{ans+=(L-pa)*(pb-R);}else if(pb<L) //pa pb L R{ans+=(L-pb)*(n-R+1);}else if(pa>R) //L R pa pb{ans+=(L)*(pa-R);}L=min(L,pa);R=max(R,pb);}cout<<ans+1<<'\n';
}
signed main()
{//ios;int _t=1;// cin>>_t;while(_t--) solve();system("pause");return 0;
}

相关文章:

Codeforces Round 852 (Div. 2)

A Yet Another Promotion 题意&#xff1a;要买n千克物品&#xff0c;第一天的价格为a&#xff0c;第二天的价格为b。第一天有促销活动&#xff0c;每买m千克物品&#xff0c;可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。 思路&#xff1a;分类讨论&…...

【PTA Data Structures and Algorithms (English)】7-2 Reversing Linked List

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K3, then you must output 3→2→1→6→5→4; if K4, you must output 4→3→2→1→5→6. Input Specif…...

Jetpack Compose 学习汇总

关于 Jetpack Compose 的学习本想只是简单的快速学习一下&#xff0c;结果万万没想到&#xff0c;竟然一下子折腾了好几个月。。。 下面将之前记录的 Jetpack Compose 相关的学习博文进行一个汇总链接整理&#xff0c;方便我以后自己查阅&#xff0c;也希望能帮到一些有正在学…...

【OpenCv】c++ 图像初级操作 | 图像灰度化

文章目录一、图像1、图像信息2、图像种类1&#xff09;二值图像&#xff1a;2&#xff09;灰度图:3&#xff09;彩色图&#xff1a;二、图像转化1、分离彩色图三个通道2、图像灰度化处理一、图像 1、图像信息 Q&#xff1a;图像在计算机中怎么储存&#xff1f; A&#xff1a;…...

VIT(vision transformer)onnx模型解析

背景&#xff1a;transformer在CV领域的应用论文下载链接&#xff1a;https://arxiv.org/abs/2010.11929Pytorch实现代码&#xff1a; pytorch_classification/vision_transformer(太阳花的小绿豆博主实现的代码)有一些大神在研究关于CNNtransformer或者纯用transformer实现。原…...

红黑树的介绍和实现

文章目录1. 红黑树1.1 红黑树的概念1.2 红黑树的性质1.3 红黑树节点的定义1.4 红黑树的插入1.5 红黑树的验证1.6 红黑树与AVL树的比较1. 红黑树 1.1 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以…...

C/C++每日一练(20230310)

目录 1. 用栈实现队列 ★★ 2. 单词搜索 II ★★★ 3. 直线上最多的点数 ★★★ 1. 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQueue 类&#xff1a; v…...

Go语言基础知识

常量//定义方式 const a int12;//指定变量类型 const b12;//不指定变量类型&#xff0c;由编译时go自动确认 const(//多行定义方式a12b23 ) //说到const&#xff0c;不得不得不提到的一个参数iota,初始值为0&#xff0c;在用const多行定义的方式中&#xff0c; 如果第一行定义了…...

案例06-没有复用思想的接口和sql--mybatis,spring

目录一、背景二、思路&方案问题1优化问题2优化三、总结四、升华一、背景 写这篇文章的目的是通过对没有复用思想接口的代码例子优化告诉大家&#xff0c;没有复用思想的代码不要写&#xff0c;用这种思维方式和习惯来指导我们写代码。 项目中有两处没有复用思想代码&#…...

如何将项目部署到服务器:从选择服务器到维护应用程序的全流程指南

将项目部署到服务器是一个重要的技能&#xff0c;对于开发人员来说&#xff0c;它是必不可少的。在本文中&#xff0c;我将介绍一些关于如何将项目部署到服务器的最佳实践。一、选择服务器在部署项目之前&#xff0c;你需要先选择一个适合你的服务器。如果你已经有一个可用的服…...

怎么做才能不丢消息?

现在主流的消息队列产品都提供了非常完善的消息可靠性保证机制&#xff0c;可以做到在消息传递的过程中&#xff0c;即使发生网络中断或者硬件故障&#xff0c;也能确保消息的可靠传递、不丢消息。 绝大部分丢消息的原因都是由于开发者不熟悉消息队列&#xff0c;没有正确使用…...

前端基础(十六)_数组对象

数组对象 1、创建数组 // 字面量创建const arr [1, 2, 3, 4, 5, 6]// 构造函数创建const arr2 new Array(1, 2, 3, 4, 5, 6)const arr3 Array(1, 2, 3, 4, 5, 6)2.push (从数组末尾添加元素) a.数组.push(要添加进数组的数组项) b.作用&#xff1a;将要添加的数组项 添加到…...

数据结构-带头双向循环链表

前言&#xff1a; 链表有很多种&#xff0c;上一章结&#xff0c;我复盘了单链表&#xff0c;这一章节&#xff0c;主要针对双链表的知识点进行&#xff0c;整理复盘&#xff0c;如果将链表分类的话&#xff0c;有很多种&#xff0c;我就学习的方向考察的重点&#xff0c;主要…...

3 问 6 步,极狐GitLab 帮助企业构建高效、安全、合规的 DevSecOps 文化

本文来源&#xff1a;about.gitlab.com 作者&#xff1a;Vanessa Wegner 译者&#xff1a;极狐(GitLab) 市场部内容团队 &#x1f512; 安全为何重要&#xff1f;此前&#xff0c;我们分享了&#xff1a; 1. 2023年DevOps发展趋势&#x1f449;重磅&#xff01;GitLab 提出五大…...

SPA(单页应用)知多少

单页面应用程序将所有的活动局限于一个Web页面中&#xff0c;在该Web页面初始化时加载相应的HTML、JavaScript 和 CSS。一旦页面加载完成&#xff0c;单页面应用不会因为用户的操作而进行页面的重新加载或跳转。取而代之的是利用 JavaScript 动态的变换HTML的内容&#xff0c;从…...

Selenium实战【远程控制】【JAVA爬虫】

简介 Selenium RemoteWebDriver是Selenium WebDriver的一个扩展,它可以将测试运行在远程机器上的浏览器中。 使用RemoteWebDriver,可以在本地机器上编写测试脚本,然后将测试请求发送到远程机器上的浏览器中执行。这使得测试可以在多个不同的机器上并行运行,从而加快测试的…...

图片动画化应用中的动作分解方法

作者 | FesianXu 前言 最近基于AI的换脸应用非常的火爆&#xff0c;同时也引起了新一轮的网络伦理大讨论。如果光从技术的角度看&#xff0c;对于视频中的人体动作信息&#xff0c;通常可以通过泰勒展开分解成零阶运动信息与一阶运动信息&#xff0c;如文献[1,2]中提到的&…...

我又和redis超时杠上了

背景 经过上次redis超时排查&#xff0c;并联系云服务商解决之后&#xff0c;redis超时的现象好了一阵子&#xff0c;但是最近又有超时现象报出&#xff0c;但与上次不同的是&#xff0c;这次超时的现象发生在业务高峰期&#xff0c;在简单看过服务器的各项指标以后&#xff0…...

一文带你吃透MySQL数据库!

文章目录1. 索引2. 事务3. 存储引擎4. 锁机制5. MySQL其他知识点文章字数大约1.27万字&#xff0c;阅读大概需要42分钟&#xff0c;建议收藏后慢慢阅读&#xff01;&#xff01;&#xff01;1. 索引 为什么使用索引 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据…...

[学习笔记] 2. 数据结构

数据结构视频地址&#xff1a;https://www.bilibili.com/video/BV1uA411N7c5 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说&#xff0c;数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...

LangChain【6】之输出解析器:结构化LLM响应的关键工具

文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器&#xff1f;1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...