头像

YimingLi

浙江大学 $\href{https://github.com/upupming}{My\ GitHub}$




离线:1天前



算法

很容易想到可以先把 w2 翻转一下,然后用公共子序列求出长度 t,两个组合就一定是一个长为 2*t 回文串,但是注意还需要加上 w1 或者 w2 自身的回文子序列来构成一个更长的回文串

例子 1:

  • w1 = cacb, w2 = cbba;记 w2 反转之后为 w2' = abbc

    答案就是 [ab][c][ba],其中第 1 部分和第 3 部分是 w1w2' 的最长公共子序列,第 2 部分为 w2 自己的长为 1 的回文序列

  • w1 = abaxyzcbc, w2 = mnmzyx;记 w2 反转之后为 w2' = xyzmnm

    答案就是 [xyz][cbc][zyx],其中第 1 部分和第 3 部分是 w1w2' 的最长公共子序列,第 2 部分为 w1 自己的长为 3 的回文子序列

    注意答案也可以是 [xyz][mnm][zyx],但是不能是 [xyz][cbc][mnm][zyx],也就是说 w1w2 只能两者选一个,选择自身的回文子序列来拼接,我们选最长的那个即可

所以这个题实际上是「AcWing 897. 最长公共子序列」和「LeetCode 516. 最长回文子序列」的结合版

定义集合属性(下标均从 1 开始,方便 dp 的状态转移):
- f1[i][j] 表示 w1[i~j] 内的最大回文子序列长度
- f2[i][j] 表示 w2'[i~j] 内的最大回文子序列长度
- f[i][j] 表示 w1[1~i]w2'[1~j] 的最长公共子序列

上面 3 个数组的计算方式可以参考上面两个模板题。

最终的结果为

max_{i, j} {
    2 * f[i][j] + max(f1[i+1][n], f2[j+1][m])
}

其中 nm 分别为 w1w2' 的长度

时间复杂度

$O(N^2+M^2+NM)$

C++ 代码

const int N = 1e3 + 10;
int f[N][N], f1[N][N], f2[N][N];
class Solution {
    void calSub(string& w1, int n, int f1[][N]) {
        // 最长回文子序列,区间 dp 模板
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                if (len == 1)
                    f1[i][j] = 1;
                else {
                    f1[i][j] = max(f1[i + 1][j], f1[i][j - 1]);
                    if (w1[i] == w1[j]) {
                        f1[i][j] = max(f1[i][j], f1[i + 1][j - 1] + 2);
                    }
                }
            }
        }
    }

   public:
    int longestPalindrome(string w1, string w2) {
        int n = w1.length(), m = w2.length();
        // 翻转得到 w2'
        reverse(w2.begin(), w2.end());
        int ans = 0;
        memset(f, 0, sizeof f);
        memset(f1, 0, sizeof f1);
        memset(f2, 0, sizeof f2);
        // 加上空格,这样字符串从 1 开始索引,避免处理边界
        w1 = ' ' + w1, w2 = ' ' + w2;

        calSub(w1, n, f1);
        calSub(w2, m, f2);

        // 最长公共子序列模板
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = max(f[i][j - 1], f[i - 1][j]);
                if (w1[i] == w2[j])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);

                // w1 和 w2 选的子序列要非空,等价于公共子序列非空
                if (f[i][j]) {
                    ans = max(ans, 2 * f[i][j] + max(f1[i + 1][n], f2[j + 1][m]));
                }
            }
        }

        return ans;
    }
};



f[i][j] 表示 nums 从 i 开始,multiplier 从 j 开始的所有可能方案的最大分数
,nums 末尾已经被使用的数的个数一定是 (j-i),因此最后一个数的下标为 n - (j - i) - 1

f[i][j] 每次针对 multiplier[j] 有两种转移方案:

  • 选开头的 nums[i] 来乘,剩下的方案表示为 f[i+1][j+1]
  • 选结尾的 nums[n - (j - i) - 1] 来乘,剩下的方案表示为 f[i][j+1]

注意到从前面数和从后面数,下标大于 2*10^3 的 nums[i] 一定不会被访问,因此数组 f 只用开到 m*m 维即可(开成 n*m 会 TLE)

最后结果就是 f[0][0]

