首页 > 其他分享 >[JOI Open 2024] 中暑

[JOI Open 2024] 中暑

时间:2024-06-19 19:59:02浏览次数:20  
标签:后缀 text sum 位置 2024 实际上 放满 JOI Open

原问题的规则实际上很大程度上是为最小化而设计的,但是我们却要求的是最大化,这意味着原问题的规则实际上是与我们要最优化的问题相矛盾,可行的办法可能是通过一些转化使新问题与规则刚好契合。

考虑原问题的规则实际上告诉我们只有当两边都不能放的时候才会对答案产生贡献,意味着实际上最优化的其实是尽可能制造两边都满的位置,第 \(i\) 条路上的人会产生贡献当且仅当 \(i\) 与 \(i+1\) 都被放满。

实际上可以发现这样的转化是非常好的,如果我们无视一个位置放满了就不能再被放的限制,问题的结果不会发生改变,这是因为如果一个位置放满了再继续放,这样不如放一个没有放满的位置,这样会使位置变得更加满从而使得答案尽可能的最大化。这意味着原问题的规则在转化问题中就是用来最大化,这是非常契合的。

考虑如果确定好了每一个位置被占据的时间 \(t_{i}\),则第 \(i\) 条道路上的人会产生贡献当且仅当其到达时间比 \(\max(t_{i},t_{i+1})\) 要大。这样如果 \(t\) 序列确定,答案也就确定了。

考虑怎样的 \(t\) 序列是合法的,对于每一个位置 \(i\),要求在 \(t_{i}\) 之前第 \(i-1\) 与 \(i\) 的道路占据 \(i\) 的大于等于 \(C_{i}\) 个。这实际上是一个匹配问题,使用霍尔定理后实际上变为判定对于一个位置集合 \(S\),其邻域 \(N(S)\) 的人数都要大于等于 \(S\) 集合的 \(C\) 之和。

考虑如果 \(S\) 是若干段连续的区间且 \(S\) 不合法,那么根据抽屉原理至少有一段区间满足其也不合法,所以实际上只需要判定区间即可。实际上可以归约为最小子段和,可以简单 \(\text{dp}\) 判定。

那么实际上只需要 \(\text{dp}\) 一个 \(t\) 序列,内层 \(\text{dp}\) 级记录一下最小后缀和,判定其是否时刻 \(\geqslant 0\) 即可。由于每个位置 \(i\) 取到的 \(t\) 的集合 \(T_{i}\),只会在相邻的两条道路上的人的到达时刻(特别,最后的一个时刻要置为极大值)与 \(0\) 处取到,所以 \(\sum_{i=1}^{n} T_{i}\) 是 \(O(n)\) 级别的。而每个点 \(i\) 只需保留 \(T_{i}\) 个时间,每个时间保留 \(T_{i}\) 个最小后缀和,转移到 \(T_{i+1}\) 个状态,复杂度为 \(O(\sum_{i=1}^{L-1}T_{i}^2T_{i+1})=O(n^3)\) 的。但出题人没有刻意卡所以可以拿到 \(95\) 分。

实际上如果事先将取到极大值的最后一个时刻忽略,每一个转移可以拆成一段前缀向一个点和一段后缀向一个点的转移,取前后缀 \(\text{max}\) 即可变成 \(O(\sum_{i=1}^{L}T_{i}^2+\sum_{i=1}^{L-1}T_{i-1}T_{i})=O(n^2)\),常数很小,速度很快。

标签:后缀,text,sum,位置,2024,实际上,放满,JOI,Open
From: https://www.cnblogs.com/zhouhuanyi/p/18257245

相关文章

  • P10540 [THUPC2024] 古明地枣的袜子 题解
    题意:一个长为\(n\)的序列\(a\),初始全为零。\(n\)个操作,第\(i\)个操作形如给\(a_1,\cdots,a_{x_i}\)加上\(y_i\)。\(m\)次查询,给定\(l,r\),求对\(a\)执行第\(l\simr\)个操作后数列\(a\)的全局最大值。\(1\len,m\le5\cdot10^5,1\lex_i,|y_i|\len,1\lel\ler\len\),时间限......
  • 使用宝塔面板反向代理openai
    创建站点配置反向代理 openai的特殊配置:proxy_set_headerX-Error-Message$upstream_http_x_error_message;proxy_bufferingoff;proxy_ssl_server_nameon;proxy_ssl_protocolsTLSv1TLSv1.1TLSv1.2; 反向代理完整配置:#PROXY-START/location^~/{......
  • OpenCV一文入门
    OpenCV一文入门官网地址OpenCV当前版本opencv-python4.9.0.80python包地址https://pypi.org/project/opencv-python/OpenCV(OpenSourceComputerVisionLibrary)是一个开源计算机视觉和机器学习软件库,由Intel最初开发,现由WillowGarage和Itseez维护。OpenCV旨......
  • 基于树莓派的OpenWrt系统打开蓝牙功能
    在树莓派设备上的OpenWrt系统打开蓝牙功能1.安装必要的软件包首先,你需要确保OpenWrt系统上安装了必要的蓝牙软件包。你可以通过OpenWrt的包管理器来安装它们。在OpenWrt系统上,你可以使用opkg命令来安装软件包。安装以下软件包(注意,包名可能会因OpenWrt版本而有所不同):kmod-inpu......
  • Redis从入门到精通2024版 视频教程 下载
    Redis从入门到精通2024版视频教程下载├─第01章开篇│   001.Redis录制计划.mp4│   002.Redis介绍.mp4│   003.Redis安装.mp4│    ├─第02章基本数据类型│   01.在后台启动Redis.mp4│   02.基本数据类型-Stri......
  • 2024-06-19:用go语言,给定一个起始下标为 0 的整数数组 nums 和一个整数 k, 可以执行一个
    2024-06-19:用go语言,给定一个起始下标为0的整数数组nums和一个整数k,可以执行一个操作将相邻两个元素按位AND后替换为结果。要求在最多执行k次操作的情况下,计算数组中所有元素按位OR后的最小值。输入:nums=[3,5,3,2,7],k=2。输出:3。解释:执行以下操作:1.将nums[0]......
  • GDCPC 2024 部分题解
    老年人过来对着会的题口胡几发B.腊肠披萨 题意翻译:给你n个小写字母串,求所有小写字母串两两之间的最长公共前缀的乘方和,对一个任意数取模。比较显然的,看到多串公共前缀直接建Trie统计贡献。建好之后对每个串在Trie上走,每走一步加上当前子树内串个数和父子树内串个数之差,就能......
  • 2024/4/21
     所学时间:2小时代码行数:127行博客园数:1篇所学知识:编写web作业,完成了大致页面。<%@pageimport="java.util.*"%><%@pageimport="java.text.*"%><%@pagesession="true"%><%@pagelanguage="java"%><%@pagecon......
  • 2024/6/14
    学习时长:3小时代码行数:未统计博客数量:1篇今天完成计网实验三的部分,也是最后一次实验S1>enableS1#configConfiguringfromterminal,memory,ornetwork[terminal]?Enterconfigurationcommands,oneperline.EndwithCNTL/Z.S1(config)#vlan10S1(config-vlan)#interfac......
  • 2024/6/2
    今日完成的主要内容是有关于数据库的实验四的内容相关内容如下:数据库的备份与恢复实验在用Windows身份验证进入SSMS后找到服务器对象,右键点击备份设备点击新建备份设备来新建一个备份设备 然后再右键点击新建的备份设备,点击备份数据库 在数据库中找到students数据库 在......