Easy: A、B

Mid: E

Hard: D、C

AWC69#

Tasks - AtCoder Weekday Contest 0069 Beta

难度挺大的一场AWC，DEF都没做出来（菜菜/(ㄒoㄒ)/ ~~）

A/B-模拟

A题意：

给你N个股票，每个股票记录M天股价，计算股票的波动率，输出波动率最大的股票编号

按照题意模拟即可，值得注意的是max_设置要小于0（不会有人设置成0然后吃了一发WA吧？？（没错，就是我,,,,））

1
n,m = map(int,input().strip().split())
2
ans = 0
3
max_ = -1
4
for k in range(n):
5
    p = 0
6
    t = list(map(int,input().strip().split()))
7
    for i in range(1,m):
8
        p += abs(t[i] - t[i-1])
9
    if p > max_:
10
        max_ = p
11
        ans = k + 1
12
print(ans)

B题意：

给定N个数据，每个数据有T+C，选出K个，求T+C的最大值

模拟排序即可

1
n,k = map(int,input().split())
2
g = []
3
for _ in range(n):
4
    t,c = map(int,input().split())
5
    g.append(t + c)
6
g.sort(reverse = True)
7
print(sum(g[:k]))

C-贪心+差分

题意

有 $N$ 盏灯排成一行，初始状态由字符串 $S$ 给出（‘1’ 表示开，‘0’ 表示关）。
每次操作可以任意选择一个长度为 $K$ 的连续区间，将区间内所有灯的状态翻转（开变关，关变开）。
问：能否通过若干次操作使得所有灯都变成开的状态？如果能，最少需要多少次操作？如果不能，输出 -1。

题解

从左到右处理

如果某个位置的灯是关的，那么为了把它变成开，我们必须选择一个以它作为起点的长度为 $K$ 的区间进行翻转（因为后面的区间无法影响到它前面的位置，而前面的操作已经决定）。

这种“从左到右”的贪心策略可以保证每个位置只被考虑一次，并且不会影响已经处理好的左边部分。

翻转的奇偶性

每盏灯被翻转的次数决定了它的最终状态。初始状态为 1 的灯，经过奇数次翻转后变为 0，偶数次则保持 1；初始为 0 的灯则相反。

所以我们可以维护一个“当前累计翻转次数”的奇偶性，并结合初始状态判断当前灯是否需要额外翻转。

差分数组高效维护区间翻转

如果我们在位置 $i$ 进行一次翻转（即以 $i$ 为起点的长度为 $K$ 的区间），那么从 $i$ 到 $i+K-1$ 的灯都会受到一次影响。

为了快速知道当前位置的累计翻转次数，可以使用差分数组：

diff[i] 表示在位置 $i$ 处翻转次数的变化量。
用一个变量 cur 记录当前位置的累计翻转次数，遍历时 cur += diff[i]。
如果需要在位置 $i$ 开始新增一次翻转，则 cur++，并在 diff[i+K]--（表示在 $i+K$ 处翻转效果结束）。

算法步骤

将字符串 $S$ 转换为整数数组 a，a[i] = 1 表示开，0 表示关。
初始化差分数组 diff 长度为 $N+2$ （下标从 0 到 N+1）。
初始化 cur = 0（当前累计翻转次数的奇偶性），ans = 0。
遍历 i 从 0 到 $N-1$ $N - 1$ ：
- cur += diff[i]（累计到当前位置的翻转次数）。
- 当前灯实际状态 = a[i] ^ (cur % 2)（因为奇数次翻转会改变状态）。
- 如果实际状态 == 0（即当前灯是关的）：
  - 如果 i + K > N，说明无法以 i 为起点做一次长度为 $K$ 的翻转（超出右边界），则无解，输出 -1。
  - 否则：
    
    ans++（进行一次操作）
    
    cur++（增加一次翻转）
    
    diff[i+K]--（标记翻转效果在 i+K 处结束）
遍历结束后，输出 ans。

贪心正确性证明

