03-23 11:45 北京邮电大学算法工程师发布于北京

关注

【笔试分享】3月22日淘天暑期实习算法岗解析

关注我：二仙桥耐笔王， 强力1v1辅导暑期实习&春招笔试

第1题-游游的字符串

题目内容

游游正在进行字符串对照试验，他有一个长度为 $n$ 的字符串 $s$ 和另一个长度同样为 $n$ 的字符串 $t$ ，他先定义一个字符:可控一级，当其为小写字母;可控二级，当其为大写字母;可控三级，当其为数字;不可控，当其为其他字符。随后，他将依次对每一个 $i=1,2,...,n$ 进行以下操作:

如果 $s$ 和 $t$ 的第 $i$ 个字符同时为可控的，且等级相同，则输出这两个字符的中位 $Ascii$ 码对应的字符;
如果 $s$ 和 $t$ 的第 $i$ 个字符同时为可控的，但等级不同，则输出这两个字符的中位 $Ascii$ 码;
否则，直接输出一条下划线"_"。

在这里，记字符 $u,v$ 的 $Ascii$ 码为 $P_u,P_u$ ，则它们的中位 $Ascii$ 码定义为 $P_u$ 和 $P_u$ ,的平均值向上取整。例如， $a$ 和 $z$ 的中位 $Ascii$ 码为 $m$ ; $A$ 和 $B$ 的中位 $Ascii$ 码为 $B$ 。

输入描述

第一行输入一个整数 $n(1≦n≦3×10^5)$ 代表字符串的长度。

第二行输入一个长度为 $n$ 的字符串 $s$ 。

第三行输入一个长度为n 的字符串 $t$ 。

除此之外，保证字符串由数字、大小写字母、空格及 $!?.+-*/$ 这七个常见半角符号混合构成。保证字符串的首尾不为空格。

输出描述

在一行上输出一个字符串，代表操作过后的字符串。。

样例1

输入

9
ciaLlo!?
dAmE*+-/

输出

8485g|____

说明

对于第一个字符，两者同时为可控的，但等级分别为二级和一级，所以，直接输出中位 $Ascii$ 码，查表可得， $67$ 和 $100$ 的平均值向上取整为 $84$

对于第二个字符，两者同时为可控的，但等级分别为一级和二级，所以，直接输出中位Ascii码，查表可得， $105$ 和 $65$ 的平均值向上取整为 $85$ 。

对于第三个字符，两者同时为一级可控，所以，输出中位 $Ascii$ 码对应的字符，查表可得， $97$ 和 $109$ 的平均值向上取整为 $103$ ，对应 $g$ 。

题解思路

这道题目要求对两个字符串 s 和 t 进行比较，根据每个字符的类型和等级输出对应的结果。具体操作如下：

步骤分析

字符分类与等级判断
每个字符有不同的等级，可以分为四类：
- 可控一级：小写字母 a-z，其 ASCII 值在 97-122 之间。
- 可控二级：大写字母 A-Z，其 ASCII 值在 65-90 之间。
- 可控三级：数字 0-9，其 ASCII 值在 48-57 之间。
- 不可控字符：其他符号或字符，如空格、标点符号等。
对每个字符，我们需要判断其属于哪种类型，如果两个字符同时为可控字符，接下来的操作才有意义。
等级比较与输出
- 如果 s[i] 和 t[i] 都是可控字符，且它们的等级相同，则输出它们 ASCII 值的中位字符（向上取整的平均值）。
- 如果 s[i] 和 t[i] 都是可控字符，但它们的等级不同，则输出它们 ASCII 值的中位数（向上取整的平均值）。
- 如果 s[i] 或 t[i] 不是可控字符，则直接输出下划线 _。
计算中位 ASCII 值
中位 ASCII 值定义为两个字符 ASCII 值的平均值向上取整，可以通过 (a + b + 1) // 2 来实现，其中 a 和 b 是字符的 ASCII 值。