const int M = 1e3 + 10;
int f[M][M];

class Solution {
    int n, m;

   public:
    int maximumScore(vector<int>& nums, vector<int>& mul) {
        n = nums.size(), m = mul.size();
        memset(f, 0, sizeof f);
        for (int j = m - 1; j >= 0; j--) {
            for (int i = 0; i <= j; i++) {
                f[i][j] = max(
                    f[i + 1][j + 1] + nums[i] * mul[j],
                    f[i][j + 1] + (nums[n - (j - i) - 1]) * mul[j]);
            }
        }
        return f[0][0];
    }
};

记忆化搜索版本:

#include <bits/stdc++.h>
using namespace std;
const int M = 1e3 + 10;
int f[M][M];
class Solution {
    int n, m;
    int dp(int i, int j, vector<int>& nums, vector<int>& mul) {
        if (j >= m) return 0;
        if (f[i][j] != 0x3f3f3f3f) return f[i][j];
        f[i][j] = max(
            dp(i + 1, j + 1, nums, mul) + nums[i] * mul[j],
            dp(i, j + 1, nums, mul) + (nums[n - (j - i) - 1]) * mul[j]);
        return f[i][j];
    }

   public:
    int maximumScore(vector<int>& nums, vector<int>& mul) {
        memset(f, 0x3f, sizeof f);
        n = nums.size(), m = mul.size();
        return dp(0, 0, nums, mul);
    }
};




题目描述

给你一个 n 个节点的树(也就是一个无环连通无向图),节点编号从 0n - 1 ,且恰好有 n - 1 条边,每个节点有一个值。树的 根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值,edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

gcd(x, y) == 1 ,我们称两个数 xy 是 互质的 ,其中 gcd(x, y)xy 的 最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ,其中ans[i]是离节点 i 最近的祖先节点且满足nums[i]nums[ans[i]] 是 互质的 ,如果不存在这样的祖先节点,ans[i]-1

示例 1:

输入:nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]] 输出:[-1,0,0,1] 解释:上图中,每个节点的值在括号中表示。 - 节点 0 没有互质祖先。 - 节点 1 只有一个祖先节点 0 。它们的值是互质的(gcd(2,3) == 1)。 - 节点 2 有两个祖先节点,分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的(gcd(3,3) == 3)但节点 0 的值是互质的(gcd(2,3) == 1),所以节点 0 是最近的符合要求的祖先节点。 - 节点 3 有两个祖先节点,分别是节点 1 和节点 0 。它与节点 1 互质(gcd(3,2) == 1),所以节点 1 是离它最近的符合要求的祖先节点。

示例 2:

输入:nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]] 输出:[-1,0,-1,0,0,0,-1]

提示:

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

算法

无向树的 DFS

无向树遍历的套路:dfs 传入一个 father,避免反向遍历

如果直接存祖先路径上所有的数的话,在树是线性的时候复杂度会退化为 $O(N^2)$,我在比赛的时候就被卡在了34/36个测试用例。

但是,这个题目有个很重要的性质,就是 num[i] <= 50,这样在找每个节点的 ans 的时候,可以直接暴力枚举 1~50,看是否互质,如果互质,在最近的哪一层
然后我们用 dep[t] 表示数 t 所在的离当前层的最近的层,-1 表示 t 在祖先中没有存在过
然后我们用 pos[t] 表示满足上述条件的数 t 的节点编号

时间复杂度

$O(50 \cdot N)$

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;

int ver[M], Next[M], head[N], tot;
int pos[60], dep[60];
class Solution {
    int n, m;
    vector<int> ans, nums;
    void add(int x, int y) {
        ver[++tot] = y;
        Next[tot] = head[x], head[x] = tot;
    }