必要性：当扫描到位置 $i$ 时，所有之前的位置已经处理成开的状态，并且不会再有操作影响它们（因为后续操作起点 ≥ i）。因此，如果当前灯是关的，必须立刻在 $i$ 开始一次翻转，否则它永远无法变开。
充分性：按照上述贪心，每次翻转都是必要的，且不会影响已经处理好的左边部分。因为翻转区间长度为 $K$ ，只会影响 $i$ 到 $i+K-1$ 的灯，而 $i$ 之后的灯尚未被处理，所以未来的操作可以纠正它们。因此贪心策略保证最少操作数。

1
def main():
2
    n, k = map(int, input().split())
3
    s = input().strip()
4
    a = [1 if ch == '1' else 0 for ch in s]
5
    diff = [0] * (n + 2)
6
    cur = 0
7
    ans = 0
8
    for i in range(n):
9
        cur += diff[i]
10
        if (a[i] + cur) % 2 == 0:
11
            if i + k > n:
12
                print(-1)
13
                return
14
            ans += 1
15
            cur += 1
16
            diff[i + k] -= 1
17
    print(ans)
18
if __name__ == "__main__":
19
    main()

D-区间覆盖+贪心

题意

有 N 个村庄，每个村庄有坐标 $X_i$ 和海拔 $P_i$ 。
一个村庄可以安装信号塔当且仅当 $P_i \geq K$ 。
信号塔可以覆盖距离 $D$ 以内的所有村庄（即村庄与塔的坐标差绝对值 ≤ D）。
目标是选择最少数量的塔，使得所有村庄都被至少一个塔覆盖。

题解

每个候选塔（海拔足够）对应一个覆盖区间： $[X_i - D, X_i + D]$ 。
每个村庄就是一个需要被覆盖的点（位置 $X_i$ ）。
我们需要用最少的区间覆盖所有点。

算法步骤

筛选可建塔的村庄：

对于每个村庄，如果 $P_i \geq K$ ，则生成区间 $[X_i - D, X_i + D]$ 。

如果没有可建塔的村庄且 N > 0，直接输出 -1。
排序：
- 将 points 按坐标升序排序。
- 将 intervals 按左端点升序排序。
贪心覆盖：
- 用指针 i 遍历 intervals，用指针 j 遍历 points。
- 初始化 ans = 0。
- 当 j < len(points) 时：
  - 设当前最左边未覆盖的点 cur = points[j]。
  - 找出所有左端点 ≤ cur 的区间，记录其中最大的右端点 max_r（移动 i 指针，同时更新 max_r）。
  - 如果 max_r < cur，说明没有区间能覆盖当前点，返回 -1。
  - 否则，ans++，然后跳过所有坐标 ≤ max_r 的点（即移动 j 直到 points[j] > max_r）。
- 输出 ans。

贪心正确性证明

贪心选择能覆盖当前最左点的最右区间，是因为这样能尽可能多地覆盖后面的点，从而最小化区间数。
由于区间按左端点排序，且我们每次只考虑能覆盖当前点的区间，保证了不会遗漏必要的区间。
如果存在可行解，贪心一定能找到最优解（这是区间覆盖问题的经典结论）。

1
def main():
2
    n, k, d = map(int, input().split())
3
    vil = []
4
    pos = []
5
    for _ in range(n):
6
        x, p = map(int, input().split())
7
        vil.append((x, p))
8
        pos.append(x)
9
    cur = []
10
    for x, p in vil:
11
        if p >= k:
12
            cur.append((x - d, x + d))
13
    if not cur:
14
        print(-1)
15
        return
16
    pos.sort()
17
    cur.sort(key=lambda x: x[0])
18
    i = j = ans = 0
19
    n = len(pos)
20
    m = len(cur)
21
    while j < n:
22
        curr = pos[j]
23
        max_r = -10 ** 18
24
        while i < m and cur[i][0] <= curr:
25
            max_r = max(max_r, cur[i][1])
26
            i += 1
27
        if max_r < curr:
28
            print(-1)
29
            return
30
        ans += 1
31
        while j < n and pos[j] <= max_r:
32
            j += 1
