风年年年

故事的结局重不重要

0%

学习过河卒

发表于 分类于
真有意思，一篇关于过河卒算法的笔记。

本周学习记录

过河卒

最初的设想是遍历下右路径，遇到障碍记录，重新跑，即暴力递归。

但时间复杂度太高了 ——O (2^(n+m))，所以这个想法显然是有问题的，看到右边标签有动态规划数组，就去进修了一下。

动态规划：

如果一个问题可以拆分成有限个子问题，并且可以通过函数递推式来计算出结果，则可使用动态规划来解决。

*动态规划有几个典型特征，最优子结构、 状态转移方程**、边界、重叠子问题 **。*

—— 知乎《看一遍就理解：动态规划详解》

过河卒这道题中，要求求出由原点到提供点的所有路径数，举一个简单的例子：

左图中，假定我要到达的点是 B，则必然经过 A 的右侧点和下方点，这两点的路径数均为一，那么，我到达 B 点的路径数就等于到达 A 右侧点和下方点的路径数之和，因为要去 B 点必然要经过这两点。

右图中，由 A 至 B 的路径数为 6，这同样可以由上题的思想得来，只是需要不断往前推，最终，我们可以总结出一个这样的递推公式：

dp（B） = dp（B~ 上～）+dp (B~ 左～)

… 即通用公式为: dp [i][j] = dp [i-1][j] + dp [i][j-1]

1
2
3
4
5
6
7
8
9
for (int i = 1;i<=n;i++){
    for (int j = 1;j<=m;j++){
        if(control[i][j]==false){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }else{
            dp[i][j]=0;
        }
    }
}

要想跳到第 10 级台阶，要么是先跳到第 9 级，然后再跳 1 级台阶上去；要么是先跳到第 8 级，然后一次迈 2 级台阶上去。

—— 知乎《看一遍就理解：动态规划详解》

但这道题并非如此简单，存在一只马及其一次行动可以跳跃的点作为障碍，卒是不能碰到这些点的，换算到代码中，可以设计这一点的路径数为 0，也就不会影响这一点右和下的点的递推计算。

然后是边界点，例如左下角的点，就只能由上方的点走来，因此只能为 1，右上角同理。

至此，所有的思考工作均已完成，开始代码实现：

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
#include <stdio.h>
#include <math.h>
#include <stdbool.h>

int main(){
    int n,m,x,y;
    scanf("%d %d %d %d",&n,&m,&x,&y);
    long long dp[n+1][m+1];
    bool control[n+1][m+1];
    for (int i =0;i<=n;i++){
        for(int j=0;j<=m;j++){
            control[i][j]=false;
            dp[i][j]=0;
        }
    }
    int houre_control[9][2]={
        {0,0},
        {1, 2}, {1, -2}, {-1, 2}, {-1, -2},
        {2, 1}, {2, -1}, {-2, 1}, {-2, -1}
    };
    for(int k=0;k<9;k++){
        int nx=x+houre_control[k][0];
        int ny=y+houre_control[k][1];
        if(nx>=0&&nx<=n&&ny>=0&&ny<=m){
            control[nx][ny]=true;
        }
    }
    dp[0][0]=control[0][0] ? 0: 1;
    for (int j=1;j<=m;j++){
        if(control[0][j]==false){
            dp[0][j]=dp[0][j-1];
        }
    }

    for (int i=1;i<=n;i++){
        if(control[i][0]==false){
            dp[i][0]=dp[i-1][0];
        }
    }

    for (int i = 1;i<=n;i++){
        for (int j = 1;j<=m;j++){
            if(control[i][j]==false){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }else{
                dp[i][j]=0;
            }
        }
    }
    printf("%lld",dp[n][m]);
    return 0;
}

dp 数组用来存储对应点的路径数，bool 类型的 control 数组用来记录被马控制的点，第一个两层 for 循环遍历初始化这两个数组，定义一个 9×2 的数组存储障碍点由马推导出的变化值，第二个 for 循环将对应控制点计算出并标记进 control 数组为 true，这里额外的 if 语句用于检验这一点是否在边界内。

