image-20210516113536256

GG

5759. 找出所有子集的异或总和再求和

模拟题目

二进制枚举所有集合 计算每个集合的异或和， 最后加起来就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for(int i=1;i<(1<<n);i++) {
            int tmp = 0;
            for(int j=0;j<n;j++) {
                if(i>>j&1) tmp ^= nums[j];
            }
            ans += tmp;
        }
        return ans;
    }
};

5760. 构成交替字符串需要的最小交换次数

模拟就好， 我这里写的太麻烦了。

先判断下1 和0的个数是否是差值不大于1的. 否则无解。

然后在分情况讨论下 看和1010101 或者 0101010 的差异个数， 除 2 就是了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int minSwaps(string s) {
        // 111000
        // 101010
        int a0 = 0, a1 = 0;
        string ss;
        for(auto c: s) {
            if(c == '0') {
                a0 ++;
            } else {
                a1 ++;
            }
        }
        if(abs(a0-a1)>1) return -1;
        else if(a0 == a1){
            int ans1 = 0, ans2 = 0;
            //. 0101010   1010101
            for(int i=0;i<s.size();i++) {
                if(i&1) {
                    if(s[i] != '1') ans1++;
                    if(s[i] != '0') ans2++;
                } else {
                    if(s[i] != '0') ans1++;
                    if(s[i] != '1') ans2++;
                }
            }
            // printf("%s | %d %d\n", s.c_str(), ans1, ans2);
            return min(ans1, ans2)/2;
        } else {
            if(a0 > a1) {
                int ans1 = 0;
                //. 0101010
                for(int i=0;i<s.size();i++) {
                    if(i&1) {
                        if(s[i] != '1') ans1++;
                    } else {
                        if(s[i] != '0') ans1++;
                    }
                }
                return ans1/2;
            } else {
                int ans2 = 0;
                //. 1010101
                for(int i=0;i<s.size();i++) {
                    if(i&1) {
                        if(s[i] != '0') ans2++;
                    } else {
                        if(s[i] != '1') ans2++;
                    }
                }
                return ans2/2;
            }
        }
    }
};

5761. 找出和为指定值的下标对

数据结构实现题，这里观察下数据范围， 应该容易想到可以遍历nums1 同时将 nums2中的元素放入map中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class FindSumPairs {
    int ans;
    vector<int> a1, a2;
    map<int, int> mp;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        a1 = nums1;
        a2 = nums2;
        for(auto num: nums2) {
            mp[num] ++;
        }
    }

    void add(int index, int val) {
        mp[a2[index]] --;
        a2[index] += val;
        mp[a2[index]] ++;
    }

    int count(int tot) {
        int ans = 0;
        for(auto a: a1) {
            if(tot-a>0 && mp.count(tot-a)) {
                ans += mp[tot-a];
            }
        }
        return ans;
    }
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(nums1, nums2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

5762. 恰有 K 根木棍可以看到的排列数目

这个题最开始想偏了， 当成了 LIS 的个数， 想了半天不回做， 后来改了回来。

首先打了个表， 看下结果的规律， 然后就写了， 这里和杨辉三角差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    static const int MOD = 1e9+7;
    void test() {
        for(int i=1;i<=10;i++) {
            vector<int> a(i);
            vector<int> dp(i);
            vector<int> ans(i+1);
            for(int j=0;j<i;j++) a[j]=j;
            do{
                int sum = 1, mx = a[0];
                for(int j=1;j<i;j++) {
                    if(a[j]>mx) {
                        sum++;
                        mx = a[j];
                    }
                }
                ans[sum]++;
            }while(next_permutation(a.begin(), a.end()));

            for(auto x: ans) printf("%d ", x); puts("");
        }
    }
    // int f[1001][1001];
    int g[1001][1001];
    void init() {
        g[1][1] = 1;
        for(int i=2;i<=1000;i++) {
            for(int j=1;j<=i;j++) {
                // f[i][j] = (f[i-1][j] + f[i-1][j-1])%MOD;
                g[i][j] = (0LL+g[i-1][j-1] + 1LL*(i-1)*g[i-1][j]%MOD)%MOD;
            }
            // for(int j=1;j<=i;j++) printf("%d ", f[i][j]);puts("");
            // for(int j=1;j<=i;j++) printf("%d ", g[i][j]);puts("");
        }

    }
    int rearrangeSticks(int n, int k) {
        // test();
        init();
        return g[n][k];
    }
};