阿里云 9.19笔试

第一题 20%   算概率，分子分母约分成p/q， 最终结果是 (p * (q^(m-2) % m) % m)
    算概率的逻辑很简单，结果需要求一个很大的幂函数，用了快速幂，改了来改去也只有20%

第二题 100% 按字符串翻转（123 变成 321）数组某个区间内所有数字，使得数组总和最大 ，求最大总和   
    计算出每个元素翻转后的差值，对这个差值数组求最大区间和，加上原始数组的和即为答案。

第三题 90%  无向连通图，初始状态只有顶点有权值。需要根据边两端的顶点是否是质数，求出边的权值。（两端顶点都是质数，两顶点权值求或；都不是质数，顶点权值求与；有一个质数，求异或）。计算完权值后，在保持图连通的情况下删除一些边，使得删除掉的边权值最大。其实就等价于求最小生成树，然后统计不在最小生成树里的边的权值和。
   
    解法 1. 素数筛法判断质数，计算边权值
            2. 生成最小生成树
    用prim过了90%（有10%显示超时），猜测用kruskal能ac，没时间写了