淘天Java研发实习 - 笔试

2025年4月8号 19：00 - 20：40

题型：

基础 - 单选 7题 21分

基础 - 多选 5题 15分

Java基础 - 单选 2题 6分

Java基础 - 多选 1题 3分

编程题（工程） 1题 20分

编程题（共用） 2题 35分

编程题（工程）：

整体判断：

题目描述：

对于给定的k个数组，第i个数组由ni个整数组成。现在想知道，是否存在这样两个不同的数组，使得这两个数组各自删除一个整数后，这两个数组剩下的元素和相等。

输入：

第一行输入一个整数，代表数据组数。

每组测试数据：第一行输入一个整数k，代表有k个数组。

第i个数组：第一行输入一个整数n，代表i数组的元素个数。

第二行输入n个整数，即i数组。

输出：

存在两个数组使得两个数组各删除一个整数后，这两个数组剩下的元素和相等，则输出YES，反之输出NO。

例如：
输入：
2
2
5
2 3 1 3 2
6
1 1 2 2 2 1
2
2
8 9
9
2 10 20 6 18 6 2 1 8 7
输出：
YES
NO

编程题（共用）：

1.小苯的字符串构造

题目描述：

小苯给了你一个正整数n，他希望你构造一个仅包含小写英文字母'a'到'z'长度为n的字符串s，满足s的所有本质不同连续子串中，长度为奇数的字串恰好出现了奇数次。

本质不同连续子串：指的是从一个字符串中提取的所有连续子串中，按内容相同性去重后得到的集合。在这个集合中，如果有两个子串在字符序列上完全相同，那么他们被视为“本质相同”，只记作一个。

例如，对字符串“aa”。所有可能的连续子串为：从位置1：“a”，“aa”；从位置2：“a”，其中“a”出现两个，但本质不同连续子串只记作“a”，“aa”两个。

输入：

第一行包含一个正整数T（1≤T≤100），代表T组数据

接下来T组数据在单独一行输入一个正整数n（1≤n≤2000）

例如：
输入：
1
4
输出：
live

2.小红的子树操作

题目描述：

在神秘莫测的比特王国中，流传着这样一个传说——在王国深处生长着一棵蕴含天机的神奇大树。这棵树由n个节点构成，1号点是根节点，每个节点都记录着一段古老的符文，初始每个节点的符文为ai。传说只有将树上所有节点的符文调和为零，才能开启通往失落宝藏的大门。聪明勇敢的小红接受了挑战，她掌握了一套奇特的操作法则，能够对树中部分节点施法改变其符文，但每次施法都需要付出一定代价。

具体来说，小红可以进行如下操作：

• 选择树中的任一节点 v 及一个非负整数 x 。
• 将 v 以及 v 的子树中所有与 v 距离为偶数的节点的权值进行异或操作，即更新为：a[u] = a[u] ^ x 。
• 每进行一次此操作就产生 x 的代价。

请问小红至少需要花费多少总代价，才能使得所有节点的符文权值均变为0？

名词解释：在一棵树中，对于任一节点 v ，以 v 为根节点并包含所有从 v 出发可以达到的后代节点（包括 v 自身）的集合构成了 v 的子树。在树中，任意两个节点之间仅存在一条简单路径，该路径上所经过的边的数目定义为这两个节点之间的距离。

输入：

第一行包含一个整数 n ，表示节点的数量。

第二行输入 n 个整数 a1，a2，……，an ，表示各个节点初始权值。

接下来第 n-1 行输入两个整数 u，v ，表示树中的一条边，所给边构成一棵以1为根的树。

1≤ n ≤2×10^5

0≤ ai ≤10^9

输出：

输出一个整数，表示将所有节点权值变为0的最小总代价。

例如：
输入：
5
1 4 3 5 5
1 2
2 3
3 4
3 5
输出：
9
解析：
先选节点1，花费1代价，使得节点变为[0,4,2,5,5];
再选节点2，花费4代价，使得节点变为[0,0,2,1,1];
再选节点3，花费2代价，使得节点变为[0,0,0,1,1];
再选节点4，花费1代价，使得节点变为[0,0,0,0,1];
再选节点5，花费1代价，使得节点变为[0,0,0,0,0];
因此输出为 1 + 4 + 2 + 1 + 1 = 9