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

【每日一题】ARC071D - ### | 前缀和 | 简单

题目内容

原题链接

给定一个长度为 n n n 的数组 a a a 和一个长度为 m m m 的数组 b b b

从数组 a a a 中挑出两个数,作为两条平行于 y y y 轴的直线,数组 b b b 中挑出两个数,作为两条平行于 x x x 轴的直线,问这四条直线构成的矩形的面积。

你需要所有可能的矩形的面积之和,答案对 1 0 9 + 7 10^9+7 109+7 取模

数据范围

  • 2 ≤ n , m ≤ 2 ⋅ 1 0 5 2\leq n,m\leq 2\cdot 10^5 2n,m2105
  • − 1 0 9 ≤ a i , b i ≤ 1 0 9 -10^9\leq a_i,b_i\leq 10^9 109ai,bi109

题解

先对两个数组排序,下标从 0 0 0 开始。

对于数组 a a a ,每个数 a i a_{i} ai,考虑比其小的数的和为 p r e a i − 1 prea_{i-1} preai1,一共有 i i i 个数比 a i a_i ai 小(小于等于),那么和 a i × i − p r e a i − 1 a_i\times i-prea_{i-1} ai×ipreai1

对于数组 b b b 也一样。

但是这里需要考虑的是,对于每个数 a i a_i ai ,其需要与数组 b b b 中任意两个数构成的直线进行计算。

所以考虑 p p r e b i = ∑ j = 0 i b i × p r e b i − 1 ppreb_{i}=\sum\limits_{j=0}^i b_i\times preb_{i-1} pprebi=j=0ibi×prebi1

最后答案就是: ∑ i = 0 n − 1 ( a i × i − p r e a i − 1 ) × p p r e b n − 1 \sum\limits_{i=0}^{n-1} (a_i\times i-prea_{i-1})\times ppreb_{n-1} i=0n1(ai×ipreai1)×pprebn1

时间复杂度: O ( n ) O(n) O(n)

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int MOD = 1e9 + 7;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<ll> a(n), b(m);for (int i = 0; i < n; ++i) cin >> a[i];for (int i = 0; i < m; ++i) cin >> b[i];sort(a.begin(), a.end());sort(b.begin(), b.end());ll prea = (a[0] % MOD + MOD) % MOD;ll preb = (b[0] % MOD + MOD) % MOD, ppreb = 0;for (int i = 1; i < m; ++i) {ppreb += b[i] * i - preb;ppreb = (ppreb % MOD + MOD) % MOD;preb += b[i];preb %= MOD;}ll ans = 0;for (int i = 1; i < n; ++i) {ll cur = ((a[i] * i - prea) % MOD + MOD) % MOD;ans = (ans + cur * ppreb % MOD) % MOD;prea += a[i];prea %= MOD;}cout << ans << "\n";return 0;
}

相关文章:

【每日一题】ARC071D - ### | 前缀和 | 简单

题目内容 原题链接 给定一个长度为 n n n 的数组 a a a 和一个长度为 m m m 的数组 b b b 。 从数组 a a a 中挑出两个数&#xff0c;作为两条平行于 y y y 轴的直线&#xff0c;数组 b b b 中挑出两个数&#xff0c;作为两条平行于 x x x 轴的直线&#xff0c;问这四…...

(Vue2)VueRouter

VueRouter 修改地址栏路径时&#xff0c;切换显示匹配的组件 使用52&#xff1a; 1下载版本3.6.5&#xff08;Vue3对应版本4.X&#xff09; npm add vue-router3.6.5 2引入 import VueRouter from vue-router 3安装注册 Vue.use(VueRouter) 4创建路由对象 const route…...

6.文本注释方法

1.单行注释 在 LaTeX 中&#xff0c;可以使用 % 符号进行单行注释。 2.整段的注释 但如果要注释一整段文字&#xff0c;可以使用 comment 宏包或 \iffalse 和 \fi 命令来实现。 2.1 使用 comment 宏包 在导言区使用 \usepackage{comment} 命令加载 comment 宏包。然后&…...

[Linux打怪升级之路]-缓冲区

