第 241 场周赛

2024-03-25 11:10:22

文章目录

第 241 场周赛

第 241 场周赛

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

深搜

二进制枚举

分析 + 排列组合

深搜

每一个元素只有两种状态，取或者不取。在递归的过程中同时记录当前所取元素的异或值。

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int ans = 0;
        dfs(ans, 0, 0, nums);
        return ans;
    }

    void dfs(int& ans, int xor_val, size_t idx, const vector<int>& nums) {
        if (idx == nums.size()) {
            ans += xor_val;
            return;
        }
        dfs(ans, xor_val ^ nums[idx], idx + 1, nums);
        dfs(ans, xor_val, idx + 1, nums);
        return;
    }
};

二进制枚举

n 个元素取和不取的每一种组合可以看作是 [ 0 , 2 n − 1 ] \left[0,2^{n}-1\right] [0,2n−1] 范围内整数的二进制表示，其中对于某个整数 x，如果其二进制表示中第 i 位为 0 表示数组中第 i 位元素不取，否则表示第 i 位元素取

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < (1 << n); ++i) {   // 遍历所有子集
            int tmp = 0;
            for (int j = 0; j < n; ++j) {   // 遍历每个元素
                if (i & (1 << j)){
                    tmp ^= nums[j];
                }
            }
            ans += tmp;
        }
        return ans;
    }
};

分析 + 排列组合

n 个 0 异或为 0

偶数个 1 异或为 0

考虑每一个元素的二进制表示

假设 n 个元素中二进制表示下第 i 位为 1 的元素的个数为 m

首先这 m 个元素的组合共有 2 m 2^{m} 2m，其中选取奇数个元素的组合等于选取偶数个元素的组合均为 2 m − 1 2^{m - 1} 2m−1（因为每个元素均有两种状态，选和不选；对于某一个元素，如果不选产生的是偶数组合，那么选上就会生成相应的奇数组合），对于选取偶数个元素的组合，其异或值第 i 位为 0，选取奇数的组合第 i 位异或值为 1
其次剩下的 n-m 个元素的组合有 2 n − m 2^{n-m} 2n−m 种，且这 2 n − m 2^{n-m} 2n−m 种组合的异或值的第 i 位均为 0
综上，如果 n 个元素种存在某一个元素的二进制表示下第 i 位为 1，那么将会产生 2 m − 1 ∗ 2 n − m = 2 n − 1 2^{m - 1} * 2^{n - m} = 2^{n - 1} 2m−1∗2n−m=2n−1 个组合，其异或值第 i 位为 1 ,那么其对最终结果的贡献值为 ( 1 < < i ) ∗ 2 n − 1 (1 << i) * 2^{n - 1} (1<<i)∗2n−1。

所以最终结果为所有元素中二进制表示下存在 1 的位左移 n-1 位相加。

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (auto num: nums){
            ans |= num;
        }
        return ans << (n - 1);
    }
};

那么问题就变成将已知字符串转换为两种交替字符串其中一种需要最少的交换次数（当然前提是需要可以交换过去：即 0 和 1 的数量差绝对值小于等于 1），只需要将源字符串和两种交替字符串进行比较统计不匹配的字符个数即可，结果为 m i n ( 第一种不匹配字符个数，第二种不匹配字符个数 ) / 2 min(第一种不匹配字符个数，第二种不匹配字符个数) / 2 min(第一种不匹配字符个数，第二种不匹配字符个数)/2，

注意：不匹配个数需要是偶数，否则无法完成交换

为什么可以保证是最小的交换次数，因为每一个不匹配的位都只进行了一次必要的交换，匹配的位没有发生交换

class Solution {
public:
    int minSwaps(string s) {
        int one_num = 0, zero_num = 0; // 0 和 1 的数量
        int diff0 = 0, diff1 = 0; // 与以 0 开头和以 1 开头的差异数
        for (size_t i = 0; i < s.size(); ++i) {
            if (s[i] == '0')
                zero_num++;
            else
                one_num++;
            
            if (i % 2 == 0)
                if (s[i] == '0')
                    diff1++;
                else
                    diff0++;
            else
                if (s[i] == '1')
                    diff1++;
                else
                    diff0++;
        }
        
        if (diff0 % 2)
            diff0 = INT_MAX;
        if (diff1 % 2)
            diff1 = INT_MAX;

        if (abs(one_num - zero_num) > 1)
            return -1;
        else 
            return min(diff0 / 2, diff1 / 2);
    }
};

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

模拟、STL 的使用

将 nums2 中的元素存入一个 map 中，然后直接进行操作即可

class FindSumPairs {
    map<int, int> map2;
    vector<int> nums1;
    vector<int> nums2;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        map2.clear();
        this->nums1 = nums1;
        this->nums2 = nums2;
        
        for (size_t i = 0; i < nums2.size(); ++i) {
            if (map2.find(nums2[i]) == map2.end())
                map2.insert(make_pair(nums2[i], 1));
            else
                map2[nums2[i]]++;
        }
    }
    
    void add(int index, int val) {
        if (map2.find(nums2[index] + val) == map2.end())
            map2.insert(make_pair(nums2[index] + val, 1));
        else
            map2[nums2[index] + val]++;
        map2[nums2[index]]--;
        nums2[index] += val;
        return;
    }
    
    int count(int tot) {
        int ans = 0;
        for (size_t i = 0; i < nums1.size(); ++i) {
            ans += map2[tot - nums1[i]];
        }
        return ans;
    }
};

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

