每日一题 3.3-3.9

2025-03-08 · 4 分钟阅读 · 算法模拟贪心策略差分二分查找前缀和 ·

复制链接:

文章目录

题目来自 AcWing

感觉每日一题越来越简单，代码量也越来越短。第一周优化暴力枚举的题目兼具创新性和挑战性，而这周的题目几乎不需要“深度求索”。

5525. 炮弹 | 原题链接

只需要把情况模拟一下就行了。唯一要注意的是，如果 Bessie 陷入了死循环就直接输出。判断死循环的方式也特别简单，每次弹跳后将当前的位置、能量、方向存储进一个集合（in 关键字访问集合的时间复杂度为 $O(1)$），同时每次弹跳前查看此次弹跳是否已经被记录。

 1N, S = map(int, input().strip().split())
 2field = [0] * N
 3cate = [0] * N
 4S -= 1
 5targets = 0
 6for i in range(N):
 7    qi, vi = map(int, input().strip().split())
 8    cate[i] = qi
 9    field[i] = vi
10    targets += qi
11
12memo = set()
13count = 0
14power = 1
15directions = {1: -1, -1: 1}
16d = 1
17while 0 <= S < N:
18    if cate[S] == 1:
19        if field[S] >= 0 and power >= field[S]:
20            field[S] = -1
21            count += 1
22        S += d * power
23    else:
24        power += field[S]
25        d = directions[d]
26        S += d * power
27
28    if (S, d, power) in memo:
29        break
30    memo.add((S, d, power))
31print(count)

5526. 平衡细菌 | 原题链接

这道题的题意是，给出一个数列 $a$，每次操作可以将数列从右向左的 $n$（$n$ 不能大于数列）个元素依次加上或减去 $n,n-1,n-2\cdots 1$，求出将整个数列所有元素都变成 $0$ 所需最少的操作次数。

不难发现，数列最左侧的数是最不好修改的，这个数每次只能加上或者减去 $1$，然后操作其右侧的数……以此类推，这个数列应该是从右向左逐个变成 $0$ 的。

而至于具体操作，对原数组的某一段加上一个公差为 $1$ 的等差数列，就是对其差分数组的某一段全部加上 $1$，进而是其二阶差分数组中的点操作。也就是说在原数组的某一段上加等差数列的操作可以通过二阶差分在 $O(1)$ 的时间内完成。

因为原数组与差分数组的首项相同，因此当差分数组的全部为 $0$ 时，原数组也必然全部为 $0$。因此可以判断，我们并不需要真的将原数组的每一项变为 $0$，而只需将二阶差分数的每一项都变成 $0$ 即可（这道题中对二阶差分数组做点操作合法，而对一阶差分数组做点操作不合法），也就是计算二阶差分数组各项绝对值之和。

 1n = int(input().strip())
 2nums = (0,) + tuple(map(int, input().strip().split()))
 3diff_1 = list(0 for _ in range(n))
 4for i in range(1, n + 1):
 5    diff_1[i - 1] = nums[i] - nums[i - 1]
 6diff_1 = [0] + diff_1
 7ans = 0
 8for i in range(1, n + 1):
 9    ans += abs(diff_1[i] - diff_1[i - 1])
10print(ans)

5538. 回文游戏 | 原题链接

这道题像是脑筋急转弯一样。首先看到这道题 $10^{10^5}$ 的数据范围时我就知道这道题不简单，这么大的数连 Python 都没法存。之前做过类似的题目，但是是两人只能拿走某个范围内任意数量的石子，按照最优策略判断最后的胜者。而最优策略就是，尽量使得剩余棋子是这个范围上界与下界之和的整数倍。

对于这道题，最优策略是每次拿完都使剩余石子数量为 10 的倍数，这是因为 1-9 数量的石子可以任意取，而 10 的倍数的数量的石子又不可能被取走。因此如果初始石子数量为 10 的倍数则先手胜，否则后手胜利。

1t = int(input().strip())
2for _ in range(t):
3    print("E" if input().strip()[-1] == '0' else "B")