前言 作者&#xff1a;小蜗牛向前冲 名言&#xff1a;我可以接受失败&#xff0c;但我不能接受放弃 如果觉的博主的文章还不错的话&#xff0c;还请点赞&#xff0c;收藏&#xff0c;关注&#x1f440;支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 本期学习目标&…...

【力扣】13. 罗马数字转整数

题目描述 罗马数字包含以下七种字符: I&#xff0c; V&#xff0c; X&#xff0c; L&#xff0c;C&#xff0c;D 和 M。 字符数值I1V5X10L50C100D500M1000 例如&#xff0c; 罗马数字 2 写做 II &#xff0c;即为两个并列的 1 。12 写做 XII &#xff0c;即为 X II 。 27 写…...

高效时间管理,事无巨细掌握——OmniFocus Pro 3 for Mac最强GTD工具

在快节奏的现代生活中&#xff0c;有效地管理和安排时间变得至关重要。如果您正在寻找一款功能强大的时间管理工具&#xff0c;那么OmniFocus Pro 3 for Mac将是您的最佳选择。作为一款专业的GTD&#xff08;Getting Things Done&#xff09;应用程序&#xff0c;它为您提供了一…...

解锁前端Vue3宝藏级资料 第五章 Vue 组件应用 3( Slots )

5.4 Slots 我们已经了解到组件能够接收任意类型的 JavaScript 值作为 props&#xff0c;但组件要如何接收模板内容呢&#xff1f;在某些场景中&#xff0c;我们可能想要为子组件传递一些模板片段&#xff0c;让子组件在它们的组件中渲染这些片段。Slots 可用于将Html内容从父组…...

接口测试之文件上传

在日常工作中&#xff0c;经常有上传文件功能的测试场景&#xff0c;因此&#xff0c;本文介绍两种主流编写上传文件接口测试脚本的方法。 首先&#xff0c;要知道文件上传的一般原理&#xff1a;客户端根据文件路径读取文件内容&#xff0c;将文件内容转换成二进制文件流的格…...

7.Flask-Migrate数据库迁移

基本介绍 flask-migrate是基于Alembic的一个封装,并集成到Flask中 所有的迁移操作其实都是Alembic做的,能跟踪模型的变化,并将变化映射到数据库中 一.安装 pip install flask-migrate二.基本使用 2.1初始化数据库迁移脚本 在Flask应用的根目录下&#xff0c;运行命令 flas…...

信创办公–基于WPS的PPT最佳实践系列 (项目8创建电子相册)

信创办公–基于WPS的PPT最佳实践系列 &#xff08;项目8创建电子相册&#xff09; 目录 应用背景操作步骤 应用背景 如果我们想把图片弄成相册&#xff0c;或者弄成一段有音乐的视频分享给朋友。我们可以利用PPT来制作。那我们如何用PPT制作电子相册或视频呢&#xff1f;可以跟…...

JRedis的基本操作,基本数据类型操作

Redis的基本数据类型&#xff1a; stringhashlistsetzset {public static void main(String[] args) {Jedis jedis new Jedis("127.0.0.1", 6379);// stringjedis.set("hello", "word");String hello jedis.get("hello");System.o…...

QT网页 webengine / CEF

QT WebEngine 官方文档 WebEngine 架构&#xff1a; 能看到 WebEngine 有一个核心模块是基于 Chromium 构造的&#xff0c;通过使用 Chromium 的Blink渲染引擎和V8 JavaScript引擎来处理和渲染Web内容&#xff0c;并将这些底层技术封装为一系列高级的C类和接口&#xff0c;以…...

Golang笔试题:编写一个函数,接收一个整数参数n,输出n的阶乘结果

今天&#xff0c;我们开发的AI笔试题工具&#xff0c;ai扁食——AI程序员笔试系统给我出了中级Golang题目&#xff0c;就是这道题&#xff1a;《请编写一个函数&#xff0c;接收一个整数参数n&#xff0c;输出n的阶乘结果》&#xff0c;希望我写一个函数&#xff0c;输出n的阶乘…...

外包干了2个月,技术退步明显.......

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...

