(枚举)(模拟)(前缀和)(数组模拟哈希)(可二分)1236. 递增三元组
目录
题目链接
一些话
流程
套路
ac代码
题目链接
1236. 递增三元组 - AcWing题库
一些话
int f[N];
memset(f,0,sizeof f)影响不到f[N]
所以尽量不要对f[N]赋值,不要用f[N]操作
流程
//由三重暴力i,j,k因为三重暴力底下是分别用i和j,j和k作比较,想到可以拆成i~j,j ~k 再乘起来,
// 但 n < 1e5,双循环复杂度也还是太高,不过还有更优的方法,
// 即枚举b中元素,求b的第k个元素大于a中元素的个数,和b的第k个元素小于c中元素的个数,然后相乘。可以通过前缀和+哈希或二分来实现
// 前缀和+哈希要先统计a和c的元素个数,然后通过前缀和来得到a和c中小于等于某值的元素个数的数组,
// 然后求b的第k个元素大于a中元素的个数就是这个a中小于等于b[k] -1 的元素个数,即s[b[k] - 1]
//b的第k个元素小于c中元素的个数就是c中元素的个数减去c中小于等于b的第k个元素的个数,即s[N-1] - s[b[i]];
套路
统计数组中小于等于多个某值的元素个数:
先哈希统计元素个数,然后前缀和
for(int i = 0;i < n;i++) cnt[a[i]]++;for(int i = 1;i < N;i++) s[i] += s[i-1] + cnt[i];
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N],c[N],cc[N],ca[N],cnt[N],s[N];
int main(){int n;cin >> n;for(int i = 0;i < n;i++) cin >> a[i] , a[i]++;for(int i = 0;i < n;i++) cin >> b[i] , b[i]++;for(int i = 0;i < n;i++) cin >> c[i] , c[i]++;for(int i = 0;i < n;i++) cnt[a[i]]++;for(int i = 1;i < N;i++) s[i] += s[i-1] + cnt[i];for(int i = 0;i < n;i++) ca[i] = s[b[i]-1];memset(s,0,sizeof s);memset(cnt,0,sizeof cnt);for(int i = 0;i < n;i++) cnt[c[i]]++;for(int i = 1;i < N;i++) s[i] += s[i-1] + cnt[i];for(int i = 0;i < n;i++) cc[i] = s[N-1] - s[b[i]];long long ans = 0;for(int i = 0;i < n;i++){ans += ca[i] * (long long) cc[i];}cout << ans << endl;return 0;
}
相关文章:
(枚举)(模拟)(前缀和)(数组模拟哈希)(可二分)1236. 递增三元组
目录 题目链接 一些话 流程 套路 ac代码 题目链接 1236. 递增三元组 - AcWing题库 一些话 int f[N]; memset(f,0,sizeof f)影响不到f[N] 所以尽量不要对f[N]赋值,不要用f[N]操作 流程 //由三重暴力i,j,k因为三重暴力底下是分别用i和j,j和k作比较…...
mysql五种索引类型(实操版本)
为什么使用索引 最近学习了Mysql的索引,索引对于Mysql的高效运行是非常重要的,正确的使用索引可以大大的提高MySql的检索速度。通过索引可以大大的提升查询的速度。不过也会带来一些问题。比如会降低更新表的速度(因为不但要把保存数据还要保…...
微服务进阶之 SpringCloud Alibaba
文章目录微服务进阶🍓SpringCloud 有何劣势?🍓SpringCloud Alibaba 提供了什么?提示:以下是本篇文章正文内容,SpringCloud 系列学习将会持续更新 微服务进阶 🍓SpringCloud 有何劣势࿱…...
前端性能优化笔记2 第二章 度量
相关 Performance API 都在 window.performance 对象下 performance.now() 方法 精度精确到微妙获取的是把页面打开时间点作为基点的相对时间,不依赖操作系统的时间。 部分浏览器不支持 performance.now() 方法,可以用 Date.now() 模拟 performance.n…...
关于new和delete的一些思考,为什么不能在析构函数中调用delete释放对象的内存空间,new和delete的原理
最近在写代码的时候,觉得每次new出来的对象都需要去delete好麻烦,于是直接把delete写到了析构函数中,在析构函数里面写了句delete this,结果调用析构函数的时候死循环了,不是很理解原因,于是去研究了一下。…...
一场以数字技术深度影响和改造传统实业的新风口,正在开启
当数字经济的浪潮开始上演,一场以数字技术深度影响和改造传统实业的新风口,正在开启。对于诸多在互联网时代看似业已走入死胡同的物种来讲,可以说是打开了新的天窗。对于金融科技来讲,同样如此。以往,谈及金融科技&…...
【LeetCode】13. 罗马数字转整数
题目链接:https://leetcode.cn/problems/roman-to-integer/ 📕题目要求: 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 例如, 罗马数字 2 写做 II ,即…...
2023/3/8集合之TreeSet HashSet简介 不含代码
TreeSet : 底层是由TreeMap维护的 无序的,不可重的 底层结构 : 红黑树(平衡二叉树) 特点 : 查询效率高,默认升序排序引用场景 : 适合应用在存储多个单个值的数据的集合,去重的,自动升序排序的场景新增方法:新增了一些与比较大小相关的方法 遍历方式 1)foreach 2)iterator 1测试…...
【面试1v1实景模拟】面试中常见的Java关键字详解
笑小枫专属目录老面👴:Java中有哪些关键字老面👴:简单介绍一下 final 关键字老面👴:简单介绍一下 this、super 关键字老面👴:简单介绍一下 static 关键字老面👴ÿ…...
MySQL8.0.16存储过程比5.7.22性能大幅下降
MySQL8.0.16存储过程比5.7.22性能大幅下降 1、背景 从5.7.22迁移数据库到8.0.16,发现存储过程执行性能大幅下降。原来在5版本上执行只需要3-5秒,到8版本上居然要达到上万秒。 5版本: call Calculation_Week() OK 时间: 3.122s 8版本&#x…...
基于MATLAB的无线信道的传播与衰落(附完整代码与分析)
目录 一. 一般路径损耗模型 1. 1自由环境下路径损耗 1. 2 考虑实际情况 1.3 考虑阴影衰落 二. 代码仿真与理解 (1)函数文件 (2)函数文件 (3)主运行文件 三. 运行结果及理解 3.1 3.2 3.3 一. …...
SDX62如何查看Kernel版本和Operating System Version Patch Level
Kernel版本号方法一:adb shell登录,然后执行uname -a# uname -aLinux sdxlemur 5.4.180-perf #1 PREEMPT Fri Mar 3 04:24:42 UTC 2023 armv7l GNU/Linux方法二:内核源码查看,apps_proc/src/kernel/msm-5.4/Makefile 文件…...
001+limou+HTML——(1)HTML入门知识
000、本人编写前言 前言:本笔记来源于莫振杰的书《HTML、CSS、Javascript从零到一快速上手》,经过修改制成的自学笔记,本书很适合小白学习入门web的相关知识,你也可以先看看我从中学到了什么,再考虑是否去认真学习这本…...
使用Arduino Uno构建一个巡线机器人
使用Arduino Uno构建一个巡线机器人 原文 MX 巡线机器人(**LFR)**是一种简单的自主引导机器人,它遵循在地面上绘制的线来检测白色表面上的暗线或黑暗表面上的白线。在本教程中,使用 Arduino Uno 和一些易于访问的组件构建黑线跟…...
【C++】类和对象(收尾)
文章目录成员变量初始化问题初始化列表explicit关键字static成员特性:友元友元函数友元类内部类特性匿名对象成员变量初始化问题 在创建对象时,编译器通过调用构造函数,给了对象中各个成员变量一个合适的初始值。但是这并不能够称为对对象中成…...
Linux延迟操作
一、软中断Linux内核中定义了如下几种软中断:enum {HI_SOFTIRQ0,TIMER_SOFTIRQ,NET_TX_SOFTIRQ,NET_RX_SOFTIRQ,BLOCK_SOFTIRQ,IRQ_POLL_SOFTIRQ,TASKLET_SOFTIRQ,SCHED_SOFTIRQ,HRTIMER_SOFTIRQ,RCU_SOFTIRQ, /* Preferable RCU should always be the last soft…...
np.insert()函数用法
目录insert()函数定义程序举例说明行插入列插入多数值行插入完整的程序和显示结果:insert()函数定义 insert(arr, obj, values, axisNone) 参数说明: arr : 需要插入的数组,即Input array; obj:向数组中插入值的位置…...
学习笔记-架构的演进之容器的封装-3月day06
文章目录前言封装应用的Dockerwhy Docker not LXC?附前言 当文件系统、访问、资源都可以被隔离后,容器就已经具备它降生所需要的全部前置支撑条件了。为了降低普通用户综合使用 namespaces、cgroups 这些低级特性的门槛,2008 年 Linux Kernel 2.6.24 内…...
Gorm根据关系模型中的属性查询原模型数据
type ExamResult struct {gorm.ModelExamManagementID uintExamManagement ExamManagement json:"examManagement" // 一场考试,其中有试卷,有试题,有试题答案//MarkExamPaperRecord MarkExamPaperRecord //每一场考试对应的结…...
车载技术【USB接口】—Android配件协议AOA【AOA连接】
简述 AOA协议是Google公司推出的用于实现Android设备与外围设备之间USB通信的协议。该协议拓展了Android设备USB接口的功能,为基于Android系统的智能设备应用于数据采集和设备控制领域提供了条件。介绍了Android系统下USB通信的两种模式,并给出了USB配件…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
