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)的求),再通过每个颜色总共有多少个节点,推测出另一边连通图每个颜色的节点有多少个,判断是否符合条件

复杂度:O(n)
结果:通过100%

T4

题意:给定一个序列,定义其平滑值为任意两相邻数的差值的最大值的绝对值,现在可以改变一个数,问修改后平滑值最小为多少

数据范围:序列长度<1e5,abs(数字)<1e9

个人思路:贪心,先找出造成平滑值最大的两个相邻数,如果这对数在最左边或者最右边,就使最左边或者最右边的数变为他相邻数的值,重新求一遍平滑值;否则的话,对于这两个数,分别变为其左边相邻和右边相邻的数的平均值,各重新求一遍平滑值,再取两者更小的值作为答案

结果:通过100%

提前一个小时做完跑路了...
#笔试##携程#
全部评论
给大佬跪了
1 回复 分享
发布于 2022-08-30 21:03 北京
t4一样的思路,为啥一直不对?
点赞 回复 分享
发布于 2022-08-30 21:08 上海
第四题一样思路只过20%
点赞 回复 分享
发布于 2022-08-30 21:09 河南
大佬,最后一道会不会出现多个最大值?
点赞 回复 分享
发布于 2022-08-30 21:10 北京
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc=new Scanner(System.in); int num=Integer.parseInt(sc.nextLine()); while(num-->0){ String input=sc.nextLine(); if(Integer.parseInt(input.substring(input.length()-1,input.length()))%2==0){ System.out.println(input); continue; } else{ if(Integer.parseInt(input.substring(0,1))%2==0){ System.out.println(input.substring(input.length()-1,input.length())+input.substring(1,input.length()-1)+input.substring(0,1)); } else{ for(int i=1;i<input.length();i++){ if(Integer.parseInt(input.substring(i,i+1))%2==0){ System.out.println(input.substring(0,i)+input.substring(i+1,input.length())+input.substring(i,i+1)); break; } if(i==input.length()-1){ System.out.println(-1); } } } } } } }
点赞 回复 分享
发布于 2022-08-30 21:31 浙江
大佬,最后一题,思路一样,造成平滑值得两个数不是可以有多对?也就是楼上说的最大值有多个
点赞 回复 分享
发布于 2022-08-30 21:32 河南
大佬 第三题能分享下吗?当时没有做出来
点赞 回复 分享
发布于 2022-08-30 21:39 湖北

相关推荐

点赞 评论 收藏
分享
11 14 评论
分享
牛客网
牛客企业服务