无涯教程-JavaScript - BINOM.DIST函数

描述 BINOM.DIST函数返回单个项二项式分布概率。 在具有固定数量的测试或试验的问题中使用BINOM.DIST。 当任何试验的输出只是成功或失败时 试验是独立的,并且 在整个实验中成功的概率不变的情况 语法 BINOM.DIST (number_s,trials,probability_s,cumulative)争论 Argu…...

linux定时重启tomcat

1.编辑重启Tomcat命令 首先编辑一个文件 vi my_restart.sh 然后输入&#xff1a; #!/bin/bash . /etc/profile tomcatPath"/opt/finereport/tomcat" binPath"$tomcatPath/bin" echo "[info][$(date %F %H:%M:%S)]正在监控tomcat&#xff0c;路径&a…...

在静态方法中访问@Value注入的静态变量!!

一、 静态变量 static修饰的成员变量&#xff0c;称为静态成员变量&#xff0c;静态成员变量最大的特性&#xff1a;不属于某个具体的对象&#xff0c;是所有对象所共享的 简单来说&#xff1a;在某些类的对象中存在一些相同的成员变量&#xff0c;那么这种成员变量就可以设置…...

掌握这些算法,让你的编程之路更顺畅——重要算法解析

一个程序员一生中可能会邂逅各种各样的算法&#xff0c;但总有那么几种&#xff0c;是作为一个程序员一定会遇见且大概率需要掌握的算法。这些算法通常被广泛应用于日常编程工作中&#xff0c;是提升编程效率和解决实际问题的重要工具。本文将介绍几种十分重要的“必抓&#xf…...

flink集群与资源@k8s源码分析-总述

1 简介 集群和资源模块提供动态资源能力,是分布式系统关键基础设施,分布式datax,分布式索引,事件引擎都需要集群和资源的弹性资源能力,提高伸缩性和作业处理能力。本文分析flink的集群和资源的k8s模块,深入了解其设计原理,为开发自有的集群和资源组件做技术准备, 同时涉…...

LeetCode 0213. 打家劫舍 II:动动态规划

【LetMeFly】213.打家劫舍 II&#xff1a;动动态规划 力扣题目链接&#xff1a;https://leetcode.cn/problems/house-robber-ii/ 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味…...

VMware17 不可恢复错误mks解决方案

用的虚拟机VMware17版本&#xff0c;然后运行带HDR的unity程序&#xff0c;结果报错 网上找了很多解决方案&#xff0c;都没用。毕竟需要在不放弃虚拟机3D加速的情况下运行。 最终皇天不负有心人&#xff0c;亲测有效的方法&#xff1a; 在虚拟机名字.vmx文件里添加以下2行&a…...

【深度学习】 Python 和 NumPy 系列教程(廿五):Matplotlib详解:3、多子图和布局:subplot()函数

目录 一、前言 二、实验环境 三、Matplotlib详解 1、2d绘图类型 2、3d绘图类型 3、多子图和布局 1. subplot()函数 简单示例 一、前言 Python是一种高级编程语言&#xff0c;由Guido van Rossum于1991年创建。它以简洁、易读的语法而闻名&#xff0c;并且具有强大的功能…...

计算机网络知识补充(1)

计算机网络:是一个将分散的&#xff0c;具有独立功能的计算机系统&#xff0c;通过通信设备和线路进行连接起来&#xff0c;由功能完善的软件实现资源共享和信息共享的系统&#xff0c;计算机网络是互连的&#xff0c;自治的计算机集合 互连:通过通信链路来进行互联互通 自治:没…...

C# Onnx Yolov8 Pose 姿态识别

效果 项目 代码 using Microsoft.ML.OnnxRuntime; using Microsoft.ML.OnnxRuntime.Tensors; using OpenCvSharp; using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System…...

7.algorithm2e中while怎么使用

algorithm2e中while怎么使用 在 algorithm2e 宏包中&#xff0c;要使用 while 循环&#xff0c;您可以使用 \While 和 \EndWhile 命令来定义循环的开始和结束。以下是如何使用 while 循环的示例&#xff1a; \documentclass{article} \usepackage[linesnumbered,boxed]{algorit…...

