P6002 [USACO20JAN] Berry Picking S

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

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

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

1
_, k = map(int, input().split())
2
a = list(map(int, input().split()))
3
ans = 0
4
for m in range(1, 1001):
5
    num = 0
6
    res = 0
7
    rest = []
8
    for x in a:
9
        num += x // m
10
        rest.append(x % m)
11
    if num >= k:
12
        res = m * k // 2
13
    elif num >= k // 2:
14
        res = (num - k // 2) * m + sum(sorted(rest, reverse=True)[:(k - num)])
15
    ans = max(ans, res)
1 collapsed line
16
print(ans)

Cow Frisbee S

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

1
from collections import deque
2

3
MAXN = int(1e6)
4

5
n = 0
6
ans = 0
7
a = [0] * (MAXN + 1)
8
s = deque()
9

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

14
for i in range(1, n + 1):
15
    while s and a[s[-1]] < a[i]:
7 collapsed lines
16
        ans += i - s[-1] + 1
17
        s.pop()
18
    if s:
19
        ans += i - s[-1] + 1
20
    s.append(i)
21

22
print(ans)

# [USACO19JAN] Icy Perimeter S

冰淇淋的面积用dfs很好求

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

难点在于求联通快的周长

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

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