百度笔试 1019

第一题

题目描述：

我们可能听过“短板效应”这一说法：一只水桶能盛多少水，并不取决于最长的那块木板，而是取决于最短的那块木板。

小明在完成某个小组任务时，也出现了类似的情况。小明的班级有n个人排成一行，每个人有一个能力值aᵢ，每连续i个人都在一个大小为i的组里，一个人会在很多个组。例如1,2,3,4,5，五个人依次排成一行，有1,2,3；2,3,4；3,4,5这三个大小为3的组，有1,2,3,4；2,3,4,5这两个大小为4的组。一个组的能力值为组里所有人能力值的最小值，小明作为班长想对于所有1≤x≤n求出所有大小为x的组的能力值的最大值为多少。

输入描述：

第一行一个正整数n，表示班级中的人数。(1≤n≤100000)

接下来一行n个整数，表示a₁,a₂……aₙ，依次表示每个人的能力值。(1≤aᵢ≤10⁹)

输出描述：

输出一行n个整数，分别表示大小为1,2,……,n的所有组能力值最大值为多少。

样例输入：

6

4 5 3 1 3 4

样例输出： 5 4 3 1 1 1

n = int(input())
a = list(map(int, input().split()))

left = [-1] * n
right = [n] * n

stack = []
# 找左边第一个比它小的元素
for i in range(n):
    while stack and a[stack[-1]] >= a[i]:
        stack.pop()
    left[i] = stack[-1] if stack else -1
    stack.append(i)

stack = []
# 找右边第一个比它小的元素
for i in range(n-1, -1, -1):
    while stack and a[stack[-1]] >= a[i]:
        stack.pop()
    right[i] = stack[-1] if stack else n
    stack.append(i)

res = [0] * (n+1)

for i in range(n):
    length = right[i] - left[i] - 1
    res[length] = max(res[length], a[i])

# 填补答案
for i in range(n-1, 0, -1):
    res[i] = max(res[i], res[i+1])

print(' '.join(map(str, res[1:])))

第二题

公共前后缀

题目描述

有两个小朋友玩词语接龙游戏，他们只认识两个字符串。若小明先说出长度为n的字符串s，小红只能说长度为m的字符串t（相反的，若小明先说出t，小红只能说s）。

游戏中定义小红的得分为k，其中k是最大的满足“小明所说字符串的后k位”和“小红所说字符串的前k位”是一样的这一前提的数字。例如小明说s、小红说t时，小红的得分即为s[n-k+1]~s[n]==t[1]~t[k]

小明想知道他应该说哪个字符串，才能让小红的得分最少，请你输出最少的得分即可。

输入描述

两行，每行一个仅包含小写字母的字符串，代表小明和小红当前认识的两个字符串。

1≤字符串长度≤1000

输出描述

输出小红可能获得的最少得分。

样例输入

ababab

babaa

样例输出

1

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j > 0 and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi

s = input().strip()
t = input().strip()

def overlap(a, b):
    combined = b + "#" + a
    pi = prefix_function(combined)
    return pi[-1]

k1 = overlap(s, t)
k2 = overlap(t, s)

print(min(k1, k2))