第 362 场 LeetCode 周赛题解

数据范围小直接暴力枚举

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();}
};

设起点和终点的横坐标之差的绝对值为 $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;}
};

枚举排列：将待移动的石子的坐标加入数组 $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;}
};

动态规划 + 字符串哈希 + 矩阵快速幂：设 $cnt$ 为满足“将 $s$ 的长为 $l(0\le l<n)$ 的后缀移动到 $s$ 的开头后 $s==t$ ” 的 $l$ 的个数。设 $p_k$ 为：恰好 $k$ 次操作后 $s$ 变为 $t$ 的方案数，设 $q_k$ 为：恰好 $k$ 次操作后 $s$ 不能变为 $t$ 的方案数，因为题目要求操作的后缀长度 $0<l<n$ ， 所以有矩阵形式的转移方程：$$\left[\begin{array}{c}{p}_k\\ q_k\end{array}\right]=\left[\begin{array}{cc}cnt-1& cnt\\ n-cnt& n-cnt-1\end{array}\right]\left[\begin{array}{c}{p}_{k-1}\\ q_{k-1}\end{array}\right]$$
若 $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是否等于tif (h1(0, n - 1) == h2(0, n - 1)) {cnt++;flag = true;}for (int i = 1; i < n; i++)//判断将s长为i的后缀移至s的开头后s是否等于tif (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;}};};