阿里国际笔试10.14

迟到了十几分钟,乍一看一题都不会,每题都像数学题….
硬想了几十分钟竟然写出来俩
第一题筛素数变体,大概意思是,给定n,要从1-n选出不冲突的数,最多能选几个,冲突的定义:a和b,要是a和b的最大公约数为质数,或者存在a1,a2..ai位于1-n之间,使得a和a1,a1和a2,…. ai和b最大公约数都为质数,则a、b冲突

直觉做法:从2开始筛素数,筛到n,要是在筛的过程中从来没有遇到别人筛过的数,就ret++,最后ret+1就是答案,得加上1(其实为啥正确,我也不会证明直觉是这样然后过了,歪打正着,有会证明的uu可以解答下

第二题,给n,选出1-n中的好数对(忘了叫啥),好数对定义:一对整数a和b,a最高位=b最低位且a最低位=b最高位,a、b可重复(比如1和1,1和11都算)
思路:开个数组,f(i,j)记录以i开始以j结尾的数字,遍历1-n记录一下,再遍历f累加f(i,j)*f(j,i),累加和就是答案

第三题没看,瞄了一眼完全不会
全部评论
第一题就是大于n/2的质数个数+2(1和任一小于等于n/2的质数),因为对于两个小于等于n/2的质数x,y,存在x->2x->2y->y使这两个数冲突
3 回复 分享
发布于 10-14 21:59 浙江
第一题在纸上画了半天,发现从 n/2 到 n 之间的所有质数都是不会冲突的,然后比n/2小的第一个质数也不会和之后的所有质数冲突,另外再加上不会和任何数冲突的1
2 回复 分享
发布于 10-14 21:43 陕西
第一题思路是啥捏
1 回复 分享
发布于 10-14 21:18 辽宁
大佬能分享下第一题啥思路吗
点赞 回复 分享
发布于 10-14 20:55 安徽
第一题想5怎么不行,想明白了不会了
点赞 回复 分享
发布于 10-14 21:01 江苏
佬这是移动端咩
点赞 回复 分享
发布于 10-14 21:26 陕西
第二题死活不会,在那儿找规律,以为可以怎么递归,最后还是没试出来
点赞 回复 分享
发布于 10-14 21:37 陕西
ak了 第三题就线性筛预处理下因子个数然后dfs算f(u)表示u到根节点的路径和 然后转化为算sum(f(u)^f(v)),按二进位枚举计算贡献就行了
点赞 回复 分享
发布于 10-14 23:48 浙江

相关推荐

不愿透露姓名的神秘牛友
11-21 10:19
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-16 12:38
点赞 评论 收藏
分享
offer决赛圈求助研究方向做的半主动悬架,智能驾驶方面。家在黄山,一开始择岗地点只选择在合肥和杭州。恋爱三年,感情稳定,男友也是更倾向于去杭州发展,杭州定居能比较顺利。📍offer公司1:杭州初创私企💰薪资包:17*15+年终💡优缺点:优点是提供免费住宿一年,工作时间在八点半到五点半,双休,基本不加班。岗位对口90%。老板是同学校的校友意愿很强烈,同岗位今年新招了五个人,有工程师一对一应届生培养。缺点是公司规模50到100人,初创。该公司有大厂企业背书,岗位办公地点设在大厂的园区内,环境挺好的。📍offer公司2:杭州外企💰薪资包:12.5*13+0-4个月年终💡优缺点:优点是:公司成立十几年很稳定 福利待遇拉满,没有房补,有餐补或者其他补贴加起来400元一个月。六险二金,工作时间八点到四点半,双休基本不加班,女性友好。缺点是岗位做PLC,对口40%,工资较少。📍offer公司3:上海私企💰薪资包:30*14💡优缺点:优点是,薪资高工作十点到七点半,基本上不加班,但是不排除业务熟练之后参与项目需要加班。岗位是智能驾驶类对口80%缺点是,公司18年成立,不是很久,规模500-999人。女生在上海打拼很累。上海不可能定居,未知私企啥时候裁员,不稳定,到时候想回合肥或者杭州不一定能回来。回顾秋招的各个企业待遇,这个企业不加班,薪资高,企查查上看到参保人数才80多个人,还是有些顾虑 #offer帮选# #offer选择投票# #求助ofeer选择# #offer帮选#
点赞 评论 收藏
分享
评论
点赞
2
分享
牛客网
牛客企业服务