阿里国际笔试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 辽宁
tql
点赞 回复 分享
发布于 10-14 20:43 山东
大佬能分享下第一题啥思路吗
点赞 回复 分享
发布于 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 浙江

相关推荐

点赞 2 评论
分享
牛客网
牛客企业服务