5539. 牛奶交换 | 原题链接

观察发现，对于一段连续的“R”，随着时间变化，牛奶会向右侧聚集，而左侧的牛奶会持续减少直至消失；对于一段连续的“L”同理。同时还能够发现，对于一组“RL”来说，这两桶牛奶的数量永远不会变化。因此解决这道问题，需要遍历 LR 序列并找到其中的 “LR” 组合，然后从这里向两侧遍历，直到时间全部消耗完或者遇到数量恒定的 “RL” 边界。

 1n, m = map(int, input().strip().split())
 2ops = input().strip()
 3init = list(map(int, input().strip().split()))
 4
 5
 6def get(x):
 7    return x % n
 8
 9
10for i in range(n):
11    if ops[get(i)] == "L" and ops[get(i + 1)] == "R":
12        l, r = i, i + 1
13        lm = rm = m
14        while lm > 0 and ops[get(l - 1)] == "L":
15            diff = min(lm, init[get(l)])
16            init[get(l)] -= diff
17            lm -= diff
18            l -= 1
19        while rm > 0 and ops[get(r + 1)] == "R":
20            diff = min(rm, init[get(r)])
21            init[get(r)] -= diff
22            rm -= diff
23            r += 1
24
25print(sum(init))

5540. 最大限度地提高生产力 | 原题链接

题意是要判断通过 $c_i-tt_i$ 得到的序列 $rest$ 中大于 $S$ 的元素是否不少于 $V$ 个。判断列表中某个区间内元素数量可以通过二分查找或者前缀和实现。

二分查找判断的是列表中第一个大于等于 $S$ 的元素的下标 $i$，再用 $n-i$ 就是列表中大于 $S$ 的元素数量：

 1n, q = map(int, input().strip().split())
 2c = tuple(map(int, input().strip().split()))
 3t = tuple(map(int, input().strip().split()))
 4rest = [c[i] - t[i] for i in range(n)]
 5rest.sort()
 6
 7for _ in range(q):
 8    v, s = map(int, input().strip().split())
 9    l, r = 0, n
10    while l < r:
11        mid = (l + r) >> 1
12        if rest[mid] <= s:
13            l = mid + 1
14        else:
15            r = mid
16    print("YES" if n - l >= v else "NO")

用 bisect.bisect_right 函数反而会超时，能通过 16/17 个测试点：

 1from bisect import bisect_right as b_r
 2
 3n, q = map(int, input().strip().split())
 4c = tuple(map(int, input().strip().split()))
 5t = tuple(map(int, input().strip().split()))
 6rest = [c[i] - t[i] for i in range(n)]
 7rest.sort()
 8
 9for _ in range(q):
10    v, s = map(int, input().strip().split())
11    print("YES" if n - b_r(rest, s) >= v else "NO")

前缀和做法中需要注意列表中最小值可能会小于 0，甚至列表中最大元素也可能会小于 0，因此设置一个偏移量 offset 以确保每个元素都能存储进 cnt 数组。为了图方便，我直接将 offset 设置为列表中最小值的相反数，这样如果列表中最小值为正，还能够节省一部分空间。如果最后访问前缀和数组中 s + offset + 1 越界则说明原列表中没有大于 S 的元素，直接输出“NO”。

 1n, q = map(int, input().strip().split())
 2c = tuple(map(int, input().strip().split()))
 3t = tuple(map(int, input().strip().split()))
 4rest = [c[i] - t[i] for i in range(n)]
 5rest.sort()
 6offset = -min(rest)
 7cnt = [0] * (max(rest) + offset + 1)
 8for i in range(n):
 9    cnt[rest[i] + offset] += 1
10prefsum = [0]
11for i in range(len(cnt)):
12    prefsum.append(prefsum[-1] + cnt[i])
13
14for _ in range(q):
15    v, s = map(int, input().strip().split())
16    if s + offset + 1 >= len(prefsum):
17        print("NO")
18        continue
19    print("YES" if n - prefsum[s + offset + 1] >= v else "NO")