首页 > 其他分享 >NOIP 模拟赛:2024-10-28

NOIP 模拟赛:2024-10-28

时间:2024-10-31 16:48:20浏览次数:1  
标签:10 le sum mn 28 2024 某组 dp

T1:

给定两个数组 \(a,b\),要求将 \(b\) 重排,使得 \(b>a\) 的位置个数最多,在此基础上最大化 \(b\) 的字典序。
\(n\le 5000\)。


最多的位置个数是容易求的,排个序即可。

如何最大化字典序?依次枚举 \(i=1\sim n\),然后从大到小枚举 \(j\) 看看 \(b_i=j\) 是否可以让后面依然保持大于位置足够。

把 \(j>a_i\) 和 \(j\le a_i\) 两类分类,因为这会影响后面需要多少个大于位置。

明显的结论:一定是 \(a_{i+1\sim n}\) 的前 \(mx-now\) 小匹配。
进而,我们发现当 \(j-1\),只会影响 \(a\) 一个位置的对应方式。\(O(n^2)\)。

T2:

给定平面上 \(n\) 个点。求点的排列,使得前 \(i\) 个点与原点的外包矩形周长 的增加量最小。\(n\le 10^5\)。


断言:每次一定选使得增加量最小的哪个点。
证明:设这个点是 \(mn\),如果选了点 \(p\) 替代 \(mn\),不如把 \(mn\) 放在 \(p\) 的前面,这样 \(p\) 及后面的点造成的增加量必然不增。

然后如何实现找增加量最小的点?维护三个优先队列,保存 "当前矩形上/右/右上方" 的点。取出一个点之后打标记,以后不要在其他队列里取出来。

T3:

\(n\) 个数 \(\{s_i\}\) 任意分组,要求每一组极差的和 \(\le k\),求方案数。\(n\le 500,k\le 1000\)。


显然要排序,然后对于 \(s_i\) 有:单独开一组或者接在某组后面。

再细分,单独开一组立刻结束/单独开一组不结束/接在某组后面结束/接在某组后面不结束。

问题在于如果接在某组后面,每一组的结尾元素是不一定的,怎么找?

我们这么做:在加入 \(s_i\) 之后,剩下所有还没结束的组,贡献都增加 \(s_i-s_{i-1}\)。这相当于对贡献做了一个差分,然后一直做前缀和直到结束,刚好就是一组的贡献。

\(dp[i][j][sum]\) 表示考虑前 \(i\) 个,有 \(j\) 个还没结束的组,当前总和是 \(sum\) 的方案数。

T4:

有 \(n\) 个三元组,每个数的值域为 \(0\sim F\)。要求改最少的数,使每个三元组的总和递减。\(n\le 10^5,F\le 10^{10}\)。


初始想法:\(dp[i][j]\) 表示前 \(i\) 个三元组,第 \(i\) 个总和为 \(j\) 的方案数。\(dp[i][j]=\min dp[i-1][j\sim 3F]+dist(sum_i,j)\)。其中 \(sum_i\) 表示 \(i\) 初始的和,\(dist(sum_i,j)\) 表示改成 \(j\) 至少需要动几个数。

\(dist(i,j)\) 可以 \(O(1)\) 计算,这个复杂度是 \(O(nF^2)\) 的。

进阶想法:记录 \(mn[i][j]\) 为 \(dp[i]\) 的后缀 \(\min\),可以优化到 \(O(nF)\)。

满分想法:我们直接在枚举 \(i\) 的过程中维护 \(mn[i][]\) 的变化。用一个 map 维护 \(mn[i][]\) 的差分,即 \(mp[j]=mn[i][j]-mn[i][j-1]\)。再用一个变量维护 \(mn[i][0]\)。\(i\) 每次变动只有常数个位置变化。

标签:10,le,sum,mn,28,2024,某组,dp
From: https://www.cnblogs.com/FLY-lai/p/18518164

