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)

https://www.luogu.com.cn/problem/P2997

1
平面上有(0,0)到(n,m)的(n+1)*(m+1)个点。问有多少点对所连的线段不过其他点，且长度在[l,h]范围内

枚举 dx, dy, dx 与 dy 互质即可。

1
def gcd(a: int, b: int):
2
    return b if a % b == 0 else gcd(b, a % b)
3

4
n, m, l, r = map(int, input().split())
5
answer = 0
6
for i in range(1, n + 1):
7
    for j in range(1, m + 1):
8
        if gcd(i, j) == 1 and l * l <= i * i + j * j <= r * r:
9
            answer += 2 * (n - i + 1) * (m - j + 1)
10
if l == 1:
11
    answer += n * (m + 1) + (n + 1) * m
12
print(answer)

# [USACO19JAN] Icy Perimeter S

冰淇淋的面积用dfs很好求

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

难点在于求联通快的周长

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

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

2, 3 is ok

(0 , 0) (6, 9) 判断所有的 dx, dy 是否满足互质，如果是互质就可以选择

W * H 插满杆子 dx = 2, dy = 3

1
def gcd(a, b):
2
    if b == 0:
3
        return a
4
    return gcd(b, a % b)
5

6
gcd(a=60, b=24) return 12
7
-> gcd(24, 12) return 12
8
-> gcd(12, 0) return 12

(2, 3)

1
for dx in range(0, W):
2
    for dy in range(0, H):
3
        判断 dx, dy 是否互质 即 gcd(dx, dy) == 1
4
        如果是互质就 continue
5
        w = W - dx + 1
6
        h = H - dy + 1
7
        ans += w * h

Cow Frisbee S

Cow Frisbee S

P2997 [USACO10NOV] Banner S

# [USACO19JAN] Icy Perimeter S