(枚举)(模拟)(前缀和)(数组模拟哈希)(可二分)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配件…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...
