acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • ABC484G 题解

    场上只切了 4 题怎么办/ll要不要退役/ll Difficulty:4.8(蓝题下位)/ Easy+ Tag:DP 套 DP(? 首先考虑爆搜。但这是指数级,太不牛了。 考虑用状态代替被搜索的串,使得最后有一种简单的方法判定状态。 显然我们可以记录当前前缀可以被表示为哪些 xyxxy...xyxxy...xyxxy... 之类和最后 x/yx/yx/y 的前 iii 位字符拼接。状态太多了!注意到只有最后的那个前缀字符才是真正被用到的,其它都可以抛弃。这样可能的状态数量就只有 ∣X∣+∣Y∣≤16|X|+|Y|\le 16∣X∣+∣Y∣≤16 了,但是显然一个字符串可以用若干个这种状态表示,所以用 O(2∣X∣+∣Y∣)O(2^{|X|+|Y|})O(2∣X∣+∣Y∣) 个二进制状态记录每一种状态是否存在,转移时最后判断状态中是否存在一个完整的 XXX 或一个完整的 YYY 即可。 然后我们发现可以把相同长度相同状态压成一种一起转移,显然是对的。 预处理每一种状态下一位接 0/10/10/1 会变为哪些状态。然后接个 DP 即可做到 O(∣S∣×2∣X∣+∣Y∣)O(|S|\times 2^{|X|+|Y|})O(∣S∣×2∣X∣+∣Y∣),可以通过。 代码中使用了滚动数组减小空间。

    userId_undefined
    cjdst
    小有名气尊贵铂金CSP-S一等奖
    19阅读
    2回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页