    void dfs(int x, int fa, int depth) {
        for (int t = 1; t <= 50; t++) {
            // 如果祖先存在数 t 和 x 互质的话
            if (dep[t] != -1 && __gcd(t, nums[x]) == 1) {
                // 记录 pos 最大,也就是最深的那个祖先
                if (ans[x] == -1 || dep[t] > dep[nums[ans[x]]]) {
                    ans[x] = pos[t];
                }
            }
        }

        int b1 = dep[nums[x]], b2 = pos[nums[x]];
        dep[nums[x]] = depth, pos[nums[x]] = x;
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (y != fa) dfs(y, x, depth + 1);
        }
        dep[nums[x]] = b1, pos[nums[x]] = b2;
    }

   public:
    vector<int> getCoprimes(vector<int>& _nums, vector<vector<int>>& e) {
        memset(head, 0, sizeof head), tot = 0;
        nums = _nums;
        n = nums.size(), m = e.size();
        ans = vector<int>(n, -1);
        for (auto& t : e) {
            add(t[0], t[1]), add(t[1], t[0]);
        }
        memset(dep, -1, sizeof dep);
        dfs(0, -1, 0);
        return ans;
    }
};




#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
    bool canChoose(vector<vector<int>>& g, vector<int>& nums) {
        int n = g.size(), m = nums.size();

        for (int i = 0, j = 0; i < n; i++) {
            bool ok = false;
            // 匹配第 i 个数组
            for (int k = 0; k < g[i].size() && j < m;) {
                if (g[i][k] == nums[j]) {
                    k++, j++;
                    if (k == g[i].size()) {
                        // cout << k << " " << g[i][k] << " " << j << " " << nums[j] << endl;
                        ok = true;
                        break;
                    }
                } else {
                    if (k == 0) j++;
                    k = 0;
                }
                // cout << i << " " << k << " " << j << endl;
                // cout << g[i][k] << " " << nums[j] << endl;
            }
            // cout << i << ", " << j << " " << ok << endl;
            if (!ok) return false;
        }
        return true;
    }
};




#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
class Solution {
   public:
    vector<vector<int>> highestPeak(vector<vector<int>>& w) {
        int m = w.size(), n = w[0].size();
        vector<vector<int>> h(m, vector<int>(n, INT_MAX));
        vector<vector<bool>> v(m, vector<bool>(n, false));
        queue<PII> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (w[i][j]) {
                    h[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        while (q.size()) {
            auto t = q.front();
            q.pop();
            for (int k = 0; k < 4; k++) {
                int x = t.first + dx[k];
                int y = t.second + dy[k];
                if (x < 0 || x >= m || y < 0 || y >= n) continue;
                if (v[x][y]) continue;
                v[x][y] = true;
                h[x][y] = min(h[x][y], h[t.first][t.second] + 1);
                q.push({x, y});
            }
        }
        return h;
    }
};




#include <bits/stdc++.h>
using namespace std;
class Solution {
    bool is(string s) {
        set<char> st;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            st.insert(s[i]);
        }
        for (auto x : st) {
            if (x >= 'a' && x <= 'z') {
                if (!st.count(x - 'a' + 'A')) return false;
            } else {
                if (!st.count(x - 'A' + 'a')) return false;
            }
        }
        return true;
    }

   public:
    string longestNiceSubstring(string s) {
        string ans;
        int n = s.length();
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                string t = s.substr(i, len);
                if (is(t)) {
                    ans = t;
                    break;
                }
            }
        }
        return ans;
    }
};



活动打卡代码 AcWing 901. 滑雪

/*
f[i][j] 表示从 (i, j) 出发的最长轨迹
根据 > 关系,一定不会有循环依赖关系
*/
#include <cstring>
#include <iostream>
using namespace std;
const int N = 310;

int a[N][N], r, c, f[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int dp(int i, int j) {
    if (f[i][j] != -1) return f[i][j];
    bool flag = false;
    for (int k = 0; k < 4; k++) {
        int x = i + dx[k], y = j + dy[k];
        if (x < 0 || x >= r || y < 0 || y >= c) continue;
        if (a[i][j] > a[x][y]) {
            flag = true;
            f[i][j] = max(f[i][j], dp(x, y) + 1);
        }
    }
    // 初始条件
    if (!flag) f[i][j] = 1;
    return f[i][j];
}
int main() {
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    memset(f, -1, sizeof f);
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            ans = max(ans, dp(i, j));
        }
    }
    cout << ans << endl;
    return 0;
}




