(枚举)(模拟)(前缀和)(数组模拟哈希)(可二分)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配件…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