相关文章

  • java8 map每10个分一组
    在Java8中,如果你想要将一个Map的条目每10个分为一组,你可以使用流(Streams)来实现这一功能。这里是一个例子,假设我们有一个Map<Integer,String>,我们想要将其每10个元素分为一组。首先,我们需要将Map的entrySet()转换为流,然后使用流的操作来实现分组。 importjava.util.......
  • DAY49 ||1143.最长公共子序列| 1035.不相交的线 | 53. 最大子序和 |392.判断子序列
    1143.最长公共子序列题目:1143.最长公共子序列-力扣(LeetCode)给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的......
  • 共码未来,花开烂漫:近千名开发者齐聚9地欢度1024程序员节
    10月23日至27日,以“共码未来,待到山花烂漫时”为主题的HDD·1024程序员节专场交流会携手HUAWEIDEVELOPEREXPERTS(HDE)、企业及高校专家,陆续在苏州、武汉、长沙、成都、南京、西安、北京、广州、上海9地举办,向近1000名鸿蒙开发者现场分享了鸿蒙生态最新成果,交流了开发经验与案例。此......
  • 美畅物联丨掌握Wireshark:GB28181协议报文分析实战指南
    Wireshark,一款在网络安全与协议分析领域享有盛誉的网络嗅探器,凭借其强大的功能集、直观的图形用户界面以及广泛的跨平台兼容性,已成为众多开发者不可或缺的得力助手。其开源特性吸引了大量开发者的积极参与,不断推动其功能的完善与升级。在GB/T28181协议(专为视频监控系统设......
  • AP5127 是一款 PWM 工作模式,高效率、外围简单、内置功率管,适用于 12-100V 输入的高精
    产品描述AP5127是一款PWM工作模式,高效率、外围简单、内置功率管,适用于12-100V输入的高精度降压LED恒流驱动芯片。输出最大功率可达25W,最大电流2.5A。AP5127可实现全亮/半亮功能切换,通过MODE切换:全亮/半亮/循环模式。AP5127工作频率固定在140KHZ,同时内置抖频电路,......
  • AP5216 是一款 PWM工作模式, 高效率、外围简单、内置功率管,适用于5V~100V输入的高精度
    产品描述AP5216是一款PWM工作模式,高效率、外围简单、内置功率管,适用于5V~100V输入的高精度降压LED恒流驱动芯片。输出最大功率可达9W,最大电流1.0A。AP5216可实现全亮/半亮功能切换,通过MODE切换:全亮/半亮模式。AP5216工作频率固定在130KHZ,同时内置抖频电路,可以降低......
  • 国标GB28181视频平台LiteGBS国标GB28181设备管理软件级联共享系统解决方案
    网络视频监控技术得益于网络技术的快速进步,已经建立起了成本效益高、分布广泛、基于网络的监控系统,显著提高了监控和管理的效能。这一技术为维护城市安全、预防犯罪以及保护公民安全提供了坚实的技术支持。在国标GB28181设备管理软件LiteGBS的运作中,服务器扮演着核心角色,它负责管理......
  • 2024.10.31总结
    本文于github同步更新。最后一天喽A:卡双模哈希......
  • AP2813 采用外部供电
    车灯LED高性能双通道输出DC-DC降压恒流芯片AP2813产品描述AP2813是一款双路降压恒流驱动器,高效率、外围简单、内置功率管,适用于5-80V输入的高精度降压LED恒流驱动芯片。内置功率管输出最大功率可达12W,最大电流1.2A。AP2813一路直亮,另外一路通过MODE1切换全亮,爆闪。AP......
  • 界面控件Kendo UI for Angular 2024 Q3亮点 - 全新的页面模板
    随着最新的2024Q3版本,Progress使用户能够使用现成的页面模板和构建块更快地构建令人惊叹的应用程序,使您的Telerik和KendoUI开发体验更好。Telerik和KendoUI 2024Q3版本将焦点放在新推出的页面模板和构建块上,每个页面模板和构建块都预先配置了TelerikUIforBlazor、KendoU......