20210417 leetcode 第 50 场双周赛

[21.04.17]双周赛（补题进度【3/4】）

最少操作使数组递增

一个小坑：暴力++++会超时
直接计算即可

---

统计一个圆中点的数目

直接a^2+b^2 <= r^2计算

---

每个查询的最大异或值

利用位运算的性质：s^a^a=s
从后往前每一步结果转移，都是上一步的k ^= a[i]
注意的细节：不超过第maximumBit的约束，如果maxBit < max(nums)直接算，否则多余的位是111…11

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int init = 0;
        for(int i = 0; i < nums.size(); i++){
            init ^= nums[i];
        }
        int max_ans = 1;
        int i = 1;
        while(nums[nums.size()-1]>>(i-1))i++;
        max_ans <<= i;
        max_ans -= 1;
        int vvb = (1<<(maximumBit))-1;
        vector<int>ret;
        ret.clear();
        //printf("%d-%d     ", init, max_ans);
        int now = init ^ max_ans;
        for(int i = nums.size()-1; i >= 0; i--){
            //printf("%d-%d     ", now, vvb);
            //now &= vvb;
            ret.push_back(vvb & ((now & vvb) | (max_ans ^ vvb)));
            now ^= nums[i];
        }
        return ret;
        
    }
};

---

使字符串有序的最少操作次数

看了半天这什么玩意，相信一定是有规律的。试图打表未果，最后看了看样例发现，这不是全排列吗。
总之这题是给你一串字符串，计算他是当前这些字符组成的全排列的字典序第几个。
无重复数字的全排列可以用康托展开，这个有重复数字的全排列，除了排列组合之外没想到什么好的解决方案。。

更新：看了看题解，确实就是用组合数计算的，思路没问题，待补题。