2024 年 4 月 29 日 10:00 - 11:40，阿里国际数字商业集团春季2025届校园招聘在线笔试。
总限时 100 分钟，共 100 分。
前面是 9 道单选题、6 道不定项选择题。
最后是三道算法题，分值分别为为 15/15/25 分。
编程题使用 ACM 模式，即需要自己处理输入输出。语言不限，不能用本地IDE（阿里系基本都是）。
Note: 试题回忆 / OCR 可能有错漏，且我的思路及解法较为笨拙，不敢保证正确性。
抛砖引玉，敬请指正。
算法题
Q1 小红的 01 串权值和 15 pts
小红定义一个01串的权值：相邻两个字符都是’1’的对儿数。例如，”110111”的权值为3。
现在小红希望你求出所有长度为n的01串的权值之和。你能帮帮她吗？
输入描述
一个正整数n
1 <= n <= 10 ^ 9
输出描述
输出所有长度为n的01串的权值之和。由于答案很大，输出答案对10^9＋7取模的结果。
示例 1
输入
1
3
输出
1
4
说明
1
2
3
4
5
110的权值是1。
011的权值是1。
111的权值是2。
除了这三个01串，其余01串的权值均为0。
所以答案是4。
My Solution
看这个数据范围疑似是找规律，但我没找到规律，只通过了10%。
1
# TODO
Correct Solution
DP?
1
# TODO
Q2 小红的红黑树 15 pts
小红有一棵有n个节点的树，其中每个节点是红色或者黑色，她想知道有多少条简单路径恰好经过一个红点和一个黑点。
输入描述
第一行输入一个整数 n（1 ≤ n ≤ 10^5）表示节点数量。
第二行输入一个长度为 n 的字符串 s 表示节点的颜色，第 i 个节点的颜色为 S_i，若 S_i 为 ‘B’ 表示节点的颜色为黑色，若 S_i 为 ‘R’ 则表示节点的颜色为红色。
接下来 n-1行，每行输入两个整数 u, v 表示树上的边 （1 <= u, v <= n）
输出描述
输出一个整数表示答案。
示例 1
输入
1
2
3
4
3
BRB
1 2
2 3
输出
1
2
说明
1
有 1-2、2-3 两条路径
My Solution
比较简单，逐个判断所有边是不是一端黑一端红即可。通过100%。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
color = input().strip()
b = set()
r = set()
for i, c in enumerate(color):
if c == "B":
b.add(i + 1)
else:
r.add(i + 1)
ans = 0
for _ in range(n - 1):
u, v = map(int, input().split())
if (u in b and v in r) or (u in r and v in b):
ans += 1
print(ans)
Correct Solution
1
# TODO
Q3 小红的 4 倍数 25 pts
小红拿到了一个数字串，她想取一个长度为k的子序列，满足这个子序列对应的正整数是4的倍数。小红想知道有多少种不同的选择方案？
请注意，选择的子序列包含前导零也是合法的。
输入描述
第一行输入两个正整数n、k，代表数字串的长度和取的子序列长度。
第二行输入一个长度为n的、仅由数字字符组成的字符串。
1 ≤ k ≤ n ≤ 200000
输出描述
一个整数，代表合法的子序列数量。由于答案很大，输出答案对10^9＋7取模的结果。
示例 1
输入
1
2
3 2
120
输出
1
2
说明
1
长度为2的三个子序列中，12和20是合法的，10是不合法的。
示例 2
输入
1
2
3 2
010
输出
1
1
说明
1
只有 00 是合法的。
My Solution
没做。
1
# TODO
Correct Solution
1
# TODO