第 362 场 LeetCode 周赛题解

A 与车相交的点

数据范围小直接暴力枚举

class Solution {
public:
    int numberOfPoints(vector <vector<int>> &nums) {
        unordered_set<int> vis;
        for (auto &p: nums)
            for (int i = p[0]; i <= p[1]; i++)
                vis.insert(i);
        return vis.size();
    }
};
1
2
3
4
5
6
7
8
9
10

---

B 判断能否在给定时间到达单元格

设起点和终点的横坐标之差的绝对值为 $dx$ ， 纵坐标之差的绝对值为 $dy$ ，则最少需要的时间 $mn$ 为 $max(dx,dy)$，当起点终点不重合时只需要 $t\ge mn$ 即可， 起点终点重合需要 $t\ge 2$ 或 $t=0$。

class Solution {
public:
    bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
        int dx = abs(sx - fx), dy = abs(sy - fy);
        int mn = min(dx, dy) + max(dx, dy) - min(dx, dy);
        if (mn != 0)
            return t >= mn;
        return t >= 2|| t == 0;
    }
};
1
2
3
4
5
6
7
8
9
10

---

C 将石头分散到网格图的最少移动次数

枚举排列：将待移动的石子的坐标加入数组 $start$ ，将没有石子的坐标加入数组 $target$ ，枚举 $start$ 可能的排列，一种排列和 $target$ 对应一种移动方案。

class Solution {
public:
    int minimumMoves(vector<vector<int>> &grid) {
        vector<pair<int, int>> start, target;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (grid[i][j] >= 1) {
                    for (int k = 0; k < grid[i][j] - 1; k++)
                        start.emplace_back(i, j);
                } else if (grid[i][j] == 0)
                    target.emplace_back(i, j);
        sort(start.begin(), start.end());
        int res = INT32_MAX;
        do {
            int t = 0;
            for (int i = 0; i < start.size(); i++) {
                t += abs(start[i].first - target[i].first) + abs(start[i].second - target[i].second);
                if (t >= res)
                    break;
            }
            res = min(res, t);
        } while (next_permutation(start.begin(), start.end()));
        return res;
    }
};
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

---

D 字符串转换

动态规划 + 字符串哈希 + 矩阵快速幂：设 $cnt$ 为满足“将 $s$ 的长为 $l(0\le l<n)$ 的后缀移动到 $s$ 的开头后 $s==t$ ” 的 $l$ 的个数。设 $p_k$ 为：恰好 $k$ 次操作后 $s$ 变为 $t$ 的方案数，设 $q_k$ 为：恰好 $k$ 次操作后 $s$ 不能变为 $t$ 的方案数，因为题目要求操作的后缀长度 $0<l<n$ ， 所以有矩阵形式的转移方程： [ p k q k ] = [ c n t − 1 c n t n − c n t n − c n t − 1 ] [ p k − 1 q k − 1 ]

[pkqk]" role="presentation">[pkqk]$$\left[\begin{array}{c}{p}_k\\ q_k\end{array}\right]$$

=

[cnt−1cntn−cntn−cnt−1]" role="presentation">[cnt−1n−cntcntn−cnt−1]$$\left[\begin{array}{cc}cnt-1& cnt\\ n-cnt& n-cnt-1\end{array}\right]$$

[pk−1qk−1]" role="presentation">[pk−1qk−1]$$\left[\begin{array}{c}{p}_{k-1}\\ q_{k-1}\end{array}\right]$$

[pk​qk​​]=[cnt−1n−cnt​cntn−cnt−1​][pk−1​qk−1​​]
若 $s==t$ 则 $[p_0,q_0{]}^T=[1,0{]}^T$ ，否则 $[p_0,q_0{]}^T=[0,1{]}^T$，设转移方程中的方阵为 $A$ ，则有 $[p_k,q_k{]}^T=A^k[p_0,q_0{]}^T$ ，通过矩阵快速幂求 $A^k$ 。

class Solution {
public:
    using ll = long long;
    using type_mat = vector<vector<ll>>;
    ll mod = 1e9 + 7;

    type_mat pow_mat(type_mat &mat, ll n) {//矩阵快速幂
        type_mat res = mat;//mat^n=mat*mat^(n-1)
        n--;
        for (type_mat e = mat; n; e = mat_product(e, e), n >>= 1)
            if (n & 1)
                res = mat_product(res, e);
        return res;
    }

    vector<vector<ll>> mat_product(type_mat &a, type_mat &b) {//矩阵乘法
        int m = a.size(), n = b[0].size(), mid = a[0].size();
        type_mat res(m, vector<ll>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int k = 0; k < mid; k++)
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j] % mod) % mod;
        return res;
    }

    int numberOfWays(string s, string t, long long k) {
        int n = s.size();
        shash h1(s, 2333, 1e9 + 9), h2(t, 2333, 1e9 + 9);
        int cnt = 0;
        bool flag = false;//s是否等于t
        if (h1(0, n - 1) == h2(0, n - 1)) {
            cnt++;
            flag = true;
        }
        for (int i = 1; i < n; i++)//判断将s长为i的后缀移至s的开头后s是否等于t
            if (h1(n - i, n - 1) == h2(0, i - 1) && h1(0, n - i - 1) == h2(i, n - 1))
                cnt++;
        vector<vector<ll>> A{{cnt - 1, cnt},
                             {n - cnt, n - cnt - 1}};
        type_mat res = pow_mat(A, k);
        return flag ? (res[0][0] + mod) % mod : (res[0][1] + mod) % mod;
    }

    class shash {//字符串哈希模板
    public:
        vector<ll> pres;
        vector<ll> epow;
        ll e, p;

        shash(string &s, ll e, ll p) {
            int n = s.size();
            this->e = e;
            this->p = p;
            pres = vector<ll>(n + 1);
            epow = vector<ll>(n + 1);
            epow[0] = 1;
            for (int i = 0; i < n; i++) {
                pres[i + 1] = (pres[i] * e + s[i]) % p;
                epow[i + 1] = (epow[i] * e) % p;
            }
        }

        ll operator()(int l, int r) {//返回s[l,r]对应的哈希值
            ll res = (pres[r + 1] - pres[l] * epow[r - l + 1] % p) % p;
            return (res + p) % p;
        }
    };

};
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
57
58
59
60
61
62
63
64
65
66
67
68
69

---