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)

https://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 = 3

def 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 * h

Cow Frisbee S

P2997 [USACO10NOV] Banner S

# [USACO19JAN] Icy Perimeter S