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

牛客周赛 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

首先,标黄色的元素的值是确定的。

其次,我们依次来看:

  1. 72,在此处,可以选择 8,9,10。即,有三种选择。(这里表示第二个 7,其他相同形式同理)
  2. 73,在此处,可以选择 8,9,10。但是,这时已经在 72处使用过一个元素,还有两种选择可用。
  3. 52,在此处,可以选择 6,8,9,10。但是,这时已经在 72 和 73 处使用过两个元素,还有两种选择可用。
  4. 依次类推…

对于一个方案,在某元素 x:

  1. 如果第一次出现时,该元素在只能在此处,在此处贡献一种组合的可能。
  2. 如果元素 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&#xff08;思维、差分、树状数组、大根堆、前后缀、递归&#xff09;A. 夹心饼干B. C. 食堂大作战&#xff08;思维&#xff09;D. 小苯的排列计数(差分、树状数组)E. 和和&#xff08;大根堆&#xff0c;前缀和&#xff09;F. 怎么写线性SPJ &…...

MQTT实现智能家居------2、写MQTT程序的思路

举个最简单的例子&#xff1a; 手机------服务器-------家具 我们这里只看手机和家具的客户端&#xff1a; 手机&#xff1a;1&#xff09;需要连接服务器 2&#xff09;需要发布指令给服务器到家里的家具 3&#xff09;接受来自于家里家具的异常状况 4&#xff09;保持心…...

大模型面试问题准备

1. BERT的多头注意力为什么需要多头&#xff1f; 为了捕捉不同子空间的语义信息&#xff0c;每个头关注不同的方面&#xff0c;增强模型的表达能力 2. 什么是softmax上下溢出问题&#xff1f; 问题描述&#xff1a; 上溢出&#xff1a;ye^x中&#xff0c;如果x取非常大的正数…...

C语言:二维数组在内存中是怎么存储的

目录 1. 二维数组的定义&#xff1a; 2. 行主序存储&#xff1a; 具体内存排列&#xff1a; 3. 如何通过指针访问数据&#xff1a; 4. 总结&#xff1a; 在 C 语言中&#xff0c;二维数组是按 行主序&#xff08;row-major order&#xff09; 存储的。也就是说&#xff0c…...

AI时代前端开发技能变革与ScriptEcho:拥抱AI,提升效率

在飞速发展的科技浪潮中&#xff0c;人工智能&#xff08;AI&#xff09;正以前所未有的速度改变着各个行业&#xff0c;前端开发领域也不例外。曾经被认为是核心竞争力的传统前端技能&#xff0c;例如精通HTML、CSS和JavaScript&#xff0c;其价值正在发生微妙的变化。 得益于…...

计算机毕业设计SpringBoot+Vue.js美容院管理系统(源码+文档+PPT+讲解)

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…...

【LeetCodehHot100_0x01】

LeetCodeHot100_0x01 1. 两数之和 解题思路&#xff1a; 暴力枚举法、哈希法 【暴力枚举】 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浏览器同源策略 浏览器的同源策略 &#xff08; Same-origin policy &#xff09;是一种重要的安全机制&#xff0c;用于限制一个源&#xff08; origin &#xff09;的文档或 脚本如何与另一个源的资源进行…...

4-知识图谱的抽取与构建-4_2实体识别与分类

&#x1f31f; 知识图谱的实体识别与分类&#x1f525; &#x1f50d; 什么是实体识别与分类&#xff1f; 实体识别&#xff08;Entity Recognition&#xff09;是从文本中提取出具体的事物&#xff0c;如人名、地名、组织名等。分类&#xff08;Entity Classification&#x…...

腾讯云大模型知识引擎×DeepSeek赋能文旅

腾讯云大模型知识引擎DeepSeek赋能文旅 ——以合肥文旅为例的技术革新与实践路径 一、技术底座&#xff1a;知识引擎与DeepSeek的融合逻辑 腾讯云大模型知识引擎与DeepSeek模型的结合&#xff0c;本质上是**“知识库检索增强生成&#xff08;RAG&#xff09;实时联网能力”**…...

TMDS视频编解码算法

因为使用的是DDR进行传输&#xff0c;即双倍频率采样&#xff0c;故时钟只用是并行数据数据的5倍&#xff0c;而不是10倍。 TMDS算法流程&#xff1a; 视频编码TMDS算法流程实现&#xff1a; timescale 1 ps / 1ps //DVI编码通常用于视频传输&#xff0c;将并行数据转换为适合…...

C++程序员内功修炼——Linux C/C++编程技术汇总

在软件开发的宏大版图中&#xff0c;C 语言宛如一座巍峨的高山&#xff0c;吸引着无数开发者攀登探索。而 Linux 操作系统&#xff0c;以其开源、稳定、高效的特性&#xff0c;成为了众多开发者钟爱的开发平台。将 C 与 Linux 相结合&#xff0c;就如同为开发者配备了一把无坚不…...

【数据结构】链表中快指针和慢指针

目录 一、找出并返回链表的中间结点 二、输出链表中倒数第k个结点 三、判断链表中是否有环 四、两个单链表相交 一、找出并返回链表的中间结点 给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 要求&#xff1a;只遍历…...

6_zookeeper集群配置

配置 一、配置myid文件 # 进入解压好的文件夹下面 touch myid vim myid # master节点写0&#xff0c;slave1节点写1&#xff0c;slave2节点写2二、配置zoo.cfg文件 1.在master节点编辑zookeeper配置文件 # 进入解压好的文件夹下面 cd conf/ cp zoo_sample.cfg zoo.cfg vim …...

Docker核心概念

容器介绍 Docker 是世界领先的软件容器平台&#xff0c;所以想要搞懂 Docker 的概念我们必须先从容器开始说起。 什么是容器? 先来看看容器较为官方的解释 一句话概括容器&#xff1a;容器就是将软件打包成标准化单元&#xff0c;以用于开发、交付和部署。 容器镜像是轻量…...

LD_PRELOAD 绕过 disable_function 学习

借助这位师傅的文章来学习通过LD_PRELOAD来绕过disable_function的原理 【PHP绕过】LD_PRELOAD bypass disable_functions_phpid绕过-CSDN博客 感谢这位师傅的贡献 介绍 静态链接&#xff1a; &#xff08;1&#xff09;举个情景来帮助理解&#xff1a; 假设你要搬家&#x…...

如何用JAVA实现布隆过滤器?

目录 引言 布隆过滤器的原理 1. 核心思想 2. 优缺点 布隆过滤器的使用场景 Java 实现布隆过滤器 1. 实现步骤 2. 代码实现 3. 代码说明 4. 测试结果 布隆过滤器的优化 总结 引言 布隆过滤器&#xff08;Bloom Filter&#xff09;是一种高效的概率数据结构&#xff0…...

游戏开发 游戏开始界面

目录 前言 一 游戏初始化界面的分析 二 游戏的大概框架 三 显示界面的开发 四 完整代码 总结 我们可以来看看游戏初始界面是什么样的 勇士游戏样例 前言 这里是开发游戏的初始界面 一 游戏初始化界面的分析 我们需要一个背景图&#xff0c;开始游戏图标&#xff0…...

Python解析 Flink Job 依赖的checkpoint 路径

引言 Apache Flink 是一个强大的分布式处理框架&#xff0c;广泛用于批处理和流处理任务。其 checkpoint 机制是确保容错的关键功能&#xff0c;允许在计算过程中保存状态&#xff0c;以便在故障时从最近的 checkpoint 恢复。本文详细探讨了一个 Python 脚本&#xff0c;该脚本…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...