蓝桥杯刷题--python-20-多路归并，贡献法

1262. 鱼塘钓鱼 - AcWing题库

n=int(input())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
l=[0]+list(map(int,input().split()))
spend=[0 for i in range(n+1)]
for i in range (1,n):
    l[i]+=l[i-1]
t=int(input())

def get(k):
    return max(0,a[k]-b[k]*spend[k])

def work(n,t):
    global spend
    res=0
    spend=[0 for i in range(len(spend))]

    for i in range(t):
        T=1
        for j in range(2,n+1):
            if (get(T)<get(j)):
                T=j
        res+=get(T)
        spend[T]+=1
    return res

res=0
for i in range(1,n+1):
    res=max(res,work(i,t-l[i-1]))

print(res)

 4261. 孤独的照片 - AcWing题库

n = int(input())
s = list(input())
l = [0 for _ in range(n)]
r = [0 for _ in range(n)]

# 预处理
sh = 0
sg = 0
for i in range(n):
    if s[i] == 'G':
        l[i] = sh;sg += 1;sh = 0
    else:
        l[i] = sg;sh += 1;sg = 0
sh = 0
sg = 0
for i in range(n - 1, -1, -1):
    if s[i] == 'G':
        r[i] = sh;sg += 1;sh = 0
    else:
        r[i] = sg;sh += 1;sg = 0

res = 0
for i in range(n):
    res += l[i] * r[i] + max(r[i] - 1, 0) + max(l[i] - 1, 0)
print(res)
 

 2868. 子串分值 - AcWing题库

 

str=[0]+list(input())
n=len(str)
l=[0 for _ in range(n)]
r=[0 for _ in range(n)]

p=[0 for i in range(26)]
for i in range(1,n):
    t=ord(str[i])-ord('a')
    l[i]=p[t]
    p[t]=i
for i in range(26):
    p[i]=n
for i in range(n-1,0,-1):
    t = ord(str[i]) - ord('a')
    r[i]=p[t]
    p[t]=i
res=0
for i in range(1,n):
    res+=(i-l[i])*(r[i]-i)
print(res)