type
status
date
slug
summary
tags
category
icon
password
3. Cyber Language
这个纯纯签到了。
不过借此题学到了 stringstream 操作。
12. Two Permutations
给定两个排列 ,,每次操作都可以选择从 或 中选择最左端的数加入到序列 (刚开始为空)尾部中,最终会形成长度为 的序列 ,问有多少种方案使得 ?
开始的想法是设 表示 中已经选择了前 个, 中已经选择了前 个的方案数
如果 ,那么 就可以从 转移。
同理,如果 ,那么 就可以从 转移。
那么我们可以写出如下代码:
不过这一份空间时间都是 的代码显然是过不去的
接下来我们考虑如何优化,回顾题目,我们发现 , 是两个排列这个条件我们没有用上,是否可以从这里入手呢?仔细一想我们会发现对于每个 , 或 中最多匹配一次,那么就考虑 与 或者 匹配,状态如何转移
设 (ps:这样的 只有一个),那么
同理,设 ,那么
这样的话时间上就被降到了 ,而且对于每个 ,最多转移两个 ,所以 数组最多用过 ,那我们就不用数组来保存 了,换成哈希表
这份代码交上去还是T了,哈希表对于这道题来说常数还是有点大
再来考虑如何优化,我们发现在中 中对于每个位置最多转移两个 ,并且转移的这两个 是上一个位置新转移到的,那么我们就可以像滚动数组那样优化一下就好啦