P6002 [USACO20JAN] Berry Picking S

所以有前 k / 2号元素都是一个相同值

枚举这个值m，有三种情况

最多能取出k个m，则前所有元素均为 m
最多能取小于 k / 2 个 m，无解
否则尽可能取多个 m，剩下部分取最大的即可.

_, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for m in range(1, 1001):
    num = 0
    res = 0
    rest = []
    for x in a:
        num += x // m
        rest.append(x % m)
    if num >= k:
        res = m * k // 2
    elif num >= k // 2:
        res = (num - k // 2) * m + sum(sorted(rest, reverse=True)[:(k - num)])
    ans = max(ans, res)
print(ans)

Cow Frisbee S

维护一个单调栈，每进入一个数 ai，就向前扫描直到遇见一个 s_top>ai，由于有 ai 挡着，所以之后的我们全部都看不见，此时最终答案加上 (i−stop+1)。

from collections import deque

MAXN = int(1e6)

n = 0
ans = 0
a = [0] * (MAXN + 1)
s = deque()

n = int(input())
for i in range(1, n + 1):
    a[i] = int(input())

for i in range(1, n + 1):
    while s and a[s[-1]] < a[i]:
        ans += i - s[-1] + 1
        s.pop()
    if s:
        ans += i - s[-1] + 1
    s.append(i)

print(ans)

# [USACO19JAN] Icy Perimeter S

冰淇淋的面积用dfs很好求

只要算出每个联通块中'#'的个数即可

难点在于求联通快的周长

观察一下样例发现周长就是每个'#'周围'.'或超过边界的方块个数

解决这一问题后这道题几乎就是一道dfs裸题了