CSP-J 2023 入门级 第一轮 阅读程序（2）

【题目】

CSP-J 2023 入门级 第一轮 阅读程序（2）

#include 
#include 
#include 
using namespace std;
int f(string x, string y) {
    int m = x.size();
    int n = y.size();
    vector<vector<int>> v(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                v[i][j] = v[i - 1][j - 1] + 1;
            } else {
                v[i][j] = max(v[i - 1][j], v[i][j - 1]);
            }
        }
    }
    return v[m][n];
}
bool g(string x, string y) {
    if (x.size() != y.size()) {
        return false;
    }
    return f(x + x, y) == y.size();
}
int main() {
    string x, y;
    cin >> x >> y;
    cout << g(x, y) << endl;
    return 0;
}
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

判断题
21. f函数的返回值小于等于min(n,m)。（ ）
22. f函数的返回值等于两个输入字符串的最长公共子串的长度。（ ）
23. 当输入两个完全相同的字符串时，g函数的返回值总是true（ ）
单选题
24. 将第19行中的"v[m][n]“替换为"v[n][m]”，那么该程序（ ）
A. 行为不变 B. 只会改变输出 C. 一定非正常退出 D. 可能非正常退出
25. 当输入为"csp-j p-jcs"时，输出为（）
A. “0” B. “1” C. “T” D. “F”
26. 当输入为"csppsc spsccp"时，输出为：（）
A. “T” B. “F” C. “0” D. “1”

【题目考点】

1. 线性动态规划

求最长公共子序列
参考：信息学奥赛一本通 1265：【例9.9】最长公共子序列

2. vector

vector是顺序存储结构的线性表（顺序表），可以将其视为长度可变的数组。
声明vector对象：
vector<数据类型> 对象名;

例：声明保存int类型的顺序表v：vector v;

使用构造函数：
vector<数据类型> 对象名(线性表长度);

例：声明保存int类型的顺序表v，线性表长度为10（即包含v[0]~v[9]共10个元素，初值为0）：vector v(10);

vector<数据类型> 对象名(线性表长度, 元素初值);

例：声明保存int类型的顺序表v，线性表长度为10，元素初值为1。（即包含v[0]~v[9]共10个元素，每个元素初值为1）：vector v(10, 1);

【解题思路】

先看f函数

int f(string x, string y) {
    int m = x.size();
    int n = y.size();
1
2
3

传入两个字符串x和y，m是字符串x的长度（字符个数），n是字符串y的长度。

vector<vector<int>> v(m + 1, vector<int>(n + 1, 0));
1

vector(n + 1, 0)表示声明一个保存int类型变量的vector，长度是n+1（这个vector中有n+1个元素），元素初值为0。
vector>表示外层vector中每个元素都是vector类型的对象。
v(m+1, vector(n+1, 0))表示外层vector对象名是v，长度是m+1，每个元素的初值都是vector(n+1, 0)。
外层顺序表中有m+1个元素，每个元素都是一个保存int类型的长度为n+1的顺序表。
实际这一段就是在使用vector声明一个m+1行n+1列的二维数组v。

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                v[i][j] = v[i - 1][j - 1] + 1;
            } else {
                v[i][j] = max(v[i - 1][j], v[i][j - 1]);
            }
        }
    }
    return v[m][n];
}
1
2
3
4
5
6
7
8
9
10
11

这一段必须先学过线性动规中的求最长公共子序列问题后才可以理解。如对该问题不清楚，详见：(信息学奥赛一本通 1265：【例9.9】最长公共子序列)
这段代码中，v[i][j]是状态，表示x字符串的前i个字符和y字符串的前j个字符的最长公共子序列的长度。
最后返回v[m][n]，即x字符串的前m个字符和y字符串的前n个字符的最长公共子序列的长度。
因此，int f(string x, string y)求的就是x字符串和y字符串的最长公共子序列的长度。

bool g(string x, string y) {
    if (x.size() != y.size()) {
        return false;
    }
    return f(x + x, y) == y.size();
}
1
2
3
4
5
6

g函数传入两个字符串x，y。

• 如果两字符串长度不同，则返回false。
• 如果长度相同，先求x+x（x后面再连接x得到的字符串）和y字符串的最长公共子序列的长度，看该长度是否与y的长度相同。也就是看x+x中是否存在一个子序列是y字符串。（在x+x中顺序选取部分字符（可以跳着选），看能否选出完整的y字符串）。

int main() {
    string x, y;
    cin >> x >> y;
    cout << g(x, y) << endl;
    return 0;
}
1
2
3
4
5
6

主函数，输入x，y字符串，输出x+x是否存在一个子序列是y字符串，如果存在输出1，否则输出0。

判断题
21. f函数的返回值小于等于min(n,m)。（ ）

答：T
f函数求x与y的最长公共子序列的长度，两字符串最长公共子序列的长度不会大于两字符串中任意一个字符串，最长时也就是与两字符串中更短的字符串一样长。该判断正确。

22. f函数的返回值等于两个输入字符串的最长公共子串的长度。（ ）

答：F
f函数的返回值是两个输出字符串的最长公共子序列的长度，而不是最长公共子串。子串是连续元素构成的子序列。子序列可以是不连续的，子串必须是连续的。
比如bcd是abcde的子串，也是子序列。而ace是abcde的子序列，不是子串。

23. 当输入两个完全相同的字符串时，g函数的返回值总是true（ ）

答：T
当x与y相同时，x+x中一定存在子串y（即子串x），子串就是子序列，所以x+x与y的最长公共子序列的长度就是y的长度，g函数返回真。

单选题
24. 将第19行中的"v[m][n]“替换为"v[n][m]”，那么该程序（ ）
A. 行为不变 B. 只会改变输出 C. 一定非正常退出 D. 可能非正常退出

答：D
如果输入的x与y长度不等，那么不会运行到f函数，直接输出0，没有非正常退出。
如果输入的x与y长度相等（空字符串无法输入，字符串长度最小为1），在g函数中调用的是f(x+x, y)，运行到函数内部，int f(string x, string y)，形参x的长度一定是y的二倍。也就是m == 2*n，因此也一定有m > n。
把v当做二维数组，v的第一维的长度是m+1，可以使用的下标范围是0~m。第二维的长度是n+1，可以使用的下标范围是0~n。由于m>n，当取v[n][m]时第二维数组越界，会产生运行时错误。（出现运行时错误时，程序可能会正常退出，也可能非正常退出。我们应该默认它会非正常退出。）

25. 当输入为"csp-j p-jcs"时，输出为（）
    A. “0” B. “1” C. “T” D. “F”

答：B
看csp-jcsp-j中是否存在子序列是p-jcs。
仔细看，是存在的。csp-jcsp-j。
第3到第7字符就是p-jcs。
输出1。（输出布尔值真时，输出1，输出布尔值假时，输出0）

26. 当输入为"csppsc spsccp"时，输出为：（）
    A. “T” B. “F” C. “0” D. “1”

答：D
看csppsccsppsc中是否存在子序列是spsccp。
仔细看，是存在的。csppsccsppsc。
第2，3，5，6，7，9字符连起来就是spsccp。
输出1。（输出布尔值真时，输出1，输出布尔值假时，输出0）

【答案】

21. T
22. F
23. T
24. D
25. B
26. D