Distance 2023牛客暑期多校训练营6 B
登录—专业IT笔试面试备考平台_牛客网
题目大意:给出两个长度为n的数组a,b,每次操作可以令一个数+1,将a的一个子集A变成和b的一个子集B变成完全相同需要的最少操作数为C(A,B),求对于a的所有子集对所有b的子集的C(A,B)的和
1<=n<=2e3
思路:我们先考察对于整个数组,如何操作使其操作数最少,首先我们需要将数字两两配对,然后分别将每一对数字变成一样的,要想整个数组求出来的最少,每一对数字之间的差就应该最小,所以最优操作就是将整个数组排序。
然后发现最大的时间复杂度是n方,显然不能枚举所有几何,但我们可以枚举每一对数字,因为根据我们上面得出的策略,在每个集合中操作的数对都是相同的,所以我们可以求每一对数组需要的操作数*含有这个数对的集合数量假设我们在长度为7的数组中选中了a[3],b[4],那么根据范德蒙德卷积公式(acm数学(番外1) 范德蒙德卷积公式_Chmaz的博客-CSDN博客)包含他们的区间数就是C(2,2+3)*C(3,3+4),对答案求和即可
//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e3 + 5;
int a[N], b[N];
ll inv[N*2], fac[N*2];
const ll MOD = 998244353;
ll qpow(ll a, ll b)
{a %= MOD;ll ret = 1;while (b){if (b & 1){ret = ret * a % MOD;}a = a * a % MOD;b >>= 1;}return ret;
}
ll C(ll x, ll y)
{return fac[y] * inv[x] % MOD * inv[y - x] % MOD;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;fac[0] = inv[0] = 1;for (int i = 1; i <= 2 * n; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = qpow(fac[i], MOD - 2);}for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}sort(a + 1, a + n + 1);sort(b + 1, b + n + 1);ll ans = 0;for (ll i = 1; i <= n; i++){for (ll j = 1; j <= n; j++){ans = (ans + abs(a[i] - b[j]) * C(min(i - 1, j - 1), i-1 + j-1) % MOD * C(min(n - i, n - j), n - i + n - j) % MOD) % MOD;}}cout << ans << endl;return 0;
}
相关文章:
Distance 2023牛客暑期多校训练营6 B
登录—专业IT笔试面试备考平台_牛客网 题目大意:给出两个长度为n的数组a,b,每次操作可以令一个数1,将a的一个子集A变成和b的一个子集B变成完全相同需要的最少操作数为C(A,B),求对于a的所有子集对所有b的子集的C(A,B)的…...
【Pandas】学习笔记之groupby()、agg()、transform()
在数据分析过程中经常需要对数据集进行分组,并且统计均值,最大值等等。那么 groupby() 的学习就十分有必要了 groupby(): 分组 官方文档: DataFrame.groupby(byNone, axis0, levelNone, as_indexTrue, sortTrue, group_keysTrue, observedF…...
使用正则表达式 移除 HTML 标签后得到字符串
需求分析 后台返回的数据是 这样式的 需要讲html 标签替换 high_light_text: "<span stylecolor:red>OPPO</span> <span stylecolor:red>OPPO</span> 白色 01"使用正则表达式 function stripHTMLTags(htmlString) {return htmlString.rep…...
Java中String方法魔性学习
这里写目录标题 先进行专栏介绍String详解常用构造方法代码演示常用成员方法代码示例总结 先进行专栏介绍 本专栏是自己学Java的旅途,纯手敲的代码,自己跟着黑马课程学习的,并加入一些自己的理解,对代码和笔记 进行适当修改。希望…...
Smartbi 权限绕过漏洞复现(QVD-2023-17461)
0x01 产品简介 Smartbi大数据分析产品融合BI定义的所有阶段,对接各种业务数据库、数据仓库和大数据分析平台,进行加工处理、分析挖掘和可视化展现;满足所有用户的各种数据分析应用需求,如大数据分析、可视化分析、探索式分析、复杂…...
springboot自定义错误消息
为了提供自定义错误消息提示,springboot在resources目录下,有一个文件ValidationMessages.properties 用于存储 验证错误的消息提示: 比如: 这样一个ValidationMessage.properties username.notempty用户名不能为空 username.len…...
微信小程序申请步骤
微信公众平台链接:https://mp.weixin.qq.com/ 1、进到微信公众平台,点一下“点击注册”,挑选账号申请种类“小程序”,填好微信小程序用户信息,包含电子邮箱、登陆密码等。 2、微信公众平台会发送一封电子邮件…...
嘉楠勘智k230开发板上手记录(四)--HHB神经网络模型部署工具
按照K230_AI实战_HHB神经网络模型部署工具.md,HHB文档,RISC-V 编译器和模拟器安装来 一、环境 1. 拉取docker 镜像然后创建docker容器并进入容器 docker pull hhb4tools/hhb:2.4.5 docker run -itd --namehhb2_4 -p 22 "hhb4tools/hhb:2.4.5"…...
微信小程序的自定义TabBar及Vant的使用
一、安装Vant 1、在 资源管理器 空白位置,点右键打开 在外部终端窗口打开 2、初始化NPM npm init -y 3、安装命令 npm i vant/weapp1.3.3 -S --production 4、构建NPM包 在 工具 里选择构建NPM包 5、删除style:v2 在app.json里,删除"style"…...
canvas实现代码雨
学习抖音: 渡一前端必修课 效果图: 全部代码: <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge">&…...
基于MFCC特征提取和HMM模型的语音合成算法matlab仿真
目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022A 3.部分核心程序 ............................................................................ %hmm是已经…...
多重网格算法的cuda编程
这里写自定义目录标题 多重网格算法介绍问题描述——五点差分法求解二维泊松方程五点差分法Gauss迭代算法限制算子介绍提升算子二重网格算法多重网格算法多重网格cuda代码编写串行代码mg.c两重网格cuda并行代码jacobi迭代的cuda编程device_jacobiMakefilecuda_mg.cucuda_mg.hma…...
DP(状态机模型)
大盗阿福 阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。 这条街上一共有 N 家店铺,每家店中都有一些现金。 阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动&#x…...
按照指定的文件顺序进行scp传输
前言 scp 默认传输顺序是按照文件名进行排序的, 但我当前工作中遇到要验证两台机器的神经网络层的精度,需要把网络层的输入输出(假设有100层, 一共64G) 从机器1传输到机器2 , 然后进行对比;这种情况下最好…...
小红书数据分析丨现实版模拟人生,这届网友热衷于“云开店”?
近期,小红书出现的一个神秘的热心群体,他们经常活跃在各种小店店主发布的求助帖评论区中,积极地帮助店主出谋划策,寻找小店经营的优化之道,成功帮助小店成功转亏为盈!江湖人称一一云股东。小红书话题#爱上帮…...
休闲卤味强势崛起:卤味零食成为新一代热门美食
随着人们生活水平的提高和消费观念的转变,休闲卤味逐渐成为了人们日常生活中的热门美食。据最新数据显示,2022年,我国卤味市场销售额达到了约2000亿元,预计到2025年将突破3000亿元大关。其中,休闲卤味以每年10%的速度持…...
自除数-C语言
描述 给定两个整数 left 和 right ,返回一个列表,列表的元素是范围 [left, right] 内所有的 自除数。 1 < left < right < 104 自除数 是指可以被它包含的每一位数整除的数,自除数 不允许包含 0 。例如,128 是一个 自除…...
-bash: ./startup.sh: Permission denied解决
今天在Linux上启动Tomcat,结果弹出:-bash: ./startup.sh: Permission denied 的提示。 这是因为用户没有权限,而导致无法执行。用命令chmod 修改一下bin目录下的.sh权限就可以了。 在Tomcat的bin目录下 ,输入命令行 :c…...
Java课题笔记~ AOP 概述
AOP 简介 AOP(Aspect Orient Programming)面向切面编程。 面向切面编程是从动态角度考虑程序运行过程。 AOP的底层,就是采用动态代理的方式实现的。 采用了两种代理:JDK动态代理、CGLIB动态代理。 JDK动态代理:使…...
真我V3 5G(RMX2200 RMX2201)解锁刷机全过程
安卓系统新Rom包为GSI,更具有通用性,可以比较放心刷。 原厂系统垃圾多、广告多,甚至热点功能不支持ipv6,严重偏离热点机的定位。 主要参考 https://www.bilibili.com/read/cv20730877/https://www.bilibili.com/read/cv2073087…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
