牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)
文章目录
- 牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)
- A. 夹心饼干
- B. C. 食堂大作战(思维)
- D. 小苯的排列计数(差分、树状数组)
- E. 和+和(大根堆,前缀和)
- F. 怎么写线性SPJ (思维、递归)
牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)
A. 夹心饼干
语法基础题
#include<bits/stdc++.h>
using namespace std;int main(){string s;cin >> s;cout << (s[0] == s[2] ? "YES" : "NO") << endl;return 0;
}
B. C. 食堂大作战(思维)
显然,只要没有两个窗口同时关门,即合法方案。
对于方案,按照关门时间排序,依次输出即可。
#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5 + 5;pair<int, int> a[maxn];int main(){int n;cin >> n;for(int i = 1; i <= n; i++){cin >> a[i].first;a[i].second = i;} sort(a+1, a+1+n);int flag = 1;for(int i = 1; i <= n; i++){if(a[i].first == a[i-1].first){flag = 0;break;}}if(flag){cout << "YES" << endl;}else cout << "NO" << endl;return 0;
}
D. 小苯的排列计数(差分、树状数组)
对于样例:
10
7 7 7 5 5 1 1 1 1 1 1
首先,标黄色的元素的值是确定的。
其次,我们依次来看:
- 72,在此处,可以选择 8,9,10。即,有三种选择。(这里表示第二个 7,其他相同形式同理)
- 73,在此处,可以选择 8,9,10。但是,这时已经在 72处使用过一个元素,还有两种选择可用。
- 52,在此处,可以选择 6,8,9,10。但是,这时已经在 72 和 73 处使用过两个元素,还有两种选择可用。
- 依次类推…
对于一个方案,在某元素 x:
- 如果第一次出现时,该元素在只能在此处,在此处贡献一种组合的可能。
- 如果元素 x 不是第一次出现时:
- 如有大于该元素的选择,可选择元素的个数等于此处贡献的组合。
- 如没有大于该元素的选择,则方案不合法。
使用差分和树状数组配合,即可实现,求[x, n] 中的可用元素个数。
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e6 + 5;
const ll mod = 998244353;ll a[maxn], tree[maxn];int lowbit(int x){return x & (-x);
}void add(int i, int value){while(i < maxn){tree[i] += value;i += lowbit(i);}
}int sum(int i){int res = 0;while(i > 0){res += tree[i];i -= lowbit(i);}return res;
}int main(){int ncase;cin >> ncase;while(ncase--){int n;cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) tree[i] = 0;for(int i = 1; i <= n; i++) add(i, 1);ll res = 1;for(int i = 1; i <= n; i++){if(a[i] != a[i-1]){if(a[i] > a[i-1] && i != 1){res = 0;break;}add(a[i], -1);}else{int cnt = sum(n) - sum(a[i]); // 差分if(cnt == 0){res = 0;break;}else{res = res * cnt % mod;add(a[i]+1, -1);}}}cout << res << endl;}return 0;
}
E. 和+和(大根堆,前缀和)
题意等价于:选一个 x,在 a[1,x] 中选 m 个最小的数,在 b[x+1, n] 中选 m 个最小的数,使得选出的数sum最小。
枚举所有可能的 x,只要能 O(1) 或者 O(log(n)) 求出 a[1,x] 中 m 个最小的数的和,即可。
对于a数组,维护一个大小为 m 的大根堆,即前 i 个元素中最小的 m 个元素。
依次遍历a数组,插入新值a[i],删除最大的元素,维护sum,维护前缀min即可。
对于 b 数组,逆序遍历,操作同上。
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e5 + 5;ll a[maxn], b[maxn];
ll pre[maxn], suf[maxn];priority_queue<int> qu;int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) cin >> b[i];ll sum = 0;for(int i = 1; i <= n; i++){sum += a[i];qu.push(a[i]);if(i > m){sum -= qu.top();qu.pop(); }pre[i] = sum;} sum = 0;while(!qu.empty()) qu.pop();for(int i = 1; i <= n; i++){sum += b[n-i+1];qu.push(b[n-i+1]);if(i > m){sum -= qu.top();qu.pop(); }suf[n-i+1] = sum;}ll res = 2e9;for(int i = m; i+m-1 < n; i++){res = min(res, pre[i] + suf[i+1]);}cout << res << endl;return 0;
}
F. 怎么写线性SPJ (思维、递归)
手搓几个样例后,容易想到一个事实:
令 mid = ( l + r ) / 2,如果 a[mid] 是一个 “唯一元素”,接下来,只需要考虑 (l, mid-1) 和 (mid+1, r) 即可。
用相同的思路处理(l, mid-1) 和 (mid+1, r),直到区间大小为 1。(递归)
#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 2e5 + 5;int a[maxn];void dfs(int l, int r, int num){if(l > r) return; int mid = l + r >> 1;a[mid] = num;dfs(l, mid-1, num+1);dfs(mid+1, r, num+1);
}int main(){int n;cin >> n;dfs(1, n, 1); set<int> s;for(int i = 1; i <= n; i++) s.insert(a[i]);cout << s.size() << endl;for(int i = 1; i <= n; i++) cout << a[i] << " ";return 0;
}
相关文章:
牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)
文章目录 牛客周赛 Round 82(思维、差分、树状数组、大根堆、前后缀、递归)A. 夹心饼干B. C. 食堂大作战(思维)D. 小苯的排列计数(差分、树状数组)E. 和和(大根堆,前缀和)F. 怎么写线性SPJ &…...
MQTT实现智能家居------2、写MQTT程序的思路
举个最简单的例子: 手机------服务器-------家具 我们这里只看手机和家具的客户端: 手机:1)需要连接服务器 2)需要发布指令给服务器到家里的家具 3)接受来自于家里家具的异常状况 4)保持心…...
大模型面试问题准备
1. BERT的多头注意力为什么需要多头? 为了捕捉不同子空间的语义信息,每个头关注不同的方面,增强模型的表达能力 2. 什么是softmax上下溢出问题? 问题描述: 上溢出:ye^x中,如果x取非常大的正数…...
C语言:二维数组在内存中是怎么存储的
目录 1. 二维数组的定义: 2. 行主序存储: 具体内存排列: 3. 如何通过指针访问数据: 4. 总结: 在 C 语言中,二维数组是按 行主序(row-major order) 存储的。也就是说,…...
AI时代前端开发技能变革与ScriptEcho:拥抱AI,提升效率
在飞速发展的科技浪潮中,人工智能(AI)正以前所未有的速度改变着各个行业,前端开发领域也不例外。曾经被认为是核心竞争力的传统前端技能,例如精通HTML、CSS和JavaScript,其价值正在发生微妙的变化。 得益于…...
计算机毕业设计SpringBoot+Vue.js美容院管理系统(源码+文档+PPT+讲解)
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
【LeetCodehHot100_0x01】
LeetCodeHot100_0x01 1. 两数之和 解题思路: 暴力枚举法、哈希法 【暴力枚举】 class Solution {public int[] twoSum(int[] nums, int target) {int n nums.length;for(int i0;i<n;i) {for(int ji1;j<n;j) {if(nums[i] nums[j] target) {return new in…...
Qt::MouseButtons解析
一 问题 今天想自定定义一个QMouseEvent变量,变量的的初始化参数有Qt::MouseButtons,这是个啥?查看类型为QFlags<Qt::MouseButton>。 二 Qt::MouseButton Qt::MouseButton 是 Qt 框架中定义的一个枚举类型(enum),用于表示鼠标事件中的物理按钮。它是 Qt 事件处理…...
跨域问题解释及前后端解决方案(SpringBoot)
一、问题引出 有时,控制台出现如下问题。 二、为什么会有跨域 2.1浏览器同源策略 浏览器的同源策略 ( Same-origin policy )是一种重要的安全机制,用于限制一个源( origin )的文档或 脚本如何与另一个源的资源进行…...
4-知识图谱的抽取与构建-4_2实体识别与分类
🌟 知识图谱的实体识别与分类🔥 🔍 什么是实体识别与分类? 实体识别(Entity Recognition)是从文本中提取出具体的事物,如人名、地名、组织名等。分类(Entity Classification&#x…...
腾讯云大模型知识引擎×DeepSeek赋能文旅
腾讯云大模型知识引擎DeepSeek赋能文旅 ——以合肥文旅为例的技术革新与实践路径 一、技术底座:知识引擎与DeepSeek的融合逻辑 腾讯云大模型知识引擎与DeepSeek模型的结合,本质上是**“知识库检索增强生成(RAG)实时联网能力”**…...
TMDS视频编解码算法
因为使用的是DDR进行传输,即双倍频率采样,故时钟只用是并行数据数据的5倍,而不是10倍。 TMDS算法流程: 视频编码TMDS算法流程实现: timescale 1 ps / 1ps //DVI编码通常用于视频传输,将并行数据转换为适合…...
C++程序员内功修炼——Linux C/C++编程技术汇总
在软件开发的宏大版图中,C 语言宛如一座巍峨的高山,吸引着无数开发者攀登探索。而 Linux 操作系统,以其开源、稳定、高效的特性,成为了众多开发者钟爱的开发平台。将 C 与 Linux 相结合,就如同为开发者配备了一把无坚不…...
【数据结构】链表中快指针和慢指针
目录 一、找出并返回链表的中间结点 二、输出链表中倒数第k个结点 三、判断链表中是否有环 四、两个单链表相交 一、找出并返回链表的中间结点 给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 要求:只遍历…...
6_zookeeper集群配置
配置 一、配置myid文件 # 进入解压好的文件夹下面 touch myid vim myid # master节点写0,slave1节点写1,slave2节点写2二、配置zoo.cfg文件 1.在master节点编辑zookeeper配置文件 # 进入解压好的文件夹下面 cd conf/ cp zoo_sample.cfg zoo.cfg vim …...
Docker核心概念
容器介绍 Docker 是世界领先的软件容器平台,所以想要搞懂 Docker 的概念我们必须先从容器开始说起。 什么是容器? 先来看看容器较为官方的解释 一句话概括容器:容器就是将软件打包成标准化单元,以用于开发、交付和部署。 容器镜像是轻量…...
LD_PRELOAD 绕过 disable_function 学习
借助这位师傅的文章来学习通过LD_PRELOAD来绕过disable_function的原理 【PHP绕过】LD_PRELOAD bypass disable_functions_phpid绕过-CSDN博客 感谢这位师傅的贡献 介绍 静态链接: (1)举个情景来帮助理解: 假设你要搬家&#x…...
如何用JAVA实现布隆过滤器?
目录 引言 布隆过滤器的原理 1. 核心思想 2. 优缺点 布隆过滤器的使用场景 Java 实现布隆过滤器 1. 实现步骤 2. 代码实现 3. 代码说明 4. 测试结果 布隆过滤器的优化 总结 引言 布隆过滤器(Bloom Filter)是一种高效的概率数据结构࿰…...
游戏开发 游戏开始界面
目录 前言 一 游戏初始化界面的分析 二 游戏的大概框架 三 显示界面的开发 四 完整代码 总结 我们可以来看看游戏初始界面是什么样的 勇士游戏样例 前言 这里是开发游戏的初始界面 一 游戏初始化界面的分析 我们需要一个背景图,开始游戏图标࿰…...
Python解析 Flink Job 依赖的checkpoint 路径
引言 Apache Flink 是一个强大的分布式处理框架,广泛用于批处理和流处理任务。其 checkpoint 机制是确保容错的关键功能,允许在计算过程中保存状态,以便在故障时从最近的 checkpoint 恢复。本文详细探讨了一个 Python 脚本,该脚本…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