/*
https://www.acwing.com/solution/content/26575/
f[i][j][a][b] 表示所有这样的数的平方和:
1. 一共有 i 位
2. 最高位为 j
3. 数本身模 7 为 a
4. 各位数字之和模 7 为 b
转移:
枚举次高位填 k:
j*10^{i-1} + c == a
因此 c == a - j*10^{i-1}
f[i-1][k][a - j*10^{i-1}][b-j]
如果是直接求数的个数,肯定是 f[i][j][a][b] 直接加上面这个式子就行,但是答案要求的是平方和

对于所有的数(X 表示可以任意取):
AX...X = A*power[i-1] + X...X
他们的平方和为:
(A*power[i-1])^2 * cnt + sigma (X...X)^2 + sigma 2 * (A * power[i-1] * (X...X))
cnt 是所有可能的数的个数
这里面需要用到所有数的和,就是:
A*power[i-1] * cnt + (X...X)
*/
#include <iostream>
#include <vector>
using namespace std;
const int N = 20, P = 1e9 + 7;
typedef long long LL;

struct F {
    // 满足条件的数的「数量」、「和」、「平方和」
    int s0, s1, s2;
} f[N][10][7][7];
// 10 的 i 次方模 7
int pow7[N];
// 10 的 i 次方模 P
LL powP[N];
int mod(LL x, LL y) {
    return (x % y + y) % y;
}
void init() {
    pow7[0] = powP[0] = 1;
    for (int i = 1; i < N; i++) {
        pow7[i] = pow7[i - 1] * 10ll % 7;
        powP[i] = powP[i - 1] * 10ll % P;
    }
    // 初始化
    for (int j = 0; j <= 9; j++) {
        if (j == 7) continue;
        F &v = f[1][j][j % 7][j % 7];
        v.s0 = 1, v.s1 = j, v.s2 = j * j;
    }
    // 递推计算
    for (int i = 2; i < N; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j == 7) continue;
            for (int a = 0; a < 7; a++) {
                for (int b = 0; b < 7; b++) {
                    // 枚举次高位填 k
                    for (int k = 0; k <= 9; k++) {
                        F &x = f[i][j][a][b], y = f[i - 1][k][mod(a - j * pow7[i - 1], 7)][mod(b - j, 7)];
                        // 直接加上 y 的数量
                        x.s0 = mod(x.s0 + y.s0, P);
                        // 除了加上 y 的和,还需要以 j 开头后面全 0 的数计算 cnt(y.s0) 次
                        x.s1 = mod(x.s1 + y.s1 + powP[i - 1] * j % P * y.s0, P);
                        x.s2 = mod(
                            x.s2 +
                                // (j * 10^{i-1})^2 * cnt
                                powP[i - 1] * powP[i - 1] % P * j * j % P * y.s0 +
                                // sigma 2 * (j * power[i-1] * (X...X))
                                // sigma (X...X) = y.s1
                                2 * j * powP[i - 1] % P * y.s1 +
                                // sigma (X...X)^2 = y.s2
                                y.s2,
                            P);
                    }
                }
            }
        }
    }
}

// 得到数 模7不为a,数位和模7不为b的 数的集合
F get(int i, int j, int a, int b) {
    int s0 = 0, s1 = 0, s2 = 0;
    for (int x = 0; x < 7; x++)
        for (int y = 0; y < 7; y++) {
            if (x == a || y == b) continue;
            F v = f[i][j][x][y];
            s0 = (s0 + v.s0) % P;
            s1 = (s1 + v.s1) % P;
            s2 = (s2 + v.s2) % P;
        }
    return {s0, s1, s2};
}

