题解 | 题解A-D

小s的签到题

https://ac.nowcoder.com/acm/contest/109081/A

【A】小s的签到题：

题目概述

快速找到“签到题”，即通过人数最多的题目。如果有多个题目通过人数相同，则选择题号字典序最小的。

解题思路

输入处理：读取题目数量、题号列表和每个题目的通过/提交数据。
提取通过数：对每个题目的统计字符串，提取通过数部分。
维护最大值：遍历所有题目，维护当前最大通过数及其对应题号。若遇到相同通过数，则比较题号字典序，保留较小的。

代码解析

n = int(input())
a = list(input().split())
b = list(input().split())
ans = ''
cnt = -1
for i in range(n):
    num, _ = map(int, b[i].split('/'))  # 提取通过数
    if num > cnt:
        ans = a[i]
        cnt = num
    elif num == cnt and a[i] < ans:  # 相同则选字典序小的
        ans = a[i]
print(ans)

读取输入：n 为题目数量，a 存储题号列表，b 存储每个题目的统计。
初始化变量：ans 保存最终结果，cnt 记录当前最大通过数（初始为-1，确保首次比较成功）。
遍历处理：
- 分割每个统计字符串，提取通过数 num。
- 若 num 大于当前最大值，更新答案和最大值。
- 若 num 等于当前最大值，但当前题号字典序更小，更新答案。
输出结果：最终 ans 即为答案。

复杂度分析

时间复杂度：O(n)。遍历所有题目，每个题目处理时间为常数。
空间复杂度：O(n)。存储题号和统计数据。

【B】小柒的行列改写：

题目概述

给定两个数组 R 和 C，需要构造一个 n x m 的矩阵。构造规则如下：

每个 R[i] 必须被使用一次，用于覆盖某一整行的所有元素。
每个 C[j] 必须被使用一次，用于覆盖某一整列的所有元素。
如果某个位置同时被行和列覆盖，最终值由最后一次操作决定。求所有元素的最大可能和。

解题思路

观察

覆盖顺序决定最终值：行和列的操作先后顺序会影响最终值，较大的值应尽可能【后覆盖】。
贪心策略：按元素值从小到大处理，优先处理值较小的行或列元素。每次处理一个元素时，计算它能产生的贡献，即作为【后覆盖】能覆盖的有效区域大小。

算法步骤

合并和排序：将 r 和 c 的所有元素合并，并按值升序排序。
遍历处理：维护两个计数器 cnt_c 和 cnt_r，分别表示已覆盖的列和行的数量。
- 处理行元素时，贡献为 R[i] * cnt_c，即【后覆盖】所有已被列覆盖的列。
- 处理列元素时，贡献为 C[j] * cnt_r，即【后覆盖】所有已被行覆盖的行。
累加贡献：将所有操作的贡献累加，得到最终结果。

代码解析

n, m = map(int, input().split())
r = [(x, 0) for x in map(int, input().split())] # 0 表示行元素
c = [(x, 1) for x in map(int, input().split())] # 1 表示列元素
sl = sorted(r + c) # 按值升序排序

cnt_r = 0
cnt_c = 0
ans = 0
for x, i in sl: 
    if i == 1:
        ans += cnt_r * x
        cnt_c += 1
    else:
        ans += cnt_c * x
        cnt_r += 1
print(ans)

复杂度分析

时间复杂度：O((n + m) log(n + m))，主要来自排序。
空间复杂度：O(n + m)，存储合并后的元素列表。

【C】树上替身追赶游戏：

题目概述

给定一棵树和一个起始节点 k，Saki 和 Miku 初始时都在 k 点。游戏每回合包含以下步骤：

Saki 移动：从当前节点移动到相邻节点。
放置替身：Saki 在新位置选择一个相邻节点放置替身。
Miku 移动：Miku 移动到离替身最近的相邻节点。

游戏结束时两人处于同一位置。求 Saki 最多能存活的回合数。

解题思路

核心观察

树的最长路径决定存活回合数：Saki 的最优策略是沿着树中从 k 出发的最长路径移动，每次尽可能远离 Miku。
BFS 统计最大深度：以 k 为根节点，通过广度优先搜索（BFS）计算树的最大深度。最大深度即为 Saki 能存活的回合数。

算法步骤

构建树的邻接表：将输入的边转换为邻接表。
BFS 遍历：从 k 出发，逐层扩展，统计树的层数（最大深度）。
输出结果：层数即为最大存活回合数。

代码解析

n, k = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

queue = [(k, 0)]  # 初始队列：起点为k，父节点标记为0
cnt = 0
while queue:
    next_queue = []
    for u, fa in queue:
        for v in g[u]:
            if v != fa:  # 避免重复访问父节点
                next_queue.append((v, u))
    cnt += 1  # 每处理完一层，计数器加1
    queue = next_queue

print(cnt)

复杂度分析

时间复杂度：O(n)。BFS 遍历所有节点，每个节点仅访问一次。
空间复杂度：O(n)。邻接表和队列的空间均与节点数线性相关。

【D】全对！：

题目大意

我们需要找到最小的时刻 t，使得所有机器人在该时刻同时回答【对的】。每个机器人的回答由其无限循环的二进制字符串的第 t 位决定，该位为1时回答【对的】。

解题思路

问题分析:
- 每个机器人的字符串会无限循环。例如，字符串 "001" 会重复为 "001001001..."。
- 时间 t 对应的位置是原字符串的 (t-1) % l 位，其中 l 是字符串的长度。
关键观察:
- 对于每个机器人，其回答由循环周期 l 的余数决定。需要所有机器人在同一余数处字符为1。
算法步骤:
- 预处理: 对每个长度 l，反转字符串并转换为二进制数。对于长度 l 相同的字符串，由于周期相同，所以可以通过【按位与】操作收集所有该长度机器人的公共1的位置。
- 枚举时间: 遍历可能的时间 t，检查每个长度的余数是否满足所有机器人的条件。

代码解释

from sys import stdin
input = lambda: stdin.readline().rstrip()

def solve():
    n = int(input())
    res = [input() for _ in range(n)]
    # 预处理每个长度的公共掩码
    b = [(1 << i) - 1 for i in range(17)]  # 初始化为全1
    for x in res:
        l = len(x)
        num = int(x[::-1], 2)  # 反转字符串转换为二进制数
        b[l] &= num  # 保留所有机器人该位置的公共1
    # 枚举可能的时间（MX为各长度最小公倍数的上界）
    mx = 16 * 9 * 5 * 7 * 11 * 13  # 720720
    for num in range(mx):
        valid = True
        for mask in range(1, 17):
            if b[mask] == 0:
                continue  # 该长度无机器人
            r = num % mask
            if (b[mask] & (1 << r)) == 0:
                valid = False
                break
        if valid:
            return num + 1  # 返回t=num+1
    return -1

print(solve())

代码详解:

预处理:
- b 数组初始化每个长度的掩码为全1，即 (1 << l) - 1，表示初始状态周期内每个时刻都回答【全对】。对于每个机器人字符串，反转后转换为整数 num，利用状态压缩来加快成勋运行速度（不状压常数低也可以过），并更新对应长度的掩码，保留所有机器人公共的1的位置。
枚举时间:
- 遍历 num 从 0 到 MX-1（对应时间 t=num+1）。
- 对每个可能的长度的掩码 mask，检查余数 num % mask 是否在所有机器人的公共1的位置中。若全部满足，则 num+1 为答案。如果无一满足，则输出-1。通过这种方法，高效地找到所有机器人同时回答“对”的最小时间 t。