官方题解｜挑战赛#8
2024-08-19 11:09:51
发布于：广东
ACGO 第 8 次挑战赛题解
本场比赛后 题在 的 下很难通过，但本文给出的代码，在 下，保证能够在时限内通过。
题解简述
以下提供每道题目的思路简述和 代码，详细题解的 AC 代码，请点击题目标题查看。
A - 交集
本题可以使用很多方法解决，这里使用集合的思想来获取两个线段的交集：
- 令交集的左端点为 ，右端点为 。
- 那么 。
对于本题，若 则交集存在，交集的线段长度为 ，否则交集不存在，长度为 。
语法小课堂
-
使用
std::max(a, b)可以获取a和b中较大的那个；反之使用std::min(a, b)可以获取a和b中较小的那个。
注意：a和b的类型一定要严格一致，并且int和long long会被认为是两种完全不同的类型。 -
条件运算符：
E1 ? E2 : E3。若E1为true则表达式的结果为E2，否则为E3。
l1, r1, l2, r2 = map(int, input().split())
print(max(min(r1, r2) - max(l1, l2), 0))
B - 比赛结果
我们可以使用一个 std::string 数组 mat 来存储比赛对局的情况。
然后使用一个二重循环遍历这个 std::string 数组 mat，对于每个 ，检查 mat[i][j] 和 mat[j][i] 是否存在矛盾；
若根据题目检查发现矛盾则直接输出 incorrect，并使用 return 0 直接退出程序（ 可以使用 exit(0)）。
若执行完整个二重循环后，并没有退出程序，则说明比赛结果是正确的，输出 correct 即可。
语法小课堂
-
std::vector可以当作普通的数组来使用，在效率上几乎与普通数组相当，而且操作和功能更为强大。 -
基于范围的
for循环：使用for (auto x : mat)可以方便地遍历许多 容器。类似于 中的for x in mat:。 -
此处使用的
for (auto &x : arr)多了一个&为 引用，表示可以对mat中的元素进行直接修改，而不加&则仅为复制（值传递）。
n = int(input())
mat = [input() for i in range(n)]
for i in range(n):
for j in range(n):
a, b = mat[i][j], mat[j][i]
if a == 'W' and b != 'L' or\
a == 'L' and b != 'W' or\
a == 'D' and b != 'D':
print("incorrect")
exit(0)
print("correct")
C - 新建文件夹（1）
令 为字符串的最大长度。
如果我们每次都按照题目描述中的的那样去暴力查找统计与 相同的字符串的数量，则总共需要花费 时间，从而导致 （超时）。
我们可以使用 std::map 来存储“到目前为止 出现的次数”（ 可以使用 defaultdict(int)），这样对于每个字符串 可以在 的时间内确定要输出的字符串。
通过这种方法，可以在总共 的时间内解决问题。
语法小课堂
-
std::map<K, V>可以创建一个具有 映射关系的容器，对于本题中，我们希望给出一个字符串，就能够获取其出现的次数，实际上是要建立一个关于 的映射关系。那么访问时就可以像数组那样使用[]访问。 -
对于 推荐使用
defaultdict而非内置的dict。
defaultdict会在尝试访问字典中不存在的键时，给定一个默认值，例如使用defaultdict(int)创建字典时，若访问到当前字典中不存在的键时，就会返回0，而非直接报错，其行为更接近C++的std::map。
from collections import defaultdict
cnt = defaultdict(int)
for i in range(int(input())):
s = input()
print(f'{s}({cnt[s]})' if s in cnt else s)
cnt[s] += 1
D - 投硬币
问题的关键点是对于投完第 枚硬币时，计数器为 时可以得到的最大金额。
这个状态只和投完第 枚硬币时的状态有关。
于是对于投完第 枚硬币，我们可以定义 为投完第 枚硬币后，计数器为 可以获得的最大金额。
那么有 ，其中 为计数器为 时，获得的额外奖金。
对于无法存在的状态，比如投完第 枚硬币后，无法令计数器为 ，那么便令 。
另外在代码实现上我们只需要保存投 枚硬币后的状态即可，所以只需要保留一维状态。
每次投完硬币后的状态数为 ；进行状态转移的复杂度为 ；总的时间复杂度为 。
n, m = map(int, input().split())
a = list(map(int, input().split()))
w = [0] * (n + 1)
for i in range(m):
c, y = map(int, input().split())
w[c] = y
dp = [-10 ** 15] * (n + 1)
dp[0] = 0
for x in a:
pre_max = max(dp)
for i in range(n, 0, -1):
dp[i] = max(dp[i], dp[i - 1] + x + w[i])
dp[0] = pre_max
print(max(dp))
E - 宏量运算
对于位运算而言，每一「位」的计算结果都是 相互独立 的，而每次运算后的结果只有 和 两种可能的结果，所以我们可以单独考虑运算对每一位的影响。
-
令 为：前 个运算对 中二进制位上的 产生影响后的结果。
-
令 为：前 个运算对 中二进制位上的 产生影响后的结果。
那么对于当前 施加前 个运算的影响的结果，应为：
- 将当前的 二进制位上的 转化为 对应二进制位上的状态，位运算操作为 ；
- 将当前 二进制位上的 转化为 对应二进制位上的状态，位运算的操作为 ，其中 （即有效二进制位上全为 ）；
如何维护 和 ？
很简单，只需要在每次操作时，将对 执行的位运算作用到 和 上即可。
每次位运算的时间复杂度为 ，总的时间复杂度为 。
N = 30
M = (1 << N) - 1
n, c = map(int, input().split())
one, zero, x = M, 0, c
for i in range(n):
t, a = map(int, input().split())
if t == 1:
one, zero = one & a, zero & a
elif t == 2:
one, zero = one | a, zero | a
else:
one, zero = one ^ a, zero ^ a
x = (x & one) | ((M ^ x) & zero)
print(x)
F - 彩球排序
若考虑所有球的颜色都互不相同，那么本题就变为了一道经典的「逆序对」问题。
那么我们可以考虑先求出整个序列 的「逆序对」的数量，在考虑如何消除相同元素的球进行交换对答案产生的影响即可。
对于颜色同为 的 个球对应的整数序列为 。
令其排序以后的序列为 。
那么求出上述序列的「逆序对」数量，并将其在最终的答案中减去即可。
在实现上，我们只需要创建一个「树状数组」，然后将球上的数字按照颜色分组。
对于每组内的数字，球的颜色都是相同的，所以我们对于这个序列求逆序对，在总答案中减去即可；
在结束后，可以再遍历一遍组内的数字，消除求逆序对的过程中对树状数组产生的影响。
然后我们再对整个数组求逆序对，便可得到最终的答案。
以上两个步骤的时间复杂度皆为 。
对于 而言一个可以优化的点是，倒序处理，这样每次查找就变成了“小于当前 x 的数量”，这样树状数组可以少做一半的
ask()运算。
from collections import defaultdict
class FenwickTree:
def __init__(self, n:int = 0)->None:
self.n = n
self.sum = [0] * (n + 1)
def add(self, p:int, x)->None:
while p <= self.n:
self.sum[p] += x
p += p & -p
def ask(self, p:int):
res = 0
while p > 0:
res += self.sum[p]
p -= p & -p
return res
n = int(input())
c = list(map(int, input().split()))
x = list(map(int, input().split()))
color = defaultdict(list)
for ci, xi in zip(c, x):
color[ci].append(xi)
res = 0
ft = FenwickTree(n + 1)
for seq in color.values():
for xi in seq[::-1]:
res -= ft.ask(xi - 1)
ft.add(xi, +1)
for xi in seq[::-1]:
ft.add(xi, -1)
for xi in x[::-1]:
res += ft.ask(xi - 1)
ft.add(xi, +1)
print(res)
有帮助，赞一个