2023届携程秋招 0830笔试
T1
题意:给若干个数,每一个数希望在重排其数字后变成偶数(如果原本是偶数就不用动),输出变更后的偶数,无法完成则输出-1
数据范围:数字<1e9
个人思路:偶数直接输出,奇数找一个偶数位换到末位去,找不到就输出-1
结果:通过100%
T2
题意:多组输入,每组输入三个数字,分别代表'y','o','u'三个字母的个数,用这些字母组成一个字符串,每一个子串'you'对答案贡献为2,'oo'贡献为1,问最大贡献值为多少
数据范围:字母个数<1e9
个人思路:贪心,先尽量多拼'you',再把剩下的'o'排一起
结果:通过100%
T3
题意:给定一棵树,每个节点会被染上一种颜色,共三种可能的颜色,现在要割掉一条边,使两个子连通图每种颜色的节点都至少有一个,问有多少种割法
数据范围:n<1e5
个人思路:dfs序预处理(用一个计数器记录dfs的顺序,每个节点是第几个遍历到的(a),遍历完成子节点后计数器的值(b),那么这个节点形成的子树的序号就是a~b),再按照dfs序处理前缀和; 再次dfs遍历,对于每一条边,以子节点形成的子树一块连通图,看子树中每个颜色的节点有多少个(通过dfs序的前缀和O(1)的求),再通过每个颜色总共有多少个节点,推测出另一边连通图每个颜色的节点有多少个,判断是否符合条件
T4
题意:给定一个序列,定义其平滑值为任意两相邻数的差值的最大值的绝对值,现在可以改变一个数,问修改后平滑值最小为多少
数据范围:序列长度<1e5,abs(数字)<1e9
个人思路:贪心,先找出造成平滑值最大的两个相邻数,如果这对数在最左边或者最右边,就使最左边或者最右边的数变为他相邻数的值,重新求一遍平滑值;否则的话,对于这两个数,分别变为其左边相邻和右边相邻的数的平均值,各重新求一遍平滑值,再取两者更小的值作为答案