AWC65#

絮叨#

经过AWC64的板子后也是回到了AWC对我来说的正常难度，和ABC一样只能AC前三道（wa）

E赛时是可做的，但是我饿了，吃饭去了(hhhhh）

D给的是曼哈顿距离，问题要求的看出来了是~~二维前缀和~~，但是这个距离不太会，遂放弃,,,,,,

难度#

Easy: A,B,C

Mid: E

Hard: D

AtCoder Weekday Contest 0065 Beta - AtCoder

A-模拟#

题意大概是对于序列的每一个值判断是k的多少倍即可

1
n,k = map(int,input().split())
2
a = list(map(int,input().split()))
3
ans = 0
4
for i,x in enumerate(a):
5
    ans += x
6
    if i != n and i >= k and i % k == 0:
7
        ans += 1
8
print(ans)

B-模拟#

题意就是找到第一个大于x的pos

1
n,k = map(int,input().split())
2
a = list(map(int,input().split()))
3
cur = 0
4
ans = -1
5
for i,x in enumerate(a):
6
    cur += x
7
    if cur >= k:
8
        ans = i + 1
9
        break
10
print(ans)

C-DP#

入门级dp，打家劫舍换皮，需要注意dp的设计

1
n = int(input())
2
a = list(map(int, input().split()))
3
if n == 1:
4
    print(max(0, a[0]))
5
else:
6
    dp = [0] * n
7
    dp[0] = max(0, a[0])
8
    dp[1] = max(dp[0], a[1])
9
    for i in range(2, n):
10
        dp[i] = max(dp[i-1], dp[i-2] + a[i])
11
    print(max(dp))

D-马哈顿距离+二维前缀和#

题意：

平面上有 $N$ 个商店，每个商店有坐标 $(X_i, Y_i)$ 和销售额 $C_i$ 。
有 $M$ 个配送中心候选点，每个候选点有坐标 $(P_j, Q_j)$ 和配送距离 $K_j$ （曼哈顿距离）。
如果商店与配送中心的曼哈顿距离 $\le K_j$ ，则该商店可被配送。
对每个候选点，求可配送商店的销售额总和。

题解：

曼哈顿距离的覆盖区域是一个菱形

可以通过坐标变换将其转化为矩形，使用二维前缀和快速查询。

曼哈顿距离：

|x - P| + |y - Q| \le K

令：

u = x + y, \quad v = x - y

则：

|x-P|+|y-Q| = \max(|u - (P+Q)|, |v - (P-Q)|)

曼哈顿距离 $\le K$ 等价于：

|u - (P+Q)| \le K \quad \text{且} \quad |v - (P-Q)| \le K

因此，每个商店变换为点 $(u, v)$ ，每个候选对应矩形查询：

U_1 = P+Q - K,\ U_2 = P+Q + K

V_1 = P-Q - K,\ V_2 = P-Q + K

注意 $v$ 可能为负数，需要平移（加偏移量）使其非负。

读入所有商店，计算每个商店的 $u = x+y$ ， $v = x-y + \text{offset}$ （offset 取 1000 或更大），将销售额累加到二维数组 grid[u][v]

对 grid 做二维前缀和 pre

对于每个候选，计算矩形边界，利用前缀和 $O(1)$ 查询总和

1
n,m = map(int,input().split())
2
of = 1000
3
max_u = max_v = 2000
4
grid = [[0]*(max_v + 5) for _ in range(max_u + 5)]
5
for _ in range(n):
6
    x,y,c = map(int,input().split())
7
    u = x + y
8
    v = x - y + of
9
    grid[u][v] += c
10
pre = [[0]*(max_v + 10) for _ in range(max_u + 10)]
11
for i in range(max_u + 5):
12
    for j in range(max_v + 5):
13
        pre[i][j] = grid[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]
14
for _ in range(m):
15
    p,q,k = map(int,input().split())
16
    u0 = p + q
17
    v0 = p - q + of
18
    u1 = max(0,u0 - k)
19
    u2 = min(max_u,u0 + k)
20
    v1 = max(0,v0 - k)
21
    v2 = min(max_v,v0 + k)
22
    ans = pre[u2][v2] - pre[u1-1][v2] - pre[u2][v1-1] + pre[u1-1][v1-1]
23
    print(ans)

E-双端队列+滑动窗口#

题意：

给定长度为 $N$ 的整数数组 $H$ ，需要找到最长的连续子数组，使得该子数组内最大值与最小值的差 ≤ $D$ ，并且子数组长度至少为 $K$ 。如果不存在，输出 -1。

题解：

使用两个单调队列分别维护窗口内的最大值和最小值

随着右指针 r 向右移动，更新两个队列

如果当前窗口内的最大值与最小值之差 > $D$ ，则移动左指针 l 缩小窗口，直到差值 ≤ $D$

每次满足差值 ≤ $D$ 时，更新答案 ans = max(ans, r - l + 1)，但只考虑长度 ≥ $K$ 的窗口

1
from collections import deque
2
n,k,d = map(int,input().split())
3
h = list(map(int,input().split()))
4
maxq = deque()
5
minq = deque()
6
ans = -1
7
l = 0
8
for r in range(n):
9
    while maxq and h[maxq[-1]] < h[r]:
10
        maxq.pop()
11
    maxq.append(r)
12
    while minq and h[minq[-1]] > h[r]:
13
        minq.pop()
14
    minq.append(r)
15
    while maxq and minq and h[maxq[0]] - h[minq[0]] > d:
16
        if maxq[0] == l:
17
            maxq.popleft()
18
        if minq[0] == l:
19
            minq.popleft()
20
        l += 1
21
    cur = r - l + 1
22
    if cur >= k:
23
        ans = max(ans,cur)
24
print(ans)

音乐

音乐