代码实现

def check(c):
    # 判断字符类型
    if c.islower():
        return 1
    elif c.isupper():
        return 2
    elif c.isdigit():
        return 3
    return 0

def solve(n, s, t):
    result = []
    for i in range(n):
        if check(s[i]) > 0 and check(t[i]) > 0:
            # 获取字符的ASCII值
            a = ord(s[i])
            b = ord(t[i])
            # 确保a <= b
            if a > b:
                a, b = b, a
            # 如果等级相同，输出字符，否则输出ASCII码
            if check(s[i]) == check(t[i]):
                mid_char = chr((a + b + 1) // 2)
                result.append(mid_char)
            else:
                mid_ascii = (a + b + 1) // 2
                result.append(str(mid_ascii))
        else:
            result.append('_')
    return ''.join(result)

# 输入
n = int(input())
s = input()
t = input()

# 输出结果
print(solve(n, s, t))

第2题-二进制数组

题目内容

对于给定的正偶数 $n$ 和正整数 $m$ ，求解下式:

$n\ xor$$\frac{n}{2}$$mod\ m$

这显然难不倒你，所以，我们将会使用一种特殊的方式给出 $n$ 的二进制形式：给出一个由 $k$ 个整数构成的数组{ $a_1,a_2,...,a_k$ }，其中，第 $i$ 个整数 $a_i$ 代表 $n$ 的二进制表示中，从高位到低位，恰好有连续 $i$ 个 $i\ mod \ 2$ 。更具体地，如果数组 $a$ ={ $3,4, 1, 2$ }，那么，第一个整数 $a_1$ 就代表有 $3$ 个 $3\ mod\ 2=1$ ,第二个整数 $a_2$ 就代表有 $4$ 个 $4\ mod \ 2=0$ ， $......$ 。最终，可以得到 $n$ 的二进制表示为 $1110000100$ 。

输入描述

第一行输入两个整数 $k,m(1≦k≦2×10^5;1≦m≦10^9)$ 。

第二行输入 $k$ 个正整数 $a_1,a_2,...,a_k(1≦a_i≦10^9)$ 。

除此之外，保证单个测试文件的 $a_i$ 之和不超过 $10^9$ 。

输出描述

输出一个十进制整数，代表式子的最终答案.

样例1

输入

4 15
3 4 1 2

输出

算法思路

核心观察

异或特性：n XOR (n >> 1) 的二进制中，只有相邻位不同的位置会产生1
段边界规则：相邻段的奇偶性不同时，交界处会生成1
快速幂优化：直接计算大数不可行，需用快速幂逐位处理

关键步骤

前缀和预处理：快速定位每个段的边界位置
最高位处理：二进制最高位总是由第一个段决定，直接计算贡献
段边界筛选：只处理奇偶性变化的段边界
模运算优化：使用快速幂算法处理大指数取模

代码实现

k, m = map(int, input().split())  # 输入k和m
a = list(map(int, input().split()))  # 输入数组a

b = []  # 用来存储二进制序列
x = 0  # 用来暂时存储1的累加和
for i in range(k):
    if a[i] % 2 == 0:  # 偶数表示0
        b.append(x)
        x = 0
        b.append(a[i])  # 偶数部分直接加入
    else:  # 奇数表示1
        x += a[i]  # 累加1的个数
if x != 0:
    b.append(x)  # 最后如果有剩余的1，需要加入b

L = sum(b)  # 计算所有1和0的总个数
pre_sum = 0  # 前缀和
result = 0  # 最终结果

# 遍历b数组进行计算
for i in range(1, len(b) + 1):
    exponent = L - 1 - pre_sum  # 指数部分
    contribution = pow(2, exponent, m)  # 计算贡献值，模m
    result = (result + contribution) % m  # 累加结果
    pre_sum += b[i - 1]  # 更新前缀和

print(result % m)  # 输出最终结果

第3题-最小权值之和

题目内容

小红拿到一棵树，结点总数为 $n$ ，根节点为 $1$

定义每个点的权值为到结点 $1$ 的边数。

现在小红可以选择一个非1号结点，使得以该结点为根节点的子树成为 $1$ 号结点的子结点。

求整棵树的最小权值之和是多少?

输入描述

第一行一个整数 $n(1≤n≤2×10^5)$ ,表示树的结点总数。

接下来 $n-1$ 行，每行两个整数 $u,v(1 ≤u,v≤n)$ ,表示 $u$ 和 $v$ 之间有一条边。

输出描述

一个整数，表示整棵树的最小权值之和。

样例1

输入

输出

题解

思路

本题的思路是：先利用深度优先搜索求出每个结点到根结点的距离（即深度）和每个结点的子树大小，然后计算初始的权值和 $S=\sum d$ ；对于每个非根结点 $v$ ，将以 $v$ 为根的子树挂接到 $1$ 号结点后，该子树所有结点的深度都会降低 $d[v]-1$ ，所以改善量为 $subtree\_size[v] \times (d[v]-1)$ ，最后取所有非根结点中最大的改善量，从 $S$ 中减去即可得到最小的权值和。

原始权值和的计算：
初始时，每个结点的权值等于其到根结点 $1$ 的距离。可以通过深度优先搜索（ $DFS$ ）计算出所有结点的深度，累加即可得到原始权值和
$S=\sum_{u=1}^{n}{d[u]}.$
操作对权值和的影响分析：
设选择了结点 $v$ （ $v\neq 1$ ），原来 $v$ 的深度为 $d[v]$ ，且以 $v$ 为根的子树中的结点数为 $subtree\_size[v]$ 。
- 操作后， $v$ 直接挂接到 $1$ 下，新深度变为 $1$ ；而 $v$ 子树内任意结点 $u$ 的深度变为 $1 + (d[u] - d[v]).$
- 因此，这部分结点权值减少了
  $(d[u] - (1 + d[u]-d[v])) = d[v]-1.$
- 整个子树的权值和减少量为
  $\text{improvement}$ = $subtree\_size[v] \times (d[v]-1).$
目标转换：
为了使整体权值和最小，我们需要最大化提升量 $\text{improvement}$ 。因此，最终答案为
$ans$ = $S$ - $max_{v\neq 1}$ { $subtree\_size[v]$ * $(d[v]-1)$ }.

代码实现

def main():
    import sys
    sys.setrecursionlimit(300000)  # 增加递归深度限制
    n = int(sys.stdin.readline())
    tree = [[] for _ in range(n+1)]  # 构造邻接表
    for _ in range(n-1):
        u, v = map(int, sys.stdin.readline().split())
        tree[u].append(v)
        tree[v].append(u)
    
    depth = [0]*(n+1)         # 存储每个结点的深度
    subtree_size = [0]*(n+1)  # 存储每个结点的子树大小
    total_depth = 0         # 累加所有结点深度，表示 S
    best = 0                # 记录最大提升量

    # 深度优先搜索函数
    def dfs(u, parent, d):
        nonlocal total_depth, best
        depth[u] = d  # 记录结点 $u$ 的深度
        total_depth += d  # 累加到总权值和
        subtree_size[u] = 1  # 初始化子树大小
        for v in tree[u]:
            if v == parent:
                continue  # 避免回到父结点
            dfs(v, u, d+1)  # 对子结点递归
            subtree_size[u] += subtree_size[v]  # 累加子树大小
        if u != 1:  # 只考虑非根结点
            improvement = subtree_size[u] * (d - 1)  # 计算提升量
            best = max(best, improvement)  # 更新最大提升量

    dfs(1, 0, 0)  # 从结点 1 开始深搜，初始深度为 0
    print(total_depth - best)  # 输出结果

if __name__ == '__main__':
    main()

#笔试#