阿里云智能秋招 2023.10.29 编程题目与题解

发表于 2023-10-30 更新于 2023-11-02 分类于笔试阅读次数：本文字数： 1.8k 阅读时长 ≈ 2 分钟

1、小红的单词

小红有一个长度不超过\(10\)的单词，写在了一个\(10\times 10\)的方块里，单词有可能是横着或者竖着的。

请你找到这个单词。

输入

输入一个\(10\times 10\)的方块，字母表示单词的组或部分，'.'表示空白。

输出

输出一个字符串表示答案。

样例

输入：
..........
..........
..........
..smallred
..........
..........
..........
..........
..........
..........

输出：
smallred

解答

由于单词是向下写或者是向右写的，因此只需要从上到下，从左到右枚举所有字母字符，按顺序添加到答案即可。

代码

n = 10
s = ""
for i in range(n):
    t = input()
    for j in range(n):
        if t[j] != '.':
            s += t[j]
print(s)

2、小红的数组变换

小红拿到了一个数组，她每次操作可以选择两个元素\(a_i,a_j\)，并选择\(a_i\)的一个因子\(x\)，然后将\(a_i\)变成\(a_i/x\)，将\(a_j\)变成\(a_j\times x\)。

小红想知道，是否可以通过有限次操作，使得数组中每个元素最多只包含一种素因子？

素因子的定义：若\(x\)能被\(p\)整除，且\(p\)是素数，则\(p\)为\(x\)的一个素因子。例如，\(12\)的素因子有\(2\)和\(3\)。

输入

第一行输入一个正整数\(t\)，代表询问次数。

接下来的\(2 \times t\)行，每\(2\)行为一次询问：

第一行输入一个正整数\(n\)，代表数组的大小。

第二行输入\(n\)个正整数\(a_i\)，代表数组的元素。

\(1\le t\le 10\)
\(1\le n\le 200000\)
\(1 \le ai \le 10^6\)
保证所有的\(n\)之和不超过\(200000\)

输出

输出\(t\)行，若可以通过有限次操作，使得数组中每个元素最多只包含一种素因子，则输出"Yes"。否则输出"No"。

样例

输入：
2
4
1 2 3 4
2
10 12

输出：
Yes
No

提示：
第一组询问，不需要任何操作，因为每个元素本身只含一种素因子。
第二组询问，显然是无解的。

解答

题目中提到的操作意味着可以将每一个数的质因子转移到另一个数中。因此，一种贪心的思想是：同一个下标的数汇聚所有同一个质因子。

因此，我们只需要分别对\(a\)中的每个数进行质因数分解，然后判断这些不同的质因子数量是否超过\(n\)即可，因为同一个质因子可以汇聚到不同的下标。

代码

import sympy


def solve(a):
    n = len(a)
    st = set()
    for x in a:
        st |= set(sympy.factorint(x).keys())
        if len(st) > n:
            return False
    return True


T = int(input())
for _ in range(T):
    input()
    a = list(map(int, input().split()))
    print("Yes" if solve(a) else "No")

3、小红的好字符串

小红定义一个字符串是“好字符串”，当且仅当其不包含任意长度不小于\(2\)的回文子串。例如，"abcda"是好字符串而"arcaea"则不是好字符串 (因为包含了回文子串"aea")。

现在小红拿到了一个字符串，她想知道有多少个非空子序列(可以不连续)是好字符串，你能帮帮她吗？

输入

一个字符串，仅包含小写字母。字符串长度不超过\(10^5\)。

输出

好子序列的数量。由于答案可能过大，请对\(10^9+7\)取模。

样例

输入：
aba

输出：
5

提示：
除了"aa"和”aba"以外，其余五个子序列均是合法的。

输入：
aaa

输出：
3

输入：
ghij

输出：
15

解答

如果一个字符串是好字符串，当且仅当这个字符串的任意相邻三个字符都不相同。因为，不存在长度为\(2\)的回文串意味着相邻两个字符不同，不存在长度为\(3\)的回文串意味着被一个字符隔开的两个字符不能相同。

因此，这道题我们可以使用动态规划进行解决。令\(f(i,j,k)(0\le i\le n,0\le j\le m,0\le k< m,i\neq j)\)表示\(s\)的长度为\(i\)的前缀中，有多少个好子序列满足：倒数第一个字符是第\(k\)个字符，倒数第二字符是第\(j\)个字符（如果子序列长度小于\(2\)，那么\(j=m\)）。其中\(m=26\)。令\(s_i\)表示字符串\(s\)中位置为\(i\)的字母的序数（从\(0\)到\(25\)），那么有以下初值：

\(f(0,\cdot,\cdot)=0\)，这是因为空字符串不会包含任何字符，没有任何符合条件的子序列。

它也有如下转移：

\(f(i-1,\cdot,\cdot)\rightarrow f(i,\cdot,\cdot)\)。这是因为第\(i\)个字符没有被使用。
\(f(i-1,j,k)\rightarrow f(i,k,s_i)\)，其中\(j\neq s_i,k\neq s_i\)，这是使用了第\(i\)个字符，并且要确保前面两个字符不是\(s_i\)。
\(f(i-1,m,k)+[s_i=k]\rightarrow f(i,m,k)\)，表示\(s_i\)自成一个子序列，其中\([]\)是一个示性函数，如果内部的布尔表达式的值为真，那么其值为\(1\)，否则为\(0\)。

因此，最终答案为\(\displaystyle{\sum_{j=0}^m\sum_{k=0}^{m-1} f(n,j,k)}\)。

代码

s = input()
m = 26
f = [[0 for _ in range(m)] for _ in range(m + 1)]
mod = 10 ** 9 + 7
for ch in s:
    x = ord(ch) - ord('a')
    for i in range(m + 1):
        if i != x:
            for j in range(m):
                if j != x:
                    f[j][x] += f[i][j]
                    if f[j][x] >= mod:
                        f[j][x] -= mod
    f[m][x] += 1
ans = (sum(f[i][j] for j in range(m) for i in range(m + 1))) % mod
print(ans)