how to

P6002 [USACO20JAN] Berry Picking S

Dec 14, 2024
notesjulyfun工作william241214
2 Minutes
368 Words

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裸题了

Article title:P6002 [USACO20JAN] Berry Picking S
Article author:Julyfun
Release time:Dec 14, 2024
Copyright 2025
Sitemap