第一题

数组中两个元素和小于等于M的组合数

对于一个整型数组，里面任何两个元素相加，小于等于M的组合有多少种?

如果有符合的，输出组合对数？没有，输出0；

输入：

输入有2行，第1行为int整型数组，第二行为M值，且M也为int

比如：

7 -1 -1

9

表示数组为[7,-1,-1]，M为9

输出：

3

解释：（7，-1）、（7，-1）、（-1，-1）共3种

不同位置相同的元素值，可以组成不同的组合

解法1：

直接暴力，O(n^2)

def force():
    nums=list(map(int,input().split(' ')))
    M=int(input())

    n=len(nums)
    res=0
    for i in range(n):
        for j in range(i+1,n):
            if(nums[i]+nums[j]<=M):res+=1
    return res

解法2：

先降序排列，在一次遍历的时候，二分查找M-n在数组中的位置；

写了一半，有时间补上

def binary_search():
    nums=list(map(int,input().split(' ')))
    M=int(input())
    nums.sort(reverse=True)
    for n in nums:
        pos=bisect.bisect(nums,M-n)
        print(pos)

第三题

计算K位

给你两个正整数n和K，其中1<=n<=26，字符串Sn的形成规则如下：

Li表示26个字符a-z，依次是

L1=’a’

L2=’b’

……

L26=’z’

S1=’a’

当i>1时，Si=S(i-1) + Li + reverse(invert(S(i-1) ))

其中 + 表示字符串的连接，reverse(x)为反转x，invert(x)为翻转x中的每一位，如’a’ 翻转为’z’, ‘b’翻转为 ‘y’ …… ‘z’翻转为 ‘a’

由此有

S1=’a’

S2=’abz’

S3=’abzcayz’

S4=’abzcayzdabzxayz’

输入：

输入有1行，为n和k

如：

3,1

输出：

a

解释：S3的第1个字符为a

解法1：

正常思路，因为存在递推关系，直接打表用dp[i]存字符串Si

按 Si=S(i-1) + Li + reverse(invert(S(i-1) )) 递推式直接推出所有S串

n,k=map(int,input().split(','))

dic={i:chr(i+ord('a')) for i in range(26)}
inv={dic[i]:dic[25-i] for i in range(26)}

def invert(s):
    res=''
    for i in s:
        res+=inv[i]
    return res

dp=[None for _ in range(27)]
dp[1]='a'

for i in range(2,n+1):
    dp[i]=dp[i-1]+dic[i-1]+invert(dp[i-1])[::-1]

print(dp[n][k-1])

解法2：

观察得出的Si串，可以发现 reverse(invert(S(i-1) )) 与 S(i-1) 仅有中间的一个字符不同，且前者中间字符为后者中间字符的翻转

由此更改invert函数，进一步降低时间复杂度

n,k=map(int,input().split(','))

dic={i:chr(i+ord('a')) for i in range(26)}
inv={dic[i]:dic[25-i] for i in range(26)}

def invert(s):
    res=list(s[:])
    pos=int(len(s)/2)
    if pos>=0:
        tmp=res[pos]
        res[pos]=inv[tmp]
    return ''.join(res)

dp=[None for _ in range(27)]
dp[1]='a'

for i in range(2,n+1):
    dp[i]=dp[i-1]+dic[i-1]+invert(dp[i-1])

print(dp[n][k-1])

补充知识：

bisect库是python中针对有序列表的一个模块，接收已排序列表作为参数。

其中包括：

bisect.bisect(a,x)（默认等同于bisect.bisect_right())
bisect.bisect_left(a,x)
bisect.insort(a,x)
bisect.insort_right(a,x)
bisect.insort_left(a,x)

(insort不要记成insert)