09-19 21:59 已编辑 门头沟学院 Java 发布于上海
关注
阿里云 9.19笔试
第一题 20% 算概率，分子分母约分成p/q， 最终结果是 (p * (q^(m-2) % m) % m)
算概率的逻辑很简单，结果需要求一个很大的幂函数，用了快速幂，改了来改去也只有20%
第二题 100% 按字符串翻转（123 变成 321）数组某个区间内所有数字，使得数组总和最大 ，求最大总和
计算出每个元素翻转后的差值，对这个差值数组求最大区间和，加上原始数组的和即为答案。
第三题 90% 无向连通图，初始状态只有顶点有权值。需要根据边两端的顶点是否是质数，求出边的权值。（两端顶点都是质数，两顶点权值求或；都不是质数，顶点权值求与；有一个质数，求异或）。计算完权值后，在保持图连通的情况下删除一些边，使得删除掉的边权值最大。其实就等价于求最小生成树，然后统计不在最小生成树里的边的权值和。
解法 1. 素数筛法判断质数，计算边权值
2. 生成最小生成树
用prim过了90%（有10%显示超时），猜测用kruskal能ac，没时间写了
算概率的逻辑很简单，结果需要求一个很大的幂函数，用了快速幂，改了来改去也只有20%
第二题 100% 按字符串翻转（123 变成 321）数组某个区间内所有数字，使得数组总和最大 ，求最大总和
计算出每个元素翻转后的差值，对这个差值数组求最大区间和，加上原始数组的和即为答案。
第三题 90% 无向连通图，初始状态只有顶点有权值。需要根据边两端的顶点是否是质数，求出边的权值。（两端顶点都是质数，两顶点权值求或；都不是质数，顶点权值求与；有一个质数，求异或）。计算完权值后，在保持图连通的情况下删除一些边，使得删除掉的边权值最大。其实就等价于求最小生成树，然后统计不在最小生成树里的边的权值和。
解法 1. 素数筛法判断质数，计算边权值
2. 生成最小生成树
用prim过了90%（有10%显示超时），猜测用kruskal能ac，没时间写了
全部评论
讲原则的柯基整顿职场
第一题C++本来20改成longlong就50了，但是还是报的答案错误
相关推荐
11-15 11:03
点赞 评论 收藏
分享
点赞 评论 收藏
分享
10-31 08:44
中国科学院计算技术研究所 算法工程师 
投递阿里云等公司10个岗位 点赞 评论 收藏
分享
游卡
| 校招
| 超多精选岗位
点赞 评论 收藏
分享