Cow Frisbee S
2024-12-21
241221julyfunnoteswilliam工作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)P2997 [USACO10NOV] Banner Shttps://www.luogu.com.cn/problem/P2997平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内枚举 dx, dy, dx 与 dy 互质即可。def gcd(a: int, b: int):
return b if a % b == 0 else gcd(b, a % b)
n, m, l, r = map(int, input().split())
answer = 0
for i in range(1, n + 1):
for j in range(1, m + 1):
if gcd(i, j) == 1 and l * l <= i * i + j * j <= r * r:
answer += 2 * (n - i + 1) * (m - j + 1)
if l == 1:
answer += n * (m + 1) + (n + 1) * m
print(answer)# [USACO19JAN] Icy Perimeter S冰淇淋的面积用dfs很好求只要算出每个联通块中'#'的个数即可难点在于求联通快的周长观察一下样例 发现周长就是每个'#'周围'.'或超过边界的方块个数解决这一问题后这道题几乎就是一道dfs裸题了2, 3 is ok(0 , 0) (6, 9)
判断所有的 dx, dy 是否满足互质，如果是互质就可以选择W * H 插满杆子 dx = 2, dy = 3def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
gcd(a=60, b=24) return 12
-> gcd(24, 12) return 12
-> gcd(12, 0) return 12(2, 3)for dx in range(0, W):
for dy in range(0, H):
判断 dx, dy 是否互质 即 gcd(dx, dy) == 1
如果是互质就 continue
w = W - dx + 1
h = H - dy + 1
ans += w *