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

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_xxAyB[x支配y]xAyB[y支配x]xAwx
=∑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=xAy[x支配y]xAy[y支配x]xAwx
=∑x∈Asizx−∑x∈Adepx−∑x∈Awx=\sum_{x\in A}siz_x-\sum_{x\in A}dep_x-\sum_{x\in A}w_x=xAsizxxAdepxxAwx
这样每个点的贡献就确定了
排序后取奇数位

C 快速最小公倍数变换
考虑把贡献改写成一个只跟rir_iri相关,只跟rjr_jrj相关,只跟ri+rjr_i+r_jri+rj相关的三个数的乘积
vp(x)v_p(x)vp(x)表示质数pppxxx质因数分解中的指数大小,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])(mpMp)+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∈A​wx​ ∑x∈A∑y[x支配y]−∑x∈A∑y[y支…...

【数据库】MySQL数据库基础

目录 1.数据库&#xff1a; 2.数据库基本操作 2.1 MySQL的运行原理 2.2显示数据库&#xff1a; 2.3创建数据库 2.4使用数据库 2.5删除数据库 3.常见的数据类型 3.1数值类型&#xff1a; 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

百分百题库提供工会考试试题、工会考试预测题、工会考试真题、工会证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 81.女职工委员会在&#xff08;&#xff09;下开展工作。 A.企业工会委员会领导 B.企业工会委员会指导 …...

初识HTML技术

文章目录一、为什么学习前端?二、第一个HTML文件VSCode三. HTML元素四. HTML页面一、为什么学习前端? 我们作为一个后端程序员&#xff0c;为什么还要学习前端&#xff0c;因为我们的终极目的是实现web开发&#xff0c;搭建网站&#xff0c;网站 前端 后端 比如我们随便…...

我们为什么要用消息队列?

消息队列是系统设计中存在时间最长的中间件之一&#xff0c;从系统有通信需求开始&#xff0c;就产生了消息队列。 消息队列的使用场景 在日常系统设计与实现的过程中&#xff0c;下面3种场景会涉及到消息队列&#xff1a; 异步处理流量控制服务解耦 异步处理 典型的应用场…...

Linux进程控制

进程控制fork函数进程终止退出码常见的退出方式进程等待什么是进程等待&#xff0c;为什么要进程等待阻塞与非阻塞进程替换替换原理替换函数执行系统命令执行自己写的程序模拟实现简易的shellfork函数 fork函数是创建一个子进程&#xff0c;之前用过。 #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. 运营管理与…...

计算机视觉废钢堆提取问题

计算机视觉废钢堆提取问题 背景介绍 在钢铁炼制中&#xff0c;废钢是非常重要的原料&#xff0c;不同等级废钢对于钢成品影响很大&#xff0c;因此需要对废钢进行正确分类。某废钢料场中&#xff0c;卸料区域布置了多个摄像头&#xff0c;用于拍摄卸料场中废钢堆&#xff0c;…...

判断水仙花数-课后程序(Python程序开发案例教程-黑马程序员编著-第二章-课后作业)

实例5&#xff1a;判断水仙花数 水仙花数是一个3位数&#xff0c;它的每位数字的3次幂之和等于它本身&#xff0c;例如13 53 33 153&#xff0c;153就是一个水仙花数。 本实例要求编写程序&#xff0c;实现判断用户输入的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&#xff0c;所以这里就下载jdk1.8进行演示。官方下载地址&#xff1a;https://www.oracle.com/java/technologies/downloads/#java8-windows。 官方下载需要注册oracle账号&#xff0c;国内下载有可能速度慢&#xff0c;若不想注册账…...

Jackson CVE-2018-5968 反序列化漏洞

0x00 前言 同CVE-2017-15095一样&#xff0c;是CVE-2017-7525黑名单绕过的漏洞&#xff0c;主要还是看一下绕过的调用链利用方式。 可以先看&#xff1a; Jackson 反序列化漏洞原理 或者直接看总结也可以&#xff1a; Jackson总结 影响版本&#xff1a;至2.8.11和2.9.x至…...

解析MySQL 8.0 OCP(1Z0-908)考试中一道大部分同学都会做错的题目

一个用户有下面的权限: mysql>SHOW GRANTS FOR jsmith;---------------------------------------------------------------------- | Grants for jsmith% | ----------------------------------------------------------…...

Java死锁

什么是死锁&#xff1f; 多个线程同时被阻塞&#xff0c;它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞&#xff0c;因此程序不可能正常终止。 死锁的必要条件&#xff1a; 1、互斥条件&#xff1a;该资源任意一个时刻只由一个线程占用。 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四个数字&#xff0c;能组成多少互不相同且无重复数字的三位数&#xff1f;都是多少&#xff1f; 最简单当然是三重循环嵌套在一起…...

【数据库系列】MQSQL历史数据分区

互联网行业企业都倾向于mysql数据库&#xff0c;虽说mysql单表能支持亿级别的数据量&#xff0c;加上索引优化下查询速度&#xff0c;勉强能使用&#xff0c;但是对于追求性能和效率的互联网企业&#xff0c;这是远远不够的。Mysql数据库单表数据量到达500万左右&#xff0c;达…...

MyBatis常用的俩种分页方式

1、使用 limit 实现分页 select * from xxx limit m,n # m 表示从第几条数据开始&#xff0c;默认从0开始 # n 表示查询几条数据 select * from xxx limit 2,3 # 从索引为2的数据开始&#xff0c;往后查询三个。2、3、4 (1) 创建分页对象&#xff0c;用来封装分页的数据 PS…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...