OPPO笔试题解 0826后端A卷

T1 环状数组权值，T2 OPPO元音辅音字符串，T3因数操作次数，3道100%，写题解不易，有帮助欢迎点赞评论

T1：环形数组最大贡献

数据量不大，双循环遍历即可。

时间复杂度 , 空间复杂度.时空复杂度不计算输入输出相关，下同。

参考代码：

n = int(input())
nums = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i, n):
        ans = max(ans, (nums[i]+nums[j])*min(j-i, i+n-j))
print(ans)

T2：OPPO型字符串

要求计算“元辅辅元”类型子序列数目，不要求连续。

思考一下，如果当前字符是O，我们怎么得到以这个O为结尾的OPPO的个数？如果我们手里有之前的OPP的个数，就很好解决了。同样的，OPP的个数可以由OP的个数得来，以此类推。

因此我们使用动态规划求解，遍历字符串，记录“元”“元辅”“元辅辅”字符串的数量即可。

我们首先给元音辅音分别标号；之后设立三个数组，dp1[i]为元音i（编号为i的元音）构成的“元”字符串数量，dp2[i][j]为元音i与辅音j构成的“元辅”字符串数量，dp3[i][j]为元音i与辅音j构成的“元辅辅”字符串数量。

时间复杂度 ，其中 表示元音/辅音字符集的大小，在本题中分别是5和21；空间复杂度 .

参考代码：

from collections import defaultdict
vowels = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}
consos = {}

index = 0
for i in range(26):
    if chr(ord('a')+i) not in vowels:
        consos[chr(ord('a')+i)] = index
        index+=1

dp1 = [0]*5
dp2 = [[0]*21 for _ in range(5)] 
dp3 = [[0]*21 for _ in range(5)]

ans, mod = 0, 10**9+7
s = input()
for c in s:
    if c in vowels:
        i = vowels[c]
        dp1[i] += 1
        for j in range(21):
            ans = (ans + dp3[i][j])%mod
    else:
        j = consos[c]
        for i in range(5):
            dp3[i][j] = (dp3[i][j] + dp2[i][j])%mod
            dp2[i][j] = (dp2[i][j] + dp1[i])%mod
print(ans)

T3：使得因子数目最接近K的最小操作次数

对于给定数组的乘积x，一次操作是将x乘2或除以2（如果是偶数），直到x的因子数目最接近给定的数k为止，求最少操作次数。

首先明确一点：在x的操作序列{···, x/4, x/2, x, x*2, x*4, ···}中，因子数目越来越大。也就是说，x的因子数目如果小于k，那么我们应当不断把x乘以2，反之不断除以2。

给定一个数x，它的因子数量怎么算？最粗暴的方式就是枚举，时间复杂度为 ，而题目数组元素最大为10000，最多100个元素，乘积大小是，显然不现实。

这里需要一个引理：对于任意的整数N，分解质因数得到，则N的因子个数M为 。

详细证明可以到网上去看，简单说下就是对于质因子有种选择，以此类推。如数12的质因子有2个2,1个3，那么我们可以取0个2、0个3相乘得到1，取0个2、1个3相乘得到3，取1个2、0个3相乘得到2，取1个2、1个3相乘得到6，取2个2、0个3相乘得到4，取2个2、1个3相乘得到12，这些都是12的因子。

我们可以发现，x是由数组的元素乘出来的，它的质因数其实就是数组元素质因数之和。这样的话我们分别获取数组元素的质因数，就能得到x的质因数，通过它就能得到因子数量，时间复杂度只有 ，其中c是数组元素最大值。

那么新的问题来了，我们能得到x的因子数，怎么得到x*2的因子数呢？仍然用上面的引理，x*2的质因数比x的多了一个2而已。

如果x的因子数为，假设对应x的质因数中2的个数，

那么x*2的因子数为，

相比于M多了一项，而在x变化时是始终不会变的， 它只跟x中非2的质因子数量有关系。

x乘几次2，就多几个，除几次2，就少几个。那么我们只需要关心k和x中间有多少就可以啦。

时间复杂度：，其中c是数组元素最大值；空间复杂度：，即我们存放质因数的map。

参考代码：

from collections import defaultdict

n, k = map(int, input().split())
nums = list(map(int, input().split()))
factors = defaultdict(int)
for num in nums:
    tmp, i = num, 2
    while i*i<=tmp:
        while tmp%i==0:
            factors[i]+=1
            tmp//=i
        i+=1
    factors[num] += 1

non_2 = 1
for key,val in factors.items():
    if key!=2:
        non_2*=val+1
cur = (factors[2]+1)*non_2

a1, a2 = 0, 0
if cur<k:
    a1 = round((k-cur)/non_2)
elif cur>k:
    a2 = min(round((cur-k)/non_2), factors[2])
print(str(a1)+" "+str(a2))