西北工业大学NOJ平台：(61-70)长安&有效表达式题解

发表于

长安

题面描述

题面（长安）

注：本题目的描述存在一定问题，具体见此处。

解法1：模拟&深度优先搜索

既然是问动点的所有可能移动情况，那么很容易想到模拟动点的运动过程，用递归实现即可，下面给出伪代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getCaseCnt(int currX, int currY) {
    // 如果不合法，直接否定本条路线
    if (currX > width || currY > height || (currX, currY) == (bannedX, bannedY)) {
        return 0;
    }
    // 如果到达，返回这一条路线
    if (currX == width && currY == height) { return 1; }
    // 要么往上走，要么往右走，绝对不能走出去或碰到禁止点
    int result = 0;
    result += getCaseCnt(currX + 1, currY) + getCaseCnt(currX, currY + 1);
    return result;
}

BEGIN:
readln(width, height, bannedX, bannedY);
while (every of {width, height, bannedX, bannedY} > 0) {
    int result = getCaseCnt(1, 1);
    writeln(result);
    readln(width, height, bannedX, bannedY);
}
END;

这个解法容易想到，但是最糟糕的时候会有2^min(width, height)个递归分支，这导致其复杂度是指数级的，在当前限制条件下不能AC，于是我们应当换一种方案。

解法2：数学&排列组合

从(1, 1)到达(m , n)点，总共需要向右移动m - 1次，向上移动n - 1次，移动m + n - 2次；

所以，不考虑P点的因素，移动方案总数为向右移动与向上移动的排列组合，所有移动方案的数量为：C(m + n - 2, m - 1)或C(m + n - 2, n - 1)。

所有不经过P点 (p, q) 的情况数为移动方案总数减去经过P点的情况数：所以所有合法的移动方案数目为：C(m + n - 2, m - 1) - C(p + q - 2, p - 1) * C(m + n - p - q, m - 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
#include <stdio.h>

/* 从(0, 0)到(m, n)，共需右走m次，上走n次，
故走法总数为组合数(m+n, m)，即result = (m+n)!/m!/n!
走到终点的总数减去经过禁止点的总数即可得到答案
*/

long long getFactorial(long long target) {
    long long result = 1;
    while (target > 1) {
        result *= target; target--;
    }
    return result;
}

long long pointBX = 1, pointBY = 1, pointPX = 1, pointPY = 1;

// 尤其注意！起始点坐标为(1, 1)而非(0, 0)，出的什么破题，这都不说清楚
long long getPathCnt() {
    long long result = 0;
    result += getFactorial(pointBY + pointBX - 2) / getFactorial(pointBY - 1) / getFactorial(pointBX - 1);
    if (pointPY <= pointBY && pointPX <= pointBX) {
        result -= getFactorial(pointPY + pointPX - 2) / getFactorial(pointPY - 1) / getFactorial(pointPX - 1) *
        getFactorial(pointBY - pointPY + pointBX - pointPX) / getFactorial(pointBY - pointPY) / getFactorial(pointBX - pointPX);
    }
    return result;
}

int main() {
    while (pointBX > 0 && pointBY > 0 && pointPX > 0 && pointPY > 0) {
        scanf("%lld%lld%lld%lld", &pointBX, &pointBY, &pointPX, &pointPY);
        if (pointBX > 0 && pointBY > 0 && pointPX > 0 && pointPY > 0) {
            printf("%lld\n", getPathCnt());
        }
    }
    return 0;
}

有效表达式

题面描述

题面（有效表达式）

解法1：模拟&深度优先搜索

同理上题，你也可以通过模拟搜索来遍历所有可能情况，用递归即可实现，以下是伪代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getCaseCnt(int bracketCnt, int vote) {
    // 如果某个右括弧左边部分的左括弧数不大于右括弧数，该情况不合法
    // 如果剩下的括弧全部放右括弧仍然不能追平左括弧数量，不合法
    if (vote > bracketCnt || vote < 0) { return 0; }
    // 能够顺利放下所有括弧，情况++
    if (bracketCnt == 0) { return 1; }
    // 每个括弧要么是左，要么是右
    int result = 0;
    result = getCaseCnt(bracketCnt - 1, vote + 1) + getCaseCnt(bracketCnt - 1, vote - 1);
    return result;
}

BEGIN:
read(bracketPairCnt);
write(getCaseCnt(bracketCnt * 2, 0));
END;

这种方法的时间复杂度为O(2^N)，因为它的目的是模拟所有的情况（有剪枝，可以论证剪枝大致减去了一半的情况），这么大的复杂度肯定也没法AC，我们仍然使用其他方法。

解法2：数学&排列组合

让我们想象一下这样的一个场景，一个动点A处于平面直角坐标系(0, 0)处，现在它要运动到(m, m)处，每次移动它只能向上或向右移动一个单位长度，那么求其运动方案总数？

很明显，看过上一篇题解的老哥都知道答案是C(2m, m)，我们不妨把向上移动对应为左括号，向右移动对应为右括号，这样，动点A的一种移动情况移动实际上就等价于一个由n个左括号和n个右括号组成的长度为2n的括号串。

这样组成的括号串并非每一个都合法，要组成合法的括号串，在任何一个时刻，动点的横坐标都不应当大于纵坐标，这样就保证了括号串的任意前缀左括弧数大于等于右括弧数，括号串也就合法。那么，如何求在这个新的限制条件下，合法的移动总数？

笔记

所有不合法的路径都和y = x - 1有交点，将路径在与该直线交点后方的所有部分按照y = x - 1对称反转，最后落点一定在(m + 1, m - 1)上（容易证明）。所以，所有不合法的路径都对应一条通往(m + 1, m - 1)的路径，故用总数减去不合法路径的数目等于合法路径的数目，答案为C(2m, m) - C(2m, m - 1)，化简得到C(2m, m) / (m + 1)。

注：读者可以尝试对“所有不合法的路径都对应一条通往(m + 1, m - 1)的路径”做必要性证明，即所有通往该点的路径都对应一条不合法的路径。

题解代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>

// 这道题确实有些难度，它涉及到Catalan数列的相关知识
// Catalan数列的第n项可以由以下公式计算：C(2n, n) / (n + 1)
int calculateCatalanNum(int target) {
    int result = 1;
    for (int i = target + 2; i <= 2 * target; i++) { result *= i; }
    for (int i = 1; i <= target; i++) { result /= i; }
    return result;
}

int main() {
    int target; scanf("%d", &target);
    int result = calculateCatalanNum(target);
    printf("%d", result);
    return 0;
}

本题的模型实际上和一个名为Catalan数列的模型等价，有兴趣的读者可以看一看下面的内容：