Python解题 - CSDN周赛第33期

本期四道题全考过，题解在网上也都搜得到。。。没有想法，顺手水一份题解吧。

第一题：奇偶排序

给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。

输入描述：第一行输入整数n。(1<=n<=1000)表示数组大小；第二行输入n个整数a.(1<=n<=100)

输出描述：输出重排之后的数组。

示例：

示例
输入 6
3 34 67 89 90 58
输出 3 67 89 34 90 58

分析

超级大水题，直接遍历一遍数组，把奇数和偶数分开成两个数组，最后再把两个数组返回即可，时间复杂度 $O(n)$ 。

如果想加点花，比如降低空间复杂度（上面需要借助外部空间存储奇数和偶数数组），可以在原数组遍历，如果遇到奇数，就和它前面的数交换位置，直到前面为空或不是偶数位置。类似冒泡排序，时间复杂度 $(On^2)$ ，很没必要。

本题因为要求奇数间和偶数间的相对位置不变，所以不能使用不稳定的排序方法比如快排。

参考代码

n = int(input().strip())
arr = [int(item) for item in input().strip().split()]
odd = list()
even = list()
for i in arr:if i%2: odd.append(i)else: even.append(i)
print(*odd, *even)

第二题：小艺改编字符串

已知字符串str。添加至少多少字符可以使得str变成回文串。

输入描述：输入字符串s.(1<=len(str)<=100000)

输出描述：输出最小需要添加字符的数量。
示例：

示例
输入 abab
输出
1

分析

很久以前考过，不过还是值得一说。思路还是动态规划，好像递归也可以？没有试过。

问哥觉得关于字符串的动态规划常常有点抽象，不太好理解，所以保险起见，我们还是画图来看。

首先，对于任意一个长度大于 1 的字符串（长度等于 1 的字符串本身就是回文串，不需要添加字符），如果我们观察它的左右两端，只有下面两种可能：

最左端和最右端的字符相同；
最左端和最右端的字符不同。

我们可以用 $i$ 和 $j$ 表示左右两端字符串的下标，用 $S_{i,j}$ 表示从下标 $i$ 到 $j$ 的字符串，如下图所示：

然后，对于左右端字符相同的字符串，我们可以把它们剥掉，得到一个新的子串 $S_{i+1, j-1}$ ，很显然，只要子串 $S_{i+1,j-1}$ 是回文串，那么原来的 $S_{i,j}$ 必定也是回文串。所以原问题就转变成一个子问题：需要添加多少字符可以使得子串 $S_{i+1,j-1}$ 变成回文串？

而对于左右端字符不同的字符串，我们有两种选择：

如果子串 $S_{i,j-1}$ 是回文串，我们可以在左边添加一个和最右端相同的字符，使原字符串 $S_{i,j}$ 变成回文串；
如果子串 $S_{i+1,j}$ 是回文串，则我们也可以在右边添加一个和最左端相同的字符，使原字符串 $S_{i,j}$ 变成回文串。

那么，只要在这两种选择中取较小的作为答案即可。

于是，动态转移过程就很清楚了。我们定义一个二维数组 $dp[i][j]$ 表示需要添加多少字符使得字符串 $S_{i,j}$ 变成回文串，则可得状态转移方程如下（ $S_i$ 和 $S_j$ 分别表示字符串 $S_{i,j}$ 左右两端的字符）：

如果 $S_i = S_j$ ，则 $dp[i][j] = dp[i+1][j-1]$
如果 $S_i \neq S_j$ ，则 $dp[i][j] = min(dp[i][j-1], dp[i+1][j])+1$

先给个递归的写法，就是直接把上面的转移公式套进来。

参考代码一

def fun(s):n = len(s)if n <= 1: return 0i, j = 0, n-1if s[i] == s[j]: return fun(s[i+1:j])return min(fun(s[i:j]), fun(s[i+1:j+1]))+1
s = input().strip()
print(fun(s))

但是因为字符串长度达到1e5，递归极有可能超时。

但是递归给我们的顺序值得参考：所有递归到最终的字符串长度必定为 1 或 0 （空字符串）。

所以，如果我们使用动态规划，原字符串的答案，必须按子字符串的长度，从小到大，递推过来。也就是说，我们必须先得到所有长度为 1 或 0 的子串的答案，再递推到长度为 2 的，然后是长度为 3 的。。。直到长度等于原字符串。

所以我们在传统的 $(i,j)$ 双循环中必须加一个变量 $k$ ，用来表示子字符串的长度。而一旦 $k$ 的长度确定了， $j = i + k$ ，所以还是双循环。循环次数也很好计算，就是所有子串数量之和： $\frac{n*(n+1)}{2}$

时间复杂度是 $O(n^2)$ ，但是因为除以 2，所以计算量级还是 1e9，勉强可以接受。

参考代码二

s = input().strip()
n = len(s)
dp = [[0]*n for _ in range(n)]
for k in range(1, n):for i in range(n - k):j = i + kif s[i] == s[j]: dp[i][j] = dp[i+1][j-1]else: dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
print(dp[0][n-1])

第三题：公司新表

公司里为了凸显公司的特性。安装了一个n进制表。已知新的表的时间是”H:M”。时间合法的定义为H<=23 && M<=59。时间有多少种进制定义的方式，依次打印出来。如果有无数种解输出”-1”，不存在输出”0”。

输入描述：输入一行字符串a:b形式。

输出描述：输出答案。

示例：

示例
输入 11:20
输出 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

分析

13期考过。

不难，但是因为要分析字符串，既抽象又繁琐，所以本题参考代码不想给了，问哥写得很繁琐，大部分时间浪费在这题，看到就烦 ><。

简单说说思路：先把给定的字符串按冒号一分为二，左边为小时数，右边为分钟数。

先特判，什么样的情况是有无数种解呢？因为字符串中可以含有字母，那么假定字母代表了一个数字，只要不进位（字符串长度为 1），就可以代表无数种解。比如一个字母 A，可以代表11进制以上的所有进制，因为 A 就代表了10（按照顺序），是合法的小时（小于24）或分钟（小于60）数。同样，很显然，如果代表小时的一个字母表示了24以上的十进制数字，或代表分钟的一个字母表示60以上的十进制数字，则必定是没有解，返回 0。

而如果进了一位，答案必定有限，比如 11，最多只能代表22进制（该进制中11代表十进制的23）。所以，只要检查分割后的代表小时和分钟的字符串的长度，小于等于1且代表十进制数字小于24或小于60，就必定是无数种解，直接返回-1。

然后就是穷举了，从小时和分钟数所能代表的最小进制开始，比如字符串AB，不可能代表12进制及以下的进制。然后循环加一，每次计算小时和分钟翻译成十进制是否小于24和小于60。知道不满足此条件为止。

如果一个都没找到，很显然，直接返回 0。否则就把所有答案打印出来即可。

第四题：选择客栈

丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

输入描述：共n+1 行。第一行三个整数 n ,k ,p ，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；接下来的 n 行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。

输出描述：一个整数，表示可选的住宿方案的总数。

示例：

示例
输入 5 2 3
0 5
1 3
0 2
1 4
1 5
输出 3