秋招日寄|拼多多笔试20240825编程题记录

第一题：题目内容

多多有一题个节点的树，树中每一条边都有一个权值，多多还有一个长度为的正整数序列:

删除树中若干条边之后(或者不删)，就会变成一个有个连通块的图，此时的得分为：剩余边权和（两个可以互相到达的节点属于同一个连通块，注意一个孤点也是一个连通块）

多多可以删除图中若干条边（可以不删）。现在多多想知道，最多能够得到多少分。现在请你告诉多多答案。

输入描述

第一行一个整数，接下来有组数据

每组数据第一行一个整数

第二行个整数

接下来行，每行个数，。

表示节点与节点之间有一条权值为w的边

保证 不超过

保证每组数据给定的都是一棵树

输出描述

对于每组数据输出一行一个整数，表示最多能够得到多少分

示例1

输入

1
3
1 3 4
1 2 1
2 3 2

输出

5

说明

删除1与2之间的边，此时剩余边权和=2，连通块数量=2，得分=2+v[2]=2+3=5

示例2

输入

2
3
3 3 4
1 2 1
2 3 2
3
1 2 5
1 2 1
2 3 2

输出

6
5

说明

第一组数据：不删除任何边

第二组数据：删除所有边

示例3

输入

1
5
2 5 2 1 4
2 1 1
2 4 4
4 3 3
1 5 4

输出

16

说明

删除2到1之间的边，形成2个连通块，此时得分为16

----------

第二题：题目内容

多多有一列正整数组成的数列，支持两种操作：

选取一个偶数，使其值减半

选取两个数字，移除并替换为两个数字的和

多多最终希望能够得到一个全为奇数的数列，请计算最少需要操作几次

输入描述

第一行一个数字，代表测试用例组数

对于每个测试用例：

第一行为，代表数组长度，

第二行个正整数，

输出描述

对于每个测试用例，输出一个数字，代表最少需要操作次数

示例1

输入

3
3
2 4 4
2
1 9
5
1 2 3 4 5

输出

3
0
2

----------

第三题：题目内容

多多携带一件价值为的礼物参加了一个节日派对。除多多外在场的有个人，第个人的当前持有的礼物价值为。

多多可以和任意当前持有礼物价值比多多低的人交换礼物。

请问最少经过多少次交换，可以使得个人持有的礼物价值形成单调不减的数列。

（）

输入描述

第一行输入两个数字和，代表人数、和多多最多持有的礼物价值。

第二行个数字,代表其他所有人最初持有的礼物价值

对于%的数据，

对于%的数据，，

输出描述

输出一个数字,代表为了达成目标最少进行的交换次数。

如果无法达成目标则输出

样例1

输入

5 5
2 1 3 2 4

输出

3

说明

最初多多的礼物价值为

第次选择和第个人交换。交换后多多的礼物价值为，其他人为{}

第次选择和第个人交换。交换后多多的礼物价值为，其他人为{}

第次选择和第个人交换。交换后多多的礼物价值为，其他人为{}

----------

第四题：题目内容

给定长度为的串，定义一次操作为，将整个字符串按顺序分为两部分，将两部分各自翻转后再按原顺序拼接。

提问，进行任意次的操作后，可以得到的最长的连续的交替的子串有多长。

例：原串为，可以先将原串分为和两部分，分别翻转得到和,按原顺序拼接后得到，此时最长的连续交替子串为，长度为

输入描述

第一行输入表示输入的串的长度。（）

第二行输入长度为的串

输出描述

输出一个数字表示可能得到的最长的交替子串的长度。

样例1

输入

5
10010

输出

5

说明

原字符串分为和，分别翻转得到和，拼接后为