可回退的跳台阶问题 100%

除了上一步或者上两步之外，还有一次回退一步的机会，也可以不回退。求到 n 级台阶处的总方案数。

解答

还是定义 dp[i] 表示到达第i阶的总方案数。

首先考虑不回退的情况，就是直接用原始版爬台阶的结果。
然后考虑回退一步的情况，在可以回退的台阶上回退一步更新后续的所有状态。

第0阶没得回退。
第n阶不可以回退，否则就陷入无穷循环了（跳上去又跳下来，如此重复无数）。

重点来了，如何更新回退后的状态？

image.png

如图，在第i阶回退到第i-1阶，这个操作会导致什么状态改变？

  • dp[i-1] 会增加 dp[i]，因为可以从第i阶到第i-1阶了，所以加上前置状态；
  • dp[i] 也会增加dp[i]，因为dp[i-1]是它的前置状态被改变了；
  • dp[i+1]会增加 dp[i]*2，因为dp[i-1] 和 dp[i] 都是它的前置状态；
  • …依次类推… 其实就是将第i-1阶当做新的起始点，那么从第i-1层到第n层的跳法（不回退）有 dp[n-i+1]种，初始状态 dp[i-1] 增加了 dp[i]，后面全都跟着增加；
  • 所以，dp[n]增加 dp[i]*dp[n-i+1]。

最终，把因一次回退（共n-1种可能）增加的方案数加入答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>

using namespace std;

int main () {
    int n;
    cin >> n;
    vector<int> dp(n+1, 0);
    dp[0] = 0, dp[1] = 1;
    for (int i=2; i<=n; ++i) { // 不回退时
        dp[i] =  dp[i-1] + dp[i-2];
    }
    int res = dp[n];
    for (int i=1; i<n; ++i) { // 考虑回退，有n-1种情况
        res += dp[i] * dp[n-i+1]; // 因为回退产生的新方案 加入答案 
    }
    cout << res << endl;
}

复杂度

  • 时间复杂度 $O(n)$
  • 空间复杂度 $O(n)$

判断矩阵中六个数是否连成一片 100%

给定一个5*5的矩阵，再给6个数，判断这六个数是否能连成一片。

01 02 03 04 05
11 12 13 14 15
21 22 23 24 25
31 32 33 34 35
41 42 43 44 45

如 1 2 3 4 12 13 这六个数可以连成一片。

解答

显然这是一个判断连通性的问题，把六个查询数看成图的结点，给这个图连上边，最后判断这个图是否是一个连通图。直接上并查集：

【数据结构与算法】并查集

https://iunpy.cn/2021/12/10/%E3%80%90%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E3%80%91%E5%B9%B6%E6%9F%A5%E9%9B%86/


重点是对 x 和 y 如何连边，也就是并查集中的 union 操作。以下两个条件满足其一即可：

  • 行相同且列相邻，abs(x-y) == 1
  • 列相同且行相邻，abs(x-y) == 10

代码

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
#include <bits/stdc++.h>

using namespace std;

int parent[100];

int find(int x) // 路径压缩查询
{
    return x == parent[x] ? x : parent[x] = find(parent[x]);
}

int main()
{
    int grid[5][5] = {
        {1, 2, 3, 4, 5},
        {11, 12, 13, 14, 15},
        {21, 22, 23, 24, 25},
        {31, 32, 33, 34, 35},
        {41, 42, 43, 44, 45}};
    vector<int> nums(6);
    parent[nums[0]] = nums[0]；
    while (cin >> nums[0]) { // 多行输入小技巧，先吞一个
        for (int i = 1; i < 6; ++i)
        {
            cin >> nums[i];
            parent[nums[i]] = nums[i]; // 根初始化为自己
        }
        for (int i = 0; i < 6; ++i)
        {
            for (int j = i + 1; j < 6; ++j)
            {
                int diff = abs(nums[i]- nums[j]);
                if (diff == 1 || diff == 10) {
                    int pi = find(nums[i]), pj = find(nums[j]);
                    parent[pj] = pi;
                }
            }
        }
        // 判断这六个数是否有同一个根
        int cnt = 0;
        int root = parent[nums[0]];
        for (auto& num:nums) {
            // FBI WARNING! 这里一定要用find再更新一次
            if (find(num) == root) { 
                cnt ++;
            }
        }
        if (cnt == 6) {
            cout << 1 << endl;;
        } else {
            cout << 0 << endl;;
        }
    }
    return 0;
}

复杂度

  • 时间复杂度 $O(n)$ ： n为输入查询个数。
  • 空间复杂度 $O(1)$

游客集散中心和景点构成图的最短路径问题 75%

  1. 输入 n 和 q，n 是节点个数，q 是操作个数。
  2. 输入 2*n-2 条边，每行三个数 u, v, w，分别是起点、终点、权值：
    • 前 n-1 条构成一个以1号节点为根的生成树；
    • 前 n-1 条边是其他的节点到根节点直接通道。
  3. 输入 q 个操作，每行三个数，第一个是操作类型 op：
    • op == 1，后两个数是 i, w，代表更新第 i 条边的权值为 w；
    • op == 2，后两个数是 u, v，代表查询从 u 到 v 的最短距离。

解答

一看是一个求任意两点间最短距离的问题，不说了，先回忆一下 Floyd 算法，写上去看看。

Floy算法C++实现

https://blog.csdn.net/weixin_42109012/article/details/94217203

… （写了半小时）

过了75%，惊喜啊。但剩下的没过原因不是猜想的超时，而是答案错误。。又想了二十分钟，还是没整明白，算了交卷。。

思考：1号节点可以达到任意节点（部分直达，部分间接），而其他所有节点都可以直接到达1号节点，这个条件应该有用，1号节点是特殊的。但用Floyd算法是一视同仁的。

🥲 To be continued.

代码

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
#include <bits/stdc++.h>

using namespace std;

#define MAXL 9999

void floyd(vector<vector<int> >& g, vector<vector<int> >& dp, int n) {
    vector<vector<int> >path(n+1, vector<int>(n+1, 0));
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            dp[i][j] = g[i][j];
            if (i != j && dp[i][j] < MAXL) {
                path[i][j] = i;
            } else {
                path[i][j] = -1;
            }
        }
    }
    for (int k=1; k<=n; ++k) {
        for (int i=1; i<=n; ++i) {
            for (int j=1; j<=n; ++j) { 
                if (dp[i][j] > dp[i][k] + dp[k][j]) {
                    dp[i][j] = dp[i][k] + dp[k][j];
                    path[i][j] = path[k][j];
                }
            }
        }
    }
}

void update(vector<vector<int> >& g, vector<vector<int> >& edges, vector<vector<int> >& dp, int n, int i, int w) {
    auto& e = edges[i];
    g[e[0]][e[1]] = w;
    floyd(g, dp, n);
}

int main () {
    int n, q;
    cin >> n >> q;
    vector<vector<int> > g(n+1, vector<int>(n+1, MAXL));
    vector<vector<int> > dp(n+1, vector<int>(n+1, MAXL));
    vector<vector<int> > edges(n*2, vector<int>(3));
    for (int i=0; i<2*n-2; ++ i) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i+1] = {u, v, w};
        g[u][v] = min(g[u][v], w);
    }
    floyd(g, dp, n);
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            // update
            update(g, edges, dp, n, x, y);
        } else if (op == 2) {
            // query
            cout << dp[x][y] << endl;
        }
    }
    return 0;
}

复杂度

  • 时间复杂度 $O(q*n^3)$ ，q次操作，执行Floyd算法是 $n^3$。
  • 空间复杂度 $O(n^2)$。