10-14 21:23 已编辑 门头沟学院 Java 发布于北京
关注
阿里国际笔试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，要从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），累加和就是答案
第三题没看，瞄了一眼完全不会
全部评论
忙活三个月收获0offer
蚌埠坦克学院 后端
第一题就是大于n/2的质数个数+2（1和任一小于等于n/2的质数），因为对于两个小于等于n/2的质数x，y，存在x->2x->2y->y使这两个数冲突
给了offer吧
西安交通大学 C++
第一题在纸上画了半天，发现从 n/2 到 n 之间的所有质数都是不会冲突的，然后比n/2小的第一个质数也不会和之后的所有质数冲突，另外再加上不会和任何数冲突的1
菠萝咕咾双
东北大学 C++
第一题思路是啥捏
一只脆啵啵
门头沟学院 C++
大佬能分享下第一题啥思路吗
牛客43689394号
门头沟学院 C++
第一题想5怎么不行，想明白了不会了
秋招之苟
门头沟学院 Java
佬这是移动端咩
给了offer吧
西安交通大学 C++
第二题死活不会，在那儿找规律，以为可以怎么递归，最后还是没试出来
Acane
浙江大学 C++
ak了 第三题就线性筛预处理下因子个数然后dfs算f(u)表示u到根节点的路径和 然后转化为算sum(f(u)^f(v))，按二进位枚举计算贡献就行了
相关推荐
投递阿里国际数字商业集团等公司10个岗位 点赞 评论 收藏
分享
10-25 17:34
西安电子科技大学 Java 点赞 评论 收藏
分享
Richard奇：不是，佬这么猛的吗
阿里巴巴开奖82人在聊 点赞 评论 收藏
分享