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 题意:要买n千克物品,第一天的价格为a,第二天的价格为b。第一天有促销活动,每买m千克物品,可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。 思路:分类讨论&…...
【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 的学习本想只是简单的快速学习一下,结果万万没想到,竟然一下子折腾了好几个月。。。 下面将之前记录的 Jetpack Compose 相关的学习博文进行一个汇总链接整理,方便我以后自己查阅,也希望能帮到一些有正在学…...

【OpenCv】c++ 图像初级操作 | 图像灰度化
文章目录一、图像1、图像信息2、图像种类1)二值图像:2)灰度图:3)彩色图:二、图像转化1、分离彩色图三个通道2、图像灰度化处理一、图像 1、图像信息 Q:图像在计算机中怎么储存? A:…...

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

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

C/C++每日一练(20230310)
目录 1. 用栈实现队列 ★★ 2. 单词搜索 II ★★★ 3. 直线上最多的点数 ★★★ 1. 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: v…...

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

案例06-没有复用思想的接口和sql--mybatis,spring
目录一、背景二、思路&方案问题1优化问题2优化三、总结四、升华一、背景 写这篇文章的目的是通过对没有复用思想接口的代码例子优化告诉大家,没有复用思想的代码不要写,用这种思维方式和习惯来指导我们写代码。 项目中有两处没有复用思想代码&#…...
如何将项目部署到服务器:从选择服务器到维护应用程序的全流程指南
将项目部署到服务器是一个重要的技能,对于开发人员来说,它是必不可少的。在本文中,我将介绍一些关于如何将项目部署到服务器的最佳实践。一、选择服务器在部署项目之前,你需要先选择一个适合你的服务器。如果你已经有一个可用的服…...
怎么做才能不丢消息?
现在主流的消息队列产品都提供了非常完善的消息可靠性保证机制,可以做到在消息传递的过程中,即使发生网络中断或者硬件故障,也能确保消息的可靠传递、不丢消息。 绝大部分丢消息的原因都是由于开发者不熟悉消息队列,没有正确使用…...

前端基础(十六)_数组对象
数组对象 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.作用:将要添加的数组项 添加到…...

数据结构-带头双向循环链表
前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要…...
3 问 6 步,极狐GitLab 帮助企业构建高效、安全、合规的 DevSecOps 文化
本文来源:about.gitlab.com 作者:Vanessa Wegner 译者:极狐(GitLab) 市场部内容团队 🔒 安全为何重要?此前,我们分享了: 1. 2023年DevOps发展趋势👉重磅!GitLab 提出五大…...
SPA(单页应用)知多少
单页面应用程序将所有的活动局限于一个Web页面中,在该Web页面初始化时加载相应的HTML、JavaScript 和 CSS。一旦页面加载完成,单页面应用不会因为用户的操作而进行页面的重新加载或跳转。取而代之的是利用 JavaScript 动态的变换HTML的内容,从…...
Selenium实战【远程控制】【JAVA爬虫】
简介 Selenium RemoteWebDriver是Selenium WebDriver的一个扩展,它可以将测试运行在远程机器上的浏览器中。 使用RemoteWebDriver,可以在本地机器上编写测试脚本,然后将测试请求发送到远程机器上的浏览器中执行。这使得测试可以在多个不同的机器上并行运行,从而加快测试的…...

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

我又和redis超时杠上了
背景 经过上次redis超时排查,并联系云服务商解决之后,redis超时的现象好了一阵子,但是最近又有超时现象报出,但与上次不同的是,这次超时的现象发生在业务高峰期,在简单看过服务器的各项指标以后࿰…...
一文带你吃透MySQL数据库!
文章目录1. 索引2. 事务3. 存储引擎4. 锁机制5. MySQL其他知识点文章字数大约1.27万字,阅读大概需要42分钟,建议收藏后慢慢阅读!!!1. 索引 为什么使用索引 通过创建唯一性索引,可以保证数据库表中每一行数据…...

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

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...

如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...