第十八届西南科技大学ACM程序设计竞赛题解
"西南科技大学第十八届ACM程序设计竞赛题解" 在本篇文章中,我们将对西南科技大学第十八届ACM程序设计竞赛的题解进行详细的分析和总结。 A. 花非花 题解: 本题的解题思路是先构造出一个序列,然后用动态规划算法处理出以中心的最长回文串的长度。由于是回文串,所以对于, 也就是回文串,显然这样包含了所有以为中心的回文串,也即以为开头的回文串数量都可以用差分来处理区间加,时间复杂度为O(n)。 B. 为欢几何 题解: 本题是一个签到题,题意是按顺序输出个字符串的第一个字符。解决方法之一是开一个数组,循环次输入字符串,每次循环过程输出即可。 C. 花空烟水流 题解: 本题的解题思路是可知,长度为的字符串由种字符组成的字符串共有种,而对于字符串来说,连续子串的数量一定小于。由此可得, 最长不会超过。算出每个的最大,然后直接暴力BFS搜索即可。最终复杂度为O(n)。 D. 似花还似非花 题解: 本题的解题思路是如果没有不可选取的限制,那么答案就是排列长度扣掉排列的最长公共子序列长度,对于不属于最长公共子序列的元素,至多只需要1次操作就可以把它挪动到恰当位置。如果限制了元素不可被选取,那么答案就是排列长度扣掉排列的包含元素的最长公共子序列长度。因此,本题实际上是求解两个排列的包含某一特定元素的最长公共子序列长度。 本题可以转化为最长上升子序列长度问题,定义表示元素在数列出现的位置,定义,也就是数列中第个元素所在数列当中的位置,我们可以得到一个新数列。这种情况下,求数列的最长公共子序列问题其实就是求数列的最长上升子序列问题。 对于求解某数列的最长上升子序列问题,有一个动态规划+二分的解法,主要步骤如下:1.定义一个动态数列,初始为空2.从左到右遍历所有元素 2.1 获取当前遍历到的元素 2.2 如果该元素比中所有元素大(为空时也成立),则把它放在数列最右端,跳过2.3 2.3 找到数列中大于的最左边的元素,并把它替换为(在整个算法过程中,数列永远是单调递增的)3.此时,数列的长度就是数列的最长上升子序列的长度。 当然了,并不一定是的最长上升子序列,只是长度一致。该算法时间复杂度为O(n log n),因为步骤2.3可以通过二分查找来进行优化。 E. 西楼暮,一席疏雨 题解: 本题是一个简单的排列组合问题。选定一个数,剩下的位置就是一个的排列,所以每个元素在式子中出现次,用快速幂求即可,注意欧拉降幂,即其中是欧拉函数;根据排列的对换性质,逆序数为奇数的排列的个数和逆序数为偶数的排列个数一定相等,所以产生的个数是。时间复杂度为O(n)。特别的,当等于时特判,此时逆序数为,所以答案为。 F. 青山隐隐,败叶萧萧 题解: 本题属于简单题。题意简化后如下:任意多次操作后,能否使得一个序列任意相邻两数之和为是质数,且每个数都是质数。前置知识:奇数 奇数 偶数,奇数 偶数 奇数,偶数 偶数 偶数; 是最小的质数,也是唯一的偶质数。又有无穷多个数满足:自身是质数,自身仍是一个质数。这样的例子有很多,例如: 这些数都满足该性质。所以题目一下就简单起来了:只要该序列是 "奇数偶数交替" 排列的数即可构造出满足题意的序列。从第二个数开始遍历序列,判断是否满足为奇数即可。只有一个数的时候,则一定可以满足。总时间复杂度为O(n)。 G. 几番烟雾,只有花难护 题解: 由题意可知,本题要求的是。正常暴力跑,每一次单独计算答案,则时间复杂度为显然会超时。考虑使用整除分块的思想处理该问题。设一共有 表示 的因数个数 个数满足 ,我们令 为这 项之和,即令 表示正整数 的第 个因子,则 。我们将原式的每一项的 部分均看成不能整除的结果,则每一项的该部分均可以改写成 故答案只需要在此基础上减去 即可。根据先前的推理,则所求原式可做以下变式:原式 我们将该式子化为三个部分:①: 部分,已经推得 计算 的一种方法是 暴力遍历,...
![](https://csdnimg.cn/release/download_crawler_static/85375315/bg1.jpg)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![avatar](https://profile-avatar.csdnimg.cn/a865418cbe244208af11d2eefdd01599_m0_50376582.jpg!1)
- 粉丝: 5
- 资源: 1
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
最新资源
![feedback](https://img-home.csdnimg.cn/images/20220527035711.png)
![feedback-tip](https://img-home.csdnimg.cn/images/20220527035111.png)
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)
评论0