2024 年 4 月 28 日 14:00 - 15:40，阿里云 2025 届工程研发笔试。
总限时 100 分钟，共 100 分。
前面是 8 道单选题、7 道不定项选择题。
最后是三道算法题，分值分别为为 15/15/25 分。
编程题使用 ACM 模式，即需要自己处理输入输出。语言不限，不能用本地IDE（阿里系基本都是）。
Note: 试题回忆 / OCR 可能有错漏，且我的思路及解法较为笨拙，不敢保证正确性。
抛砖引玉，敬请指正。
算法题
Q1 小红的数组染色 15 pts
小红拿到了一个数组，初始所有元素都是白色，她准备将一些元素染成红色，将另外一些元素染成蓝色。小红希望使得红色元素之和与蓝色元素之和相等，她想知道有多少种不同染色方案？
输入描述
第一行输入一个正整数n，代表数组的大小。
第二行输入n个正整数a_i，代表数组的元素。
1 <= n <= 50
1 <= a_i <= 10
输出描述
一个整数，代表不同的染色方案数量。由于答案可能很大，输出答案对10^9＋7取模的结果。
示例 1
输入
1
2
4
1 2 4 3
输出
1
6
说明
1
2
3
4
5
6
方案1：1和4染红，2和3染蓝。
方案2：1和4染蓝，2和3染红。
方案3：1和2染红，3染蓝。
方案4：1和2染蓝，3染红。
方案5：1和3染红，4染蓝。
方案6：1和3染蓝，4染红。
示例 2
输入
1
2
3
1 1 1
输出
1
6
说明
1
显然只有1个染红、1个染蓝这种可能，共有6种不同的染色方式。
My Solution
不会做。刚开始用回溯找和为原数组和一半的子集，但这是错误思路。
因为并不用所有白块都染色，可以只染一部分。
拆分数组后再回溯的话，复杂度就会增加很多。
1
# TODO
Correct Solution
DP?
1
# TODO
Q2 小苯的合并极差 15 pts
小苯有一个长n的数组a，他可以对数组进行任意次以下两种操作：
- 选择1 ≤ i＜n，将a_i 和a_ (i+1) 合并为一个数字，结果为 a_i & a_(i+1)。（&表示按位与运算）
- 选择1 ≤ i＜n，将a_i 和a_ (i+1) 合并为一个数字，结果为 a_i | a_(i+1)。（ 竖线表示按位或运算）
（两种操作均可以执行任意次，前提是数组长度至少为2。当然每次操作执行完后，n 都会减少1。）
小苯希望最大化数组的极差，请你帮帮他吧。
极差定义：数组最大值与最小值之间的差距。
输入描述
输入包含两行。
第一行一个正整数n （1 ≤ n ≤ 10^5），表示数组 a 的长度。
第二行 n 个整数 a_i（0 ≤ a_i ≤ 10^9），表示数组 a 的值。
输出描述
输出包含一行一个整数，表示数组的最大极差。
示例 1
输入
1
2
6
1 2 3 1 1 6
输出
1
7
说明
1
2
3
可以合并 a1 和 a2 为 a1 & a2，再合并 a5 和 a6 变为 a5 | a6。
此时数组变为：｛0, 3, 1, 7｝，极差为 7 最大。
可以证明不存在比 7 更大的极差。
My Solution
没有思路，骗分。直接输出所有数字的按位或，即默认最小为0，最大为所有数字按位或。通过100%。
1
# 略
Correct Solution
1
# TODO
Q3 小红的 red 重排 25 pts
小红拿到了一个长度为3*n的字符串，其中’red’三种字符都恰好有n个。
现在她每次操作可以交换任意两个字符，请你求出小红使得该字符串包含n个”red”连续子串的操作操作次数，并给出任意一个方案。
输入描述
第一行输入一个正整数n。
第二行输入一个长度为3*n的，由n个’r’、n个’e’、n个’d’组成的字符串。
1≤ n ≤ 50000
输出描述
第一行输入一个正整数 q ，代表操作次数。
接下来的 q 行、毎行输入两个正整数u、v，代表交换第 u 个字符和第 v 个字符。
示例 1
输入
1
2
1
edr
输出
1
2
3
2
1 3
2 3
说明
1
2
首先交换第一个字符和第三个字符，字符串变成"rde"。
然后交换第二个字符和第三个字符，字符串变成"red"。
示例 2
输入
1
2
3
redredred
输出
1
0
My Solution
没做。
1
# TODO
Correct Solution
1
# TODO