当前位置: 首页 > 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;数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

Oracle实用参考(13)——Oracle for Linux物理DG环境搭建(2)

13.2. Oracle for Linux物理DG环境搭建 Oracle 数据库的DataGuard技术方案,业界也称为DG,其在数据库高可用、容灾及负载分离等方面,都有着非常广泛的应用,对此,前面相关章节已做过较为详尽的讲解,此处不再赘述。 需要说明的是, DG方案又分为物理DG和逻辑DG,两者的搭建…...