钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

NWERC 2018 E. Equality Control

题面

E. Equality Control

题意

判断两段 “程序” 是否等价.
细节参见题面(懒得翻译)

暴力模拟写法

很简单, 递归模拟即可.
你问结果?
当然是喜闻乐见TLE了.

投机取巧

我们可以发现如下性质:

  • shuffle中如果是一个常数列, 那么这个shuffle只有唯一确定的排列, 也就是说这个shuffle没有意义
  • 遇到contract直接读过去就行, 它也是没有意义
  • sorted和shuffle是相互覆盖的关系, 也就是说, 如果它们相互嵌套, 只要读最外面的就可以了
  • 等价的条件是: 两段 “程序” 中所有有意义的shuffle区间相等(不管是位置还是其中的数列)

踩的坑

首先是被string坑了, 在某个测试点出现了MLE, 换成char[]就将错误变成了TLE.
TLE很显然是单纯暴力递归导致的, 于是开始研究如何优化.
没考虑第一条性质, WA.
理解错题意, 傻乎乎的认为不是整段 “程序” 最外层的shuffle都是没有意义的, WA.
上面这个解决了自然就能想到第四条性质, 遂AC.

完整AC代码