第十八届西南科技大学ACM程序设计竞赛题解
需积分: 50 71 浏览量
2022-05-14
22:51:35
上传
评论 1
收藏 601KB PDF 举报
第十八届西南科技大学正式赛赛题题解
A.花非花
题解：
先构造出一个序列 ，用 算法处理出以 为中心的最长
回文串的长度 ，因为 是回文串，所以对于 ，
也是回文串，显然这样包含了所有以 为中心的回文串，也即以
为开头的回文串数量都 ，可以用差分来处理区间加，时间复杂度 。
B.为欢几何
题解：
本场签到题之一。题意是按顺序输出 个字符串的第一个字符。
做法很多种，方法之一是开一个 数组 。循环 次输入字符串 ，每次循环过程输出 即
可。
C.花空烟水流
题解：
可知，长度为 ，由 种字符组成的字符串共有 种，而对于字符串 来说，连续子串的数量一定小
于 。由此可得， 最长不会超过 。算出每个 的最大 ，然后直接暴力bfs搜索即可。最终
复杂度为 。
D.似花还似非花
题解：
如果没有不可选取 的这个限制，显然需要的最小操作次数就是排列长度 扣掉排列 的最长公共
子序列长度，对于不属于最长公共子序列的元素，至多只需要1次操作就可以把它挪动到恰当位置。
如果限制了元素 不可被选取，那么答案就是排列长度 扣掉排列 的包含元素 的最长公共子序
列长度。
因此，这个题实际上是求解两个排列的包含某一特定元素 的情况下的最长公共子序列长度。
两个排列的最长公共子序列长度问题可以转化为最长上升子序列长度问题。定义 表示元素 在数列
出现的位置，定义 ，也就是数列 中第 个元素所在数列 当中的位置，我们可以得
到一个新数列 。
这种情况下，求数列 ， 的最长公共子序列问题其实就是求数列 的最长上升子序列问题。
对于求解某数列 的最长上升子序列问题，有一个动态规划+二分的解法，主要步骤如下：
1.定义一个动态数列 ， 初始为空
2.从左到右遍历所有元素
2.1 获取当前遍历到的元素
2.2 如果该元素比 中所有元素大( 为空时也成立)，则把它放在数列最右端，跳过2.3
评论0