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

ARC 207

image

目前打得最好的一集。

A

考虑如果 \(\le 0\) 还会减一,那么花掉的钱就是,\(1+2+\cdots +(n-1)\)。现在的问题就是,可能少花掉一些。

最多花掉 \(\mathcal{O}(n^2)\),所以考虑计数这个。发现其实,花掉的是 \(\sum_{i=1}^n \min(p_i-1,a_{p_i})\)

对于 \(\min(p_i-1,a_{p_i})=k\) 设计状态,\(dp_{i,sum,cnt}\) 为:从大到小,现在 \(k=i\),和是 \(sum\)\(cnt\) 个处理完了。

考虑转移:

  • \(\min(p_i-1,a_{p_i})=a_{p_i}=k\)。这个就是当前一些枚举选择几个。

  • \(\min(p_i-1,a_{p_i})=p_i-1=k\)。只可能 \(+1\)\(0/1\) 枚举。

可以用组合数计算出来。具体的,选择几个 \(a_i=k\) 的组合数,对应的大的 \(p\) 的组合数等。

复杂度是 \(\mathcal{O}(n^4)\),因为枚举选择个数,一共只会有 \(\mathcal{O}(n)\) 次枚举。

B

构造题,难死了。

考虑 \(n\le 5\) 构造不出来。

查看样例,发现正好不可到达的点对为 \((1,n),(2,n-1),\cdots\)。如果 \(n\) 是偶数就这个样子构造。

具体的,有一个二分图。左边是 \(1\sim n/2\),右边的是 \(n/2+1\sim n\)。对于 \(i\le n/2\),给所有的 \(j>n/2,i+j\neq n+1\) 连边。这样子是对的,因为所有连了边的右部点可以到达,所有左部点可以到达,没有连边的右部点至少要 \(3\) 次(二分图!)所以是对的。

考虑 \(n\) 是奇数:\(1+(n-1)=n\),那么留下一个 \(n\) 不能到达自己就好了。

C

比较简单。

题目相当于,把原来的序列划分成若干段,每一段的或是不下降的,最大化段数。

考虑段的或,一共只有 \(n\log n\) 种值(经典)。

\(f_x\)\(1\sim i\),现在最后一段权值是 \(x\),的最大段数。

考虑加入 \(a_{i+1}\)。有两种:

  • \(a_{i+1}\) 加入上一个段尾。直接或上,转移。

  • \(l=i+1\) 开一个新的段,要求新的段的结尾 \(r\),满足 \(l\sim r\) 的或更大。

直接枚举 \(r\) 是不行的,但是发现有第一种转移,找到一个最小的 \(r\) 就可以转移到其他的。那么二分+ST 表就可以,复杂度两个 \(\log\)

http://www.hskmm.com/?act=detail&tid=25462

相关文章:

  • 半年小结 Vol4. 跌跌撞撞开启 PhD 生涯
  • 深入解析:C++:内存管理
  • 大数求余
  • visual studio 无法打开文件
  • 基于MPPT算法的光伏并网发电系统simulink建模与仿真
  • 实用指南:【系统架构设计师】2025年上半年真题论文回忆版: 论系统负载均衡设计方法(包括解题思路和参考素材)
  • 软件版悟空博弈+WAUC构筑元人文演化之路研究报告——声明Ai研究
  • QBXT2025S刷题 Day5题
  • [KaibaMath1001] 关于∀ε0,|a-b|ε = a=b的证明
  • 基于Web的分布式图集管理系统架构设计与实践 - 教程
  • TCP小结 - 指南
  • 国庆 Day2 强基物理
  • ZR 2025 十一集训 Day 6
  • 软件版悟空博弈 + WAUC:构筑元人文的演化之路
  • 基于MVO多元宇宙优化的DBSCAN聚类算法matlab仿真
  • AirSim 安装过程记录 - zzh
  • LARAVEL安装报错:Illuminate\Database\QueryException could not find driver (Connection: sqlite, SQL:
  • 基于AXI模块的视频流传输(硬件连接篇)
  • [GDOUCTF 2023]泄露的伪装
  • 仿射密码
  • AtCoder Regular Contest 207 (Div.1) 游记
  • 深入解析:AI破局:饿了么如何搅动即时零售江湖
  • 从零开始学Flink:数据输出的终极指南
  • 数据编织平台实现AI代理自助数据访问
  • [题解]P12008 【MX-X10-T4】[LSOT-4] Fragment of Memories
  • 线性表的顺序存储和链式存储
  • AWS WebRTC:获取ICE服务地址(part 3):STUN服务和TURN服务的作用 - 实践
  • Python中的对象池与驻留机制:小整数、字符串与大整数
  • 基于ADMM无穷范数检测算法的MIMO通信系统信号检测MATLAB仿真,对比ML,MMSE,ZF以及LAMA
  • 点乘与叉乘的由来:从四元数到公理自洽的启示