数学（第一类斯特林数）

动态规划

数学

第一类斯特林数（无符号）：

[ n k ] \left[\begin{array}{l}n \\ k\end{array}\right] [nk] 表示将 n 个互不相同的元素划分成 k 个圆排列的方案数，也可以表示为 s ( n , k ) s(n, k) s(n,k)，其递推式为：
[ n k ] = [ n − 1 k − 1 ] + ( n − 1 ) [ n − 1 k ] \left[\begin{array}{l} n \\ k \end{array}\right]=\left[\begin{array}{l} n-1 \\ k-1 \end{array}\right]+(n-1)\left[\begin{array}{c} n-1 \\ k \end{array}\right] [nk]=[n−1k−1]+(n−1)[n−1k]
其中， [ 0 0 ] = 1 , [ n 0 ] = 0 ( n ! = 0 ) , [ 0 k ] = 0 ( k ! = 0 ) \left[\begin{array}{l}0 \\ 0\end{array}\right] = 1, \left[\begin{array}{l}n \\ 0\end{array}\right] = 0(n != 0), \left[\begin{array}{l}0 \\ k\end{array}\right] = 0(k!=0) [00]=1,[n0]=0(n!=0),[0k]=0(k!=0)，

第二类斯特林数：

{ n k } \left\{\begin{array}{l}n \\ k\end{array}\right\} {nk} 表示将 n 个互不相同的元素划分成 k 个非空集合的方案数，可以表示为 S ( n , k ) S(n, k) S(n,k)，其递推式为：
{ n k } = { n − 1 k − 1 } + k { n − 1 k } \left\{\begin{array}{l} n \\ k \end{array}\right\}=\left\{\begin{array}{c} n-1 \\ k-1 \end{array}\right\}+k\left\{\begin{array}{c} n-1 \\ k \end{array}\right\} {nk}={n−1k−1}+k{n−1k}
其中， { 0 0 } = 1 , { n 0 } = 0 ( n ! = 0 ) , { 0 k } = 0 ( k ! = 0 ) \left\{\begin{array}{l}0 \\ 0\end{array}\right\} = 1, \left\{\begin{array}{l}n \\ 0\end{array}\right\} = 0(n != 0), \left\{\begin{array}{l}0 \\ k\end{array}\right\} = 0(k != 0) {00}=1,{n0}=0(n!=0),{0k}=0(k!=0)，

解释：

第一类斯特林数：

s ( n , k ) s(n, k) s(n,k) 表示将 n 个不相同的元素划分成 k 个圆排列的方案数，那么 s ( n , k ) s(n, k) s(n,k) 可以由两部分组成：

第一部分，算最后一个元素，则前 n-1 个元素划分成 k-1 个圆排列，最后一个元素是一个单独的圆排列，即 s ( n − 1 , k − 1 ) s(n - 1, k - 1) s(n−1,k−1)

第二部分，不算最后一个元素，前 n-1 个元素划分成 k 个圆排列，即 s ( n − 1 , k ) s(n - 1, k) s(n−1,k)，最后将最后一个元素插入前 n-1 个元素的左边，构成一个整体，那么之前的 s ( n − k , k ) s(n - k, k) s(n−k,k) 中的每一种方案都将变成 n-1 种，即会产生 s ( n − 1 , k ) ∗ ( n − 1 ) s(n - 1, k) * (n - 1) s(n−1,k)∗(n−1) 种方案数

最终可得： s ( n , k ) = s ( n − 1 , k − 1 ) + s ( n − 1 , k ) ∗ ( n − 1 ) s(n, k) = s(n - 1, k - 1) + s(n - 1, k) * (n - 1) s(n,k)=s(n−1,k−1)+s(n−1,k)∗(n−1)

第二类斯特林数：

思路同上

虽然是两种方法但是解释是一样的，即可以将该问题看成将 n 根木棍划分成 k 个圆排列：

由于划分成的 k 组，每一组均有一个最大值，将 k 组的最大值取出，作为可以看见的 k 根棍
假设某个小组内有 s 个元素，则该小组产生的排列数为 ( s − 1 ) ! (s-1) ! (s−1)!种（因为最大的必须放最前边），和 s 个元素所组成的圆排列数相等

所以该问题可以转化成第一类斯特林数。

class Solution {
    int MOD = 1e9 + 7;
public:
    int rearrangeSticks(int n, int k) {
        long long dp[n + 5][k + 5];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % MOD;
            }
        }

        return dp[n][k];
    }
};

暴力求解斯特林数时间复杂度为 O ( n ∗ k ) O(n * k) O(n∗k)，但有更高效的方法计算

码农公寓

第 241 场周赛

文章目录

第 241 场周赛

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

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

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

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

码农公寓

文章目录

第 241 场周赛

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

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

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

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

相关文章