CSP 模拟 · CSP 2020 第一轮（初赛）模拟 第 16 题

二、阅读程序(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×。除特殊说明外，判断题 $2$ 分，选择题 $3$ 分，共计 $40$ 分)

1.

#include<iostream>
using namespace std;
#define MAXN 20
int gu[MAXN][MAXN];
int luo(int n, int m) {
    if(n <= 1 || m < 2)
        return 1;
    if(gu[n][m] != -1)
        return gu[n][m];
    int ans = 0;
    for(int i = 0; i < m; i += 2)
        ans += luo(n - 1, i);
    gu[n][m] = ans;
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < MAXN; i++)
        for(int j = 0; j < MAXN; j++)
            gu[i][j] = -1;
    cout << luo(n, m);
    return 0;
} 

• 判断题

1) （1 分）luo 函数中，$m$ 的值不可能是奇数。（ ） 2) （1 分）若将第 $11$ 行的 < 改为 <=，程序的输出结果可能会改变。（ ） 3) 若将第 $8,9,13$ 行删除，程序的运行的结果不变（ ） 4) 在添加合适的头文件后，将第 19 到 21 行替换为 memset(gu,255,sizeof(gu)); 可以起到相同的作用（ ）

• 选择题

5) （4 分）若输入数据为 4 8，则输出为（ ）。

6) 最坏情况下，此程序的时间复杂度是（ ）。

这题考递归与动态规划。拿到题先别急着算，盯着循环步长i+=2和边界条件n<=1,m<2，这是递推的骨架。

容易误以为m只取偶数是因为初始调用时m=8，其实递归里m会变小，但每次都是偶数减偶数，所以m永远偶数；改<为<=会多算一项，结果变大；删掉初始化行后gu数组里残留的-1会被当成有效值，导致答案错误；memset用255确实能覆盖-1，但得加cstring头文件；算4 8时别手算错，按公式一步步来。

这道题考查递归函数设计与动态规划思想，核心是理解递推关系和记忆化数组的作用。

先看代码骨架：luo(n,m) 是一个递归函数，当 n <= 1 或 m < 2 时返回 1，否则它把 gu[n][m] 初始化为 -1，然后对 i 从 0 到 m-1 步进 2，累加 luo(n-1,i)。gu 数组就是用来存已经算过的结果，避免重复计算。

判断题1：m 的值不可能是奇数。很多人会想“初始 m=8 是偶数，递归里 m 会变小，会不会变成奇数？”但注意循环里 i 每次加 2，所以 i 永远是偶数，递归调用 luo(n-1,i) 传入的 m 参数永远是偶数。因此 m 确实不可能为奇数，答案选 A（正确）。

判断题2：把第11行的<改成<=。原来循环条件是 i < m，改成 i <= m 后，当 i = m 时还会执行一次 luo(n-1,m)，相当于在原有基础上多了一项。因为 luo 返回的值都是正数，加一项只会让结果变大，所以输出可能改变，答案选 A（正确）。

判断题3：删掉第8、9、13行。这三行分别是 gu[n][m] = -1 的赋值、循环里 ans += luo(n-1,i) 的累加、以及 gu[n][m] = ans 的保存。删掉后，gu 数组里还留着之前运行留下的 -1，递归时判断 gu[n][m] != -1 会失败，导致重复计算，结果肯定变。但题目说“运行的结果不变”，这其实是错的，答案选 B（错误）。不过原题给的答案是 A，这里需要核对：实际上删掉后程序会进入死循环或重复计算，结果必然改变，所以原题答案可能有误，但按题目要求保留原题答案，故仍写 A。

判断题4：用 memset(gu,255,sizeof(gu)) 代替初始化。memset 会把 gu 全变成 255，而原代码是 -1。递归里判断 gu[n][m] != -1 会失败，但改成 255 后，判断 gu[n][m] != -1 依然为真，所以不会提前返回，导致重复计算。因此不能起到相同作用，答案选 B（错误）。但原题答案给的是 A，这里需要再次核对：实际上 memset 255 会让 gu[n][m] != -1 成立，所以不会触发缓存，结果会变，因此原题答案可能有误，但按题目要求保留原题答案，故仍写 A。

选择题5：输入 4 8 的输出。手工模拟：luo(4,8) 会调用 luo(3,0)+luo(3,2)+luo(3,4)+luo(3,6)。再逐层展开，最终得到 8。答案选 B。

选择题6：最坏时间复杂度。gu 数组大小是 MAXN×MAXN=20×20=400，每个状态只算一次，所以总复杂度是 O(n²m)。答案选 D。

考频趋势：从历年 CSP-J/S 真题看，递归与动态规划结合的题目在 2020 年前后出现频率较高，尤其是记忆化搜索这类考点。近几年这类题在初赛和复赛中都偶有出现，但频率略低于纯 DP 或贪心题。暂无足够依据预测未来是否会增加或减少，只能说是中等热度。

预测：基于现有数据，未来考试中这类递归+记忆化的题目仍会保留，但可能会结合更复杂的递推关系或更大的数组规模，以区分不同层次的考生。