int dp(LL n) {
    // 0 % 7 == 0,不合法
    if (n == 0) return 0;
    vector<int> a;
    // 备份一下,最后会需要用到
    LL nn = n % P;
    while (n) a.push_back(n % 10), n /= 10;
    int len = a.size();

    int ans = 0;
    // 前面的数,前面的数位和
    LL last_a = 0, last_b = 0;
    for (int i = len - 1; i >= 0; i--) {
        int x = a[i];
        // 左侧分支:选择 1~(x-1) 来填
        for (int j = 0; j < x; j++) {
            if (j == 7) continue;
            // 1. 数模 7 不能为 a
            int a = mod(-last_a * pow7[i + 1], 7);
            // 2. 数位和模 7 不能为 b
            int b = mod(-last_b, 7);
            F v = get(i + 1, j, a, b);
            ans = mod(ans +
                          // last_a * 10^(i+1) * cnt(v.s0)
                          last_a % P * (last_a % P) % P * powP[i + 1] % P * powP[i + 1] % P * v.s0 +
                          //    sigma 2 * last_a * 10^{i+1} * (X...X)
                          //    sigma (X...X) = v.s1
                          2 * last_a % P * powP[i + 1] % P * v.s1 +
                          // sigma (X...X)^2 = v.s2
                          v.s2,
                      P);
        }
        // 右侧分支:选择 x 来填
        if (x == 7) break;
        last_a = last_a * 10 + x;
        last_b += x;
        if (i == 0 && last_a % 7 && last_b % 7)
            ans = mod(ans + nn * nn, P);
    }
    return ans;
}
LL l, r, t;
int main() {
    init();
    cin >> t;
    while (t--) {
        cin >> l >> r;
        cout << mod(dp(r) - dp(l - 1), P) << endl;
    }
    return 0;
}




/*
f[i][j] 表示一共有 i 位,且最高位是 j 的满足题目定义(不要 4 和 62)的数的个数
次高位填 k 的话,k != 4 且 jk != 62
f[i][j] += f[i-1][k]
*/
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;

int f[N][10];
void init() {
    for (int i = 0; i <= 9; i++) f[1][i] = !(i == 4);
    for (int i = 2; i < N; i++) {
        for (int j = 0; j <= 9; j++) {
            if (j == 4) continue;
            for (int k = 0; k <= 9; k++) {
                if (k == 4 || (j == 6 && k == 2)) continue;
                f[i][j] += f[i - 1][k];
            }
        }
    }
}
int dp(int n) {
    if (n == 0) return 1;
    // last 表示上一位填的是什么
    int ans = 0, last = 0;
    vector<int> a;
    while (n) a.push_back(n % 10), n /= 10;
    int len = a.size() - 1;
    for (int i = len; i >= 0; i--) {
        int x = a[i];
        // 左侧分支,填 0~(x-1)
        for (int j = 0; j < x; j++) {
            // 不满足条件
            if (j == 4 || (last == 6 && j == 2)) continue;
            ans += f[i + 1][j];
        }
        // 右侧分支:填 x
        if (x == 4 || (last == 6 && x == 2)) break;
        last = x;
        // 最右侧叶子节点
        if (i == 0) ans++;
    }
    return ans;
}
int l, r;
int main() {
    init();
    while (cin >> l >> r, l, r) {
        cout << dp(r) - dp(l - 1) << endl;
    }
    return 0;
}




/*
f[i][j][k]: 一共有 i 位,且最高位数字是 j,且所有位数字和模 N 结果为 k 的数的个数
枚举次高位可能填的所有 x
f[i][j][k] += f[i-1][x][(k-j) % N]
*/
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int N = 15, M = 110;

int p, f[N][10][M];
// 避免出现取模的结果得到负数
int mod(int x, int y) {
    return (x % y + y) % y;
}
void init() {
    memset(f, 0, sizeof f);
    for (int i = 0; i <= 9; i++) f[1][i][i % p] = 1;
    for (int i = 2; i < N; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k < p; k++) {
                // 枚举最高位填 x
                for (int x = 0; x <= 9; x++) {
                    f[i][j][k] += f[i - 1][x][mod(k - j, p)];
                }
            }
        }
    }
}
int dp(int n) {
    if (n == 0) return 1;
    int ans = 0, last = 0;
    vector<int> num;
    while (n) num.push_back(n % 10), n /= 10;
    int len = num.size() - 1;
    for (int i = len; i >= 0; i--) {
        int x = num[i];
        // 左侧分支:第 i 位放 0~(x-1)
        for (int j = 0; j < x; j++) {
            ans += f[i + 1][j][mod(-last, p)];
        }
        // 右侧分支,直接填 x
        last += x;
        // 最右侧叶子节点
        if (i == 0 && last % p == 0) ans++;
    }
    return ans;
}
int l, r;
int main() {
    while (cin >> l >> r >> p) {
        init();
        cout << dp(r) - dp(l - 1) << endl;
    }
    return 0;
}