1 条题解
-
0
题目分析
30 分
暴力枚举交换的两个位置,然后 计算最小代价,时间复杂度 。
50 分
最小代价的计算显然可以优化,不需要每次重新计算,将交换的两个位置的代价重新计算即可,时间复杂度 。
正解
这么大显然是没用的,先用个桶统计一下 。
考虑没有那个交换操作怎么做,要成为回文串的话,两个对称位置上的字母 ,可以是 变成 也可以是 变成 ,或者两个都变成另外一个字母 ,于是可以在 下解决问题。
现在有了一个交换操作,但是并不需要真的去 去枚举交换的位置,因为该交换操作最多只涉及到了两对对称位置上的字母,其他的都没有影响,于是直接 去枚举涉及到的两对对称位置上的字母是什么就可以了。
- 1
信息
- ID
- 58
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者