2023thupc总结
A 大富翁
很有意思的题
∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx\sum_{x\in A}\sum_{y\in B}[x支配y]-\sum_{x\in A}\sum_{y\in B}[y支配x]-\sum_{x\in A}w_x∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx
=∑x∈A∑y[x支配y]−∑x∈A∑y[y支配x]−∑x∈Awx=\sum_{x\in A}\sum_{y}[x支配y]-\sum_{x\in A}\sum_{y}[y支配x]-\sum_{x\in A}w_x=∑x∈A∑y[x支配y]−∑x∈A∑y[y支配x]−∑x∈Awx
=∑x∈Asizx−∑x∈Adepx−∑x∈Awx=\sum_{x\in A}siz_x-\sum_{x\in A}dep_x-\sum_{x\in A}w_x=∑x∈Asizx−∑x∈Adepx−∑x∈Awx
这样每个点的贡献就确定了
排序后取奇数位
C 快速最小公倍数变换
考虑把贡献改写成一个只跟rir_iri相关,只跟rjr_jrj相关,只跟ri+rjr_i+r_jri+rj相关的三个数的乘积
设vp(x)v_p(x)vp(x)表示质数ppp在xxx质因数分解中的指数大小,MpM_pMp表示所有vp(ai)v_p(a_i)vp(ai)的最大值,mpm_pmp所有vp(ai)v_p(a_i)vp(ai)的非严格次大值
考虑算出MpM_pMp在操作之后的改变值ΔMp\Delta M_pΔMp
ΔMp=([vp(ri)=Mp]+[vp(rj)=Mp])(mp−Mp)+max(vp(ri+rj)−Mp,0)\Delta M_p=([v_p(r_i)=M_p]+[v_p(r_j)=M_p])(m_p-M_p)+\max(v_p(r_i+r_j)-M_p,0)ΔMp=([vp(ri)=Mp]+[vp(rj)=Mp])(mp−Mp)+max(vp(ri+rj)−Mp,0)
证明
当[vp(ri)=Mp]=0,[vp(rj)=Mp]=0[v_p(r_i)=M_p]=0,[v_p(r_j)=M_p]=0[vp(ri)=Mp]=0,[vp(rj)=Mp]=0时,显然满足
当[vp(ri)=Mp]=1,[vp(rj)=Mp]=0[v_p(r_i)=M_p]=1,[v_p(r_j)=M_p]=0[vp(ri)=Mp]=1,[vp(rj)=Mp]=0时,vp(ri+rj)=vp(rj)<Mpv_p(r_i+r_j)=v_p(r_j)<M_pvp(ri+rj)=vp(rj)<Mp,满足
当[vp(ri)=Mp]=0,[vp(rj)=Mp]=1[v_p(r_i)=M_p]=0,[v_p(r_j)=M_p]=1[vp(ri)=Mp]=0,[vp(rj)=Mp]=1时,与上种情况类似
当[vp(ri)=Mp]=1,[vp(rj)=Mp]=1[v_p(r_i)=M_p]=1,[v_p(r_j)=M_p]=1[vp(ri)=Mp]=1,[vp(rj)=Mp]=1时,mp=Mpm_p=M_pmp=Mp,满足
然后就能用nttnttntt优化了
相关文章:
2023thupc总结
A 大富翁 很有意思的题 ∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx\sum_{x\in A}\sum_{y\in B}[x支配y]-\sum_{x\in A}\sum_{y\in B}[y支配x]-\sum_{x\in A}w_x∑x∈A∑y∈B[x支配y]−∑x∈A∑y∈B[y支配x]−∑x∈Awx ∑x∈A∑y[x支配y]−∑x∈A∑y[y支…...

【数据库】MySQL数据库基础
目录 1.数据库: 2.数据库基本操作 2.1 MySQL的运行原理 2.2显示数据库: 2.3创建数据库 2.4使用数据库 2.5删除数据库 3.常见的数据类型 3.1数值类型: 3.2字符型类型 3.3日期类型 4.表的操作 4.1创建表 4.2查看表 4.3删除表 5.汇总…...

grid了解
结构 <div class"grid"><div>1</div><div>2</div><div>3</div><div>4</div><div>5</div><div>6</div><div>7</div><div>8</div><div>9</div>&l…...
2023年全国最新工会考试精选真题及答案13
百分百题库提供工会考试试题、工会考试预测题、工会考试真题、工会证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 81.女职工委员会在()下开展工作。 A.企业工会委员会领导 B.企业工会委员会指导 …...

初识HTML技术
文章目录一、为什么学习前端?二、第一个HTML文件VSCode三. HTML元素四. HTML页面一、为什么学习前端? 我们作为一个后端程序员,为什么还要学习前端,因为我们的终极目的是实现web开发,搭建网站,网站 前端 后端 比如我们随便…...
我们为什么要用消息队列?
消息队列是系统设计中存在时间最长的中间件之一,从系统有通信需求开始,就产生了消息队列。 消息队列的使用场景 在日常系统设计与实现的过程中,下面3种场景会涉及到消息队列: 异步处理流量控制服务解耦 异步处理 典型的应用场…...

Linux进程控制
进程控制fork函数进程终止退出码常见的退出方式进程等待什么是进程等待,为什么要进程等待阻塞与非阻塞进程替换替换原理替换函数执行系统命令执行自己写的程序模拟实现简易的shellfork函数 fork函数是创建一个子进程,之前用过。 #include <unistd.h…...

PMP项目管理引论介绍
目录1. 指南概述和目的1.1 项目管理标准1.2 道德与专业行为规范2 基本要素2.1 项目2.2 项目管理的重要性2.3 项目、项目集、项目组合以及运营管理之间的关系2.3.1 概述2.3.2. 项目组合与项目集管理2.3.3. 运营管理2.3.4. 组织级项目管理和战略2.3.5. 项目管理2.3.6. 运营管理与…...

计算机视觉废钢堆提取问题
计算机视觉废钢堆提取问题 背景介绍 在钢铁炼制中,废钢是非常重要的原料,不同等级废钢对于钢成品影响很大,因此需要对废钢进行正确分类。某废钢料场中,卸料区域布置了多个摄像头,用于拍摄卸料场中废钢堆,…...
判断水仙花数-课后程序(Python程序开发案例教程-黑马程序员编著-第二章-课后作业)
实例5:判断水仙花数 水仙花数是一个3位数,它的每位数字的3次幂之和等于它本身,例如13 53 33 153,153就是一个水仙花数。 本实例要求编写程序,实现判断用户输入的3位数是否为水仙花数的功能。 实例目标 掌握Pytho…...

目标检测: 数据增强代码详解
1. 常见的数据增强 1.1 翻转图像 左右水平翻转 假设图片的宽高为w,h,bdbox左上角A坐标为(x1,y1), 右下角B为(x2,y2)。经过左右水平翻转后,bdbox的左上角A1坐标(w-x2,y1) ,右下角B1坐标为(w-x1,y2)左右水平翻转的代码实现如下:from PIL import Image image = Image.open(i…...

第二讲:ambari编译复盘,如何实现一次性成功编译ambari
上节课我们已经讲解了如何成功编译ambari源码,安装ambari-server rpm包以及成功部署ambari。本节课我们来复盘一下上节课的编译过程,以及思考如何实现一次性成功编译ambari。 要想一次性成功编译ambari,那么就需要将预置工作做好,比如: maven镜像源配置,node_moudle模块…...

Windows下jdk安装与卸载-超详细的图文教程
jdk安装 下载jdk 由于现在主流就是jdk1.8,所以这里就下载jdk1.8进行演示。官方下载地址:https://www.oracle.com/java/technologies/downloads/#java8-windows。 官方下载需要注册oracle账号,国内下载有可能速度慢,若不想注册账…...

Jackson CVE-2018-5968 反序列化漏洞
0x00 前言 同CVE-2017-15095一样,是CVE-2017-7525黑名单绕过的漏洞,主要还是看一下绕过的调用链利用方式。 可以先看: Jackson 反序列化漏洞原理 或者直接看总结也可以: Jackson总结 影响版本:至2.8.11和2.9.x至…...
解析MySQL 8.0 OCP(1Z0-908)考试中一道大部分同学都会做错的题目
一个用户有下面的权限: mysql>SHOW GRANTS FOR jsmith;---------------------------------------------------------------------- | Grants for jsmith% | ----------------------------------------------------------…...
Java死锁
什么是死锁? 多个线程同时被阻塞,它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞,因此程序不可能正常终止。 死锁的必要条件: 1、互斥条件:该资源任意一个时刻只由一个线程占用。 2、请求与…...

BloomFilter原理学习
文章目录BloomFilter简单介绍BloomFilter中的数学知识fpp(误判率/假阳性)的计算k的最小值公式总结编程语言实现golang的实现[已知n, p求m和k](https://github.com/bits-and-blooms/bloom/blob/master/bloom.go#L133)参考BloomFilter简单介绍 BloomFilter我们可能经常听到也在使…...
C语言老题新解第1-5题
文章目录1 互不相同且无重复数字2 企业利润提成3 两个完全平方数4 判断一年的第几天5 三个整数比较大小1 互不相同且无重复数字 1 有1, 2, 3, 4四个数字,能组成多少互不相同且无重复数字的三位数?都是多少? 最简单当然是三重循环嵌套在一起…...

【数据库系列】MQSQL历史数据分区
互联网行业企业都倾向于mysql数据库,虽说mysql单表能支持亿级别的数据量,加上索引优化下查询速度,勉强能使用,但是对于追求性能和效率的互联网企业,这是远远不够的。Mysql数据库单表数据量到达500万左右,达…...
MyBatis常用的俩种分页方式
1、使用 limit 实现分页 select * from xxx limit m,n # m 表示从第几条数据开始,默认从0开始 # n 表示查询几条数据 select * from xxx limit 2,3 # 从索引为2的数据开始,往后查询三个。2、3、4 (1) 创建分页对象,用来封装分页的数据 PS…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...