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

AtCoder AGC044 总结

AtCoder AGC044 总结

A

试一试,发现分别找到 \(\le x\)\(2,3,5\) 的倍数,\(>x\)\(2,3,5\) 的倍数,然后记忆化搜索做即可,证明不会。

B

每个位置维护一个 \(a_{i,j}\) 表示它逃出去的最小路径,每次一个人离开后,这个人对于路径的贡献就从 \(1\) 变成 \(0\),暴力地递归更新它周围点的 \(a\) 即可。每次更新会使 \(a\) 减一,复杂度是初始 \(a\) 的和,是 \(O(n^3)\) 级别。

C

我们只关心位置模 \(3^n\) 的值即可,因此大于 \(3^n\) 也没关系,那么加一就没有限制了。考虑把问题放在在三叉的字典树上,翻转打标记即可,全局加一问题是经典的(考虑从低位到高位建树,那么所有前缀为连续的 \(2\) 的路径都会变成 \(0\),递归前缀为连续的 \(2\) 的路径即可)。

D

首先把所有字符问一次长为 \(L\),那么可以知道所有字符的出现次数,也可以知道 \(S\) 的长度。考虑每种字符依次插入,发现当返回值 \(q=|S|-|T|\) 时当且仅当 \(T\)\(S\) 的子序列。于是二分位置把 \(c\) 插入,询问 \(c\) 开始的后缀是否是子序列,这样可以把第一个 \(c\) 放到最左的位置。若有多个 \(c\),从上一个 \(c\) 开始的位置二分,询问前面个数个 \(c\) 与这个 \(c\) 开始的后缀拼成的字符串是否是子序列。

E

考虑特殊值。考虑 \(a_i\) 最大值,那么如果当前走到了最大值,那么一定不会再走,于是断环成链,首尾各放一个最大值。

\(f_i\) 为从 \(i\) 开始走的最大期望,则(对于 \(0<i<n\)

\[f_i=\max(a_i,\frac {f_{i-1}+f_{i+1}}2-b_i) \]

考虑把 \(\max\) 右侧的 \(b_i\) 消去,设 \(g_i=f_i-c_i\),则

\[g_i=\max(a_i-c_i,\frac {g_{i-1}+c_{i-1}+g_{i+1}+c_{i+1}}2-b_i-c_i) \]

只要解出 \(\frac {c_{i-1}+c_{i+1}}2-b_i-c_i=0\) 即可将 \(b_i\) 消去。由于 \(c_0,c_n\) 是无意义的,所以将前式移项得到 \(c_{i+1}=2(b_i+c_i)-c_{i-1}\),并随意指定 \(c_0,c_1\) 即可线性求 \(c\)。于是我们得到了(令 \(d_i=a_i-c_i\)

\[g_i=\max(d_i,\frac {g_{i-1}+g_{i+1}}2) \]

放在二维平面上,假设若没有 \(d_i\),那么就是 \((0,g_0),(n,g_n)\) 的直线。现在 \(d_i\) 会把直线往上「顶」,我们只需求 \(g_0,\{d_i\},g_n\) 构成的凸包即可。

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

相关文章:

  • UOJ#32【UR #2】跳蚤公路 题解
  • 2025 年窗帘杆源头厂家最新推荐榜单:包含支架 / 环 / 全自动 / 可伸缩等多类产品及配件,帮助选到品质与交期双优的优质厂家
  • 2025 年电动窗帘厂家推荐榜单:聚焦国内优质企业定制实力与口碑,为采购者提供最新选择参考电动窗帘系统/电机/轨道/配件/智能电动窗帘厂家推荐
  • Vue3 使用注意事项
  • ClickHouse ReplacingMergeTree 去重陷阱:为什么你的 FINAL 查询无效? - 若
  • js中?? 和 || 的区别详解
  • 微信机器人API接口| 个人开发者必备
  • 直击现场! “ 直通乌镇 ”开源赛复赛收官,OpenCSG担任评委,十强藏着哪些产业机会?
  • Python 列表生成式、字典生成式与生成器表达式
  • java 解析json字符串,获取特定的字段值,JsonObject
  • python 批量提取txt数据中的值写入csv
  • 回忆中学的函数
  • Java 一行一行的读取文本,小Demo 大学问
  • 家里wifi电信出口ip如何控制不变,解决访问云服务器上面的资源
  • 2025 年挤压造粒机源头厂家最新推荐榜单:前五企业技术实力、服务能力及口碑测评指南对辊挤压/化肥挤压/干粉挤压造粒机厂家推荐
  • MYSQL数据库取消表的约束
  • 2025 年京东 e 卡回收平台最新推荐排行榜:权威测评实时结算平台,助力用户安全高效转让京东 e 卡
  • 2025 年支付宝消费券回收平台最新推荐榜单:优质平台权威测评,助您高效安全处理闲置消费券支付宝消费券回收/闲置支付宝消费券回收/支付宝消费券快速回收平台推荐
  • ICP备案查询网站 域名备案查询
  • 2025 年注浆管厂家最新权威推荐排行榜:聚焦 R780/108 / 隧道 / 预埋 / 桩基等专用产品,精选 TOP5 优质企业
  • stable diffusion网络结构详解
  • 9.30
  • 网络与系统攻防技术实验一——逆向破解与Bof
  • 【python】解决grpcio.protoc生成的pb文件里面没有类和方法定义
  • 阙韩
  • “计算机配置\Windows 设置\安全设置\本地策略\审核策略” 配置后不生效
  • Spring Boot 事件发布与监听 观察者模式的实际应用 - 实践
  • P13969 [VKOSHP 2024] Exchange and Deletion
  • Matlab 通用库的fft和dsp toolbox的dsp.fft对比
  • [CTS2024] 众生之门