There,Hello
There,Hello
ACMer
个人博客

2022杭电多校3【题解】

There,Hello - 2022-7-30 / 题解
发布于:2022-7-30|最后更新: 2023-11-17|
type
status
date
slug
summary
tags
category
icon
password

3. Cyber Language

这个纯纯签到了。
不过借此题学到了 stringstream 操作。

12. Two Permutations

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