钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

Codeforces Round #700 (Div. 2)D1. Painting the Array I

题面

D1. Painting the Array I

官方题解

官方题解(D1对应1479B1)

题解大意

约定:

  • 我们将生成的两个序列分别称为st, 也就是a(0)a(1)
  • 我们将st的最后一个元素分别称为xy
  • 我们将扫描ai过程中的当前元素称为z
  • 我们将xz后首次出现的位置称为next(x)

贪心策略I:

  • z 等于 x 或 y 中某一个, 将 z 分配给相反的子序列, 比如 z == x 时, 将 z 分配给 t 附加在 y 后. 特别的, 如果 z == x == y 时, 任意分配即可

贪心策略II:

  • 如果 z, x, y 互不相等, 将 z 分配给具有最近的下一个相同值的值后. 说人话就是: 如果 next(x) < next(y), 则 z 附加在 x 后, 否则, z 附加在 y 后

证明:
见官方题解

一点点改动

首先, 题目并没有要求输出子序列, 所以重复元素就不需要操作了, z == x == y 时, 跳过即可

其次, 影响结果的是两个元素之间的关系, 所以不需要求next(x)和next(y)(TLE警告)了, 考虑 ai + 1就可以了

完整AC代码

这里其实并不需要用vector, 因为我们只考虑尾部元素, 既然AC了, 优化的事情就交给读者了.