Flask狼书笔记 | 08_个人博客(下)

文章目录 8 个人博客8.4 初始化博客8.5 使用Flask-Login管理用户认证8.6 CSRFProtect实现CSRF保护8.7 编写博客后台小结 8 个人博客 8.4 初始化博客 1、安全存储密码 密码不要以明文的形式直接存储在数据库中&#xff0c;以防被攻击者盗取、泄露。一般的做法是&#xff0c;不…...

机器学习第十课--提升树

一.Bagging与Boosting的区别 在上一章里我们学习了一个集成模型叫作随机森林&#xff0c;而且也了解到随机森林属于Bagging的成员。本节我们重点来学习一下另外一种集成模型叫作Boosting。首先回顾一下什么叫Bagging? 比如在随机森林里&#xff0c;针对于样本数据&#xff0c;…...

react scss.modules中使用iconfont

全局引入详见全局引入scss 全局的scss文件中引入iconfont.css use "../font/iconfont.css"; 然后就可以正常使用啦...

使用Jmeter+ant进行接口自动化测试(数据驱动)

最近在做接口测试&#xff0c;因为公司有使用jmeter做接口测试的相关培训资料&#xff0c;所以还是先选择使用jmeter来批量管理接口&#xff0c;进行自动化测试。话不多说&#xff0c;进入正题&#xff1a; 1.使用csv文件保存接口测试用例&#xff0c;方便后期对接口进行维护&…...

可视化图表组件之股票数据分析应用

股市是市场经济的必然产物&#xff0c;在一个国家的金融领域之中有着举足轻重的地位。在过去&#xff0c;人们对于市场走势的把握主要依赖于经验和直觉&#xff0c;往往容易受到主观因素的影响&#xff0c;导致决策上出现偏差。如今&#xff0c;通过数据可视化呈现&#xff0c;…...

网站建设公司官网/舆情管理

1 docker数据卷之docker volume2 3 docker中数据卷其实就类似于虚拟机的虚拟磁盘&#xff0c;在虚拟机的虚拟磁盘的使用过程中&#xff0c;我们可以将本地的磁盘文件或目录挂载4 到这个虚拟磁盘上&#xff0c;从而完成对本机数据的读写。5 6 7 docker数据卷的创建可以在创建这个…...

做网站周记/软文营销的作用有哪些

转载于:https://www.cnblogs.com/yymn/p/4504143.html...

帮人做兼职的网站吗/北京建站

排序和搜索是数据结构和算法学习中的两个最基本的操作。关于排序&#xff0c;我在上一篇已经做了比较详细的介绍&#xff0c;请参考 http://www.cnblogs.com/chenxizhang/archive/2009/04/22/1441209.html 这一篇我们来关注一下搜索。我们同样把目光放在Array这个最基础的数据类…...

张家界做网站找哪家好/网络推广网站排行榜

Android R关键流程 Android R Ims Boot Init Android R 手动搜网之网络上报流程 Android R MT Call Notification流程时序图 Android Q关键流程 Android Q MO Call Android Q MT Call Android Q 会议电话上报 Android Q 通话状态上报 Android Q 通话控制下发 Android Q Init…...

网站链接怎么做/百度权重工具

MySQL以以下规则描述比较操作如何进行转换&#xff1a;两个参数至少有一个是 NULL 时&#xff0c;比较的结果也是 NULL&#xff0c;例外是使用 <> 对两个 NULL 做比较时会返回 1&#xff0c;这两种情况都不需要做类型转换两个参数都是字符串&#xff0c;会按照字符串来比…...

优化网站费用/百度推广每年600元什么费用

以下是emul的鏈接:ed2k://|file|Devexpress.XPO.v1.6.3015.for.MSVS2k3.NET-FPE.rar|2153540|5D3347A713C61B2EAC82B463D4C50A50|h4EJSH4MD2WBFZITYDLXFG7BITSZQKGLA|/好像就是加了多幾種數據的支持&#xff0c;如MYSQL之類。转载于:https://www.cnblogs.com/chinaver2002/arch…...