携程9.18笔试

第一题 水仙花数 直接a了
第二题 忘了也比较简单
第三题 位运算+贪心，最多异或和一次（不会证明），遍历数组，如果在该为上为1，则是n（总数） - cnt（该为上1的个数），如果是0则是cnt，乘以power（2，x）也就是该位的2次幂（基于异或的特性），总时间复杂度为O(nlogn)。
第四题 二维dp，反转的区间对左右两侧没影响，只要考虑[l,r]区间的逆序对数量，我本来想用O(n^3)水一下分的，没想到直接过了。正的算一遍dp[l][r]区间中的逆序对，反着在算一变，直接遍历区间总的减去正的区间加上反的区间，求最小值就过了。可以优化时间复杂度，我当时懒得写了，就直接暴力n^3水过去了。
用了一个小时a了，感觉还行