526互联

第 117 场双周赛（容斥原理，记忆化搜索，排序）

发布时间 2023-11-12 21:19:12作者: 深渊之巅

 本题我们采用隔板法+容斥原理来解决

合格总方案数 = 总方案书 - 不合理的方案数 = 不考虑limit的方案数 - 不合法方案数（至少有一个小朋友 > limit）

任意方案数 n个小球放到3个盒子中 -> n + 2个位置，选两个位置放隔板剩下位置放球 c(n + 2, 2)

三个小朋友为：甲乙丙

小朋友甲（乙丙）>limit 的方案数 c(n - (limit+1) + 2, 2)

小朋友甲乙（甲丙，乙丙）> limit 方案数 c(n - (limit + 1) * 2 + 2, 2)

下朋友甲乙丙三个都 > limit 的方案数 c(n - (limit + 1) * 3 + 2, 2)

def c2(n: int) -> int:
    return n * (n - 1) // 2 if n > 1 else 0

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        return c2(n + 2) - 3 * c2(n - (limit + 1) + 2) + 3 * c2(n - 2 * (limit + 1) + 2) - c2(n - 3 * (limit + 1) + 2)

 

 解法1：dfs

本题可以抽象为一个分组背包问题方案数

n组物品，每组可以选择a - z至少选择1个'l', 1个t，2个e的方案数

MOD = 10 ** 9 + 7

@cache
def dfs(i: int, L: int, t: int, e: int) -> int:
    if i == 0:
        return 1 if L == 0 and t == 0 and e == 0 else 0
    
    res = dfs(i - 1, 0, t, e)
    res += dfs(i - 1, L, 0, e)
    res += dfs(i - 1, L, t, max(0, e - 1))
    res += dfs(i - 1, L, t, e) * 23
    return res % MOD

class Solution:
    def stringCount(self, n: int) -> int:
        return dfs(n, 1, 1, 2)

解法2: 容斥原理

与上一题类似，详细理解 灵神的详细讲解

class Solution:
    def stringCount(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        return (
            pow(26, n, MOD)
           -pow(25, n - 1, MOD) * (75 + n)
           +pow(24, n - 1, MOD) * (72 + n * 2)
           -pow(23, n - 1, MOD) * (23 + n)
        ) % MOD

 

 

 

class Solution {
public:
    long long maxSpending(vector<vector<int>>& values) {
        int n = values.size(), m = values[0].size();
        vector<int> arr(n * m + 1, 0);
        
        int idx = 0;
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < m; j ++ ) {
                arr[idx ++ ] = values[i][j];
            }
        }
        
        sort(arr.begin(), arr.end());
        
        long long res = 0;
        for(int i = 0; i <= idx; i ++ ) {
            res += (long long)i * arr[i];
        }
        
        return res;
        
    }
};