img

力扣第401场周赛

A

暴力一下即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int numberOfChild(int n, int k)
    {
        int i=0;
        int status=0;
        while(k--)
        {
            if(status == 0) i++;
            else if(status == 1) i--;
            if(i==n-1) status = 1;
            else if(i==0) status = 0;
        }
        return i;
    }
};

B

前缀和做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
   int valueAfterKSeconds(int n, int k) {
       vector<int> nums(n, 1), presum(n);

       for (int i = 0; i < k; ++i) {
           presum[0] = 1;

           for (int j = 1; j < n; ++j) {
               presum[j] = (presum[j - 1] + nums[j]) % 1000000007;
           }

           nums = presum;
       }

       return nums.back();
   }
};

然而：

斜着看可以发现有组合数的规律

1
2
3
4
5
6
1
1,1
1,2,1
1,3,3,1
1,4,6,4
1,5,10,10

最后就是求解C（n-1+k,n-1)

只需要用一个逆元求组合数即可。

组合数模板详看灵神(灵茶山艾府）：

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
const int MOD = 1'000'000'007;
const int MX = 2001;

long long q_pow(long long x, int n) {
    long long res = 1;
    for (; n > 0; n /= 2) {
        if (n % 2) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

// 组合数模板
long long fac[MX], inv_fac[MX];

auto init = [] {
    fac[0] = 1;
    for (int i = 1; i < MX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv_fac[MX - 1] = q_pow(fac[MX - 1], MOD - 2);
    for (int i = MX - 1; i > 0; i--) {
        inv_fac[i - 1] = inv_fac[i] * i % MOD;
    }
    return 0;
}();

long long comb(int n, int k) {
    return fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

class Solution {
public:
    int valueAfterKSeconds(int n, int k) {
        return comb(n + k - 1, k);
    }
};

C

D

C和D是一样的，但范围不一致。

本题排完序就是一个普通的01背包。由于D数据过大，需要进行bitset优化：

定义f[i][j]为能否从前i个数中得到奖励j

那么就可以有

f[i][j]=f[i-1][j]

f[i][j]=f[i-1][j-v]

因此f[i][j]=f[i-1][j]||f[i-1][j-v]

答案就是f[n][j]=1中最大的j

由于0<=j-v<v，转移时候相当于取f的低v位，再左移v位，然后与f取按位或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) 
    {
        ranges::sort(rewardValues);
        rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
        bitset<100000> f{1};
        for (int v : rewardValues) 
        {
            int a = f.size() - v;
            f |= f << a >> (a - v); // 简化上式
        }
        for (int i = rewardValues.back() * 2 - 1; ; i--) 
        {
            if (f.test(i)) 
            {
                return i;
            }
        }
    }
};