33
    print(ans)
34
if __name__ == "__main__":
35
    main()

E-离线 + 树状数组

题意

有一个图书馆，共有 $N$ 个书架，从左到右编号 $1$ 到 $N$ 。

每个书架 $i$ 有 $A_i$ 本书，修复完成日为 $D_i$ ，每本书借出费用为 $V_i$ 。

在修复完成日当天及之后，该书架上的所有书都可以借出。

现在有 $Q$ 个独立的借阅计划。每个计划指定一个连续书架区间 $[L_j, R_j]$ 和一个日期 $T_j$ 。

在该计划中，只有那些 $D_i \le T_j$ 的书架（即在该日期前已修复完成）上的所有书才会被借出。

每个书架 $i$ 借出后产生的费用为 $A_i \times V_i$ 。

对于每个计划，需要计算该区间内所有符合条件书架的费用总和。输出每个计划的结果。

题解

要求对每个查询 (L, R, T)，计算区间 [L, R] 内所有满足 D_i ≤ T 的书架的 A_i * V_i 之和。

将书架按修复日期 D_i 升序排序。
将查询按日期 T_j 升序排序。
使用一个树状数组（Fenwick Tree）维护：
- 初始时，树状数组为空（所有书架的权值都未加入）。
- 遍历排序后的查询，同时维护一个指针 p 指向书架列表。
- 对于当前查询的日期 T，将书架中所有 D_i ≤ T 的书架，将其权值 A_i * V_i 添加到树状数组的对应位置 i 上（单点更新）。
- 然后对当前查询的区间 [L, R] 用树状数组求区间和（前缀和相减），得到答案。

1
 class FenwickTree:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8

9
    def update(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13

14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20
def solve():
21
    n, q = map(int, input().split())
22
    book = []
23
    for i in range(1, n + 1):
24
        a, d, v = map(int, input().split())
25
        book.append((d, i, a * v))
26
    book.sort(key=lambda x: x[0])
27
    for _ in range(q):
28
        l, r, t = map(int, input().split())
29
        bit = FenwickTree(n)
30
        i = 0
31
        while i < n and book[i][0] <= t:
32
            _, pos, w = book[i]
33
            bit.update(pos, w)
34
            i += 1
35
        ans = bit.query(r) - bit.query(l - 1)
36
        print(ans)
37
if __name__ == "__main__":
38
    solve()

1
import sys
2
class FenwickTree:
3
    def __init__(self, length):
4
        self.length = length
5
        self.tree = [0] * (length + 1)
6
    def lowbit(self, x):
7
        return x & -x
8
    def update(self, idx, val):
9
        while idx <= self.length:
10
            self.tree[idx] += val
11
            idx += self.lowbit(idx)
12
    def query(self, idx):
13
        res = 0
14
        while idx > 0:
15
            res += self.tree[idx]
16
            idx -= self.lowbit(idx)
17
        return res
18
def solve():
19
    input = sys.stdin.readline
20
    n, q = map(int, input().split())
21
    books = []
22
    for i in range(1, n + 1):
23
        a, d, v = map(int, input().split())
24
        books.append((d, i, a * v))
25
    books.sort(key=lambda x: x[0])
26
    queries = []
27
    for idx in range(q):
28
        l, r, t = map(int, input().split())
29
        queries.append((t, l, r, idx))
30
    queries.sort(key=lambda x: x[0])
31
    bit = FenwickTree(n)
32
    ans = [0] * q
33
    ptr = 0
34
    for t, l, r, qid in queries:
35
        while ptr < n and books[ptr][0] <= t:
36
            _, pos, w = books[ptr]
37
            bit.update(pos, w)
38
            ptr += 1
39
        ans[qid] = bit.query(r) - bit.query(l - 1)
40

41
    sys.stdout.write("\n".join(map(str, ans)))
42

43
if __name__ == "__main__":
44
    solve()

音乐

音乐

AWC69#

音乐

目录

音乐

音乐

AWC69-贪心+差分/区间覆盖+贪心/离线处理+树状数组

AWC69#

音乐

目录