力扣第410场周赛

A

普通模拟即可

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
class Solution {
public:
    int finalPositionOfSnake(int n, vector<string>& commands) {
        int i=0;
        int j=0;
        for(auto s:commands)
        {
            if(s[0]=='U')
            {
                i--;
            }
            else if(s[0]=='D')
            {
                i++;
            }
            else if(s[0]=='L')
            {
                j--;
            }
            else
            {
                j++;
            }
            
        }
        int ans=n*i+j;
        return ans;
    }
};

B

dfs求解子树大小。

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
class Solution {
public:
    int countGoodNodes(vector<vector<int>>& edges) {
        int n=edges.size()+1;
        vector<vector<int>>g(n);
        for(auto &e:edges)
        {
            int x=e[0];
            int y=e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        int ans=0;
        auto dfs=[&](auto&& dfs,int x,int fa)->int
        {
            int size=1;
            int size0=0;
            bool ok=true;
            for(int y:g[x])
            {
                if(y==fa)
                {
                    continue;
                }
                int sz=dfs(dfs,y,x);
                if(size0==0)
                {
                    size0=sz;
                }
                else if(sz!=size0)
                {
                    ok=false;
                }
                size+=sz;
            }
            ans+=ok;
            return size;
        };
        dfs(dfs,0,-1);
        return ans;


        }
};

C/D

建议参考灵神的视频，那个k的推导确实绝妙。

值域类dp。

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
class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        const int MOD = 1'000'000'007; // 定义结果取模的常数
        int n = nums.size(); // 数组的长度
        int m = *max_element(nums.begin(), nums.end()); // 数组中元素的最大值

        // f[i][j] 表示在前 i 个元素中，最后一个元素为 j 时的单调数组对的数量
        vector<vector<long long>> f(n, vector<long long>(m + 1));
        vector<long long> s(m + 1); // 用于存储 f[i-1] 的前缀和

        // 初始化 f[0][j]，当 i = 0 时，所有 arr1[0] = j 的情况都合法
        fill(f[0].begin(), f[0].begin() + nums[0] + 1, 1);

        // 遍历从第二个元素到最后一个元素
        for (int i = 1; i < n; i++) {
            // 计算 f[i-1] 的前缀和，方便后续的状态转移
            partial_sum(f[i - 1].begin(), f[i - 1].end(), s.begin());

            // 遍历当前元素可能的值 j
            for (int j = 0; j <= nums[i]; j++) {
                // 计算 k 的最大值，满足 arr1[i-1] ≤ arr1[i] 且 arr2[i-1] ≥ arr2[i]
                int max_k = j + min(nums[i - 1] - nums[i], 0);
                
                // 状态转移：如果 max_k ≥ 0，则 f[i][j] 由前一行的前缀和决定；否则 f[i][j] 为 0
                f[i][j] = max_k >= 0 ? s[max_k] % MOD : 0;
            }
        }

        // 计算最终结果：所有可能的 f[n-1][j] 的和
        return accumulate(f[n - 1].begin(), f[n - 1].begin() + nums[n - 1] + 1, 0LL) % MOD;
    }
};