然后就是递推计算，每一步赋值前均检验此点是否为控制点，若是直接赋值为 0。

将上边界和左边界的点均定义为 1，最后遍历计算剩余点得出结果。

说实话，这题蛮难的，我从开学一直到前天才做出来，期间一直不太理解什么是动态，后来也是看了B站的一个讲解才理解一半并开始做题。

总结，如果没有障碍，从 (0,0) 到 (n,m) 的路径数是一个组合数问题，可以用动态规划求解。存在障碍时，只需要将障碍点的路径数设为 0，表示不可达，然后按照同样的动态规划方法计算。

动态规划状态定义：定义二维数组 dp，dp [i][j] 表示从起点到点 (i,j) 的路径数。

状态转移方程：对于非障碍点 (i,j)，由于卒只能向右或向下移动，所以到达 (i,j) 的路径数等于到达其上方点 (i-1,j) 和左方点 (i,j-1) 的路径数之和。即：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

对于障碍点，dp [i][j] = 0。

边界条件：

  • 起点 (0,0)：如果不是障碍，则 dp [0][0]=1，否则为 0。

  • 第一行（i=0，j>0）：只能从左方来，所以如果 (0,j) 不是障碍，则 dp [0][j]=dp [0][j-1]，否则为 0。

  • 第一列（i>0，j=0）：只能从上方来，所以如果 (i,0) 不是障碍，则 dp [i][0]=dp [i-1][0]，否则为 0。

计算顺序：按照行优先的顺序，从 (0,0) 开始，依次计算每个点的 dp 值，直到终点 (n,m)。

马的控制点：马的位置及其 8 个控制点（马走日字）需要标记为障碍。注意这些点可能超出棋盘范围，需要判断。

快速幂

这个是由一个 io 题启发我去学的，原题找不到了。

快速幂，顾名思义，快速的算出某数的 n 次方

传统计算方法：a^n = a × a × a × … × a（n 次）

时间复杂度：O (n)，当 n 非常大时（如 n=10^9）会非常慢。

我学的是二进制的思想：

例如：n^m 中 m = 15 (10)。十进制的 15 转换为二进制是 1111 (2)。

** 十进制转二进制的转换关系：**15= 2^3×1+2^2×1+2^1×1+2^0×1

n=3 时，可以用这样的幂分解，3^15=3^(2^3+2^2+2^1+2^0)=3^(2^3)⋅3^(2^2)⋅3^(2^1)⋅3^(2^0)

一个关键的公式：n^(2^(m−1)) × n^(2^(m−1)) = n^(2^m)

由这个公式，我们可以通过小的次方数，累乘得到更高次方的数，代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
long long int quik_power(int base, int minumber)
{
    long long int result = 1;
    while (minumber > 0)
    {
        if (minumber & 1)
            result *= base;
        base *= base;
        minumber >>= 1;
    }
    return result;
}

铺地毯

这题蛮好做的其实，但是我最开始的思路是二维数组暴力枚举，也是成功超时，然后去学了学思路，发现这题的思路贼简单，初始化一个巨大的二维数组并赋值为 0，输入每个地毯的范围，接着将输入的坐标逆序查询是否在由 n—1 地毯的范围内，如果无结果就输出-1，查询到直接 break 输出对应地毯。

代码实现：

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
#include <stdio.h>
#include <math.h>

int main(){
    int n;
    scanf("%d",&n);
    int a[n+1],b[n+1],g[n+1],k[n+1];
    for(int i = 1;i<=n;i++){
        scanf("%d %d %d %d",&a[i],&b[i],&g[i],&k[i]);
    }
    int x,y,temp=0;
    scanf("%d %d",&x,&y);
    for (int i = n;i>=1;i--){
        if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]){
            printf("%d",i);
            temp++;
            break;
        }
    }
    if(temp==0){
        printf("-1");
    }
    return 0;
}