初赛程序题专项（四）

二、阅读程序

(1)

01 #include <iostream>
02 #include <vector>
03
04 using namespace std;
05
06 int n, S;
07 vector<int> a;
08
09 int solve(int index, int current_sum) {
10     if (index == n) {
11         if (current_sum == S) {
12             return 1;
13         }
14         return 0;
15     }
16

18     int count1 = solve(index + 1, current_sum);
19
21     int count2 = solve(index + 1, current_sum + a[index]);
22
23     return count1 + count2;
24 }
25
26 int main() {
27     cin >> n >> S;
28     a.resize(n);
29     for (int i = 0; i < n; ++i) {
30         cin >> a[i];
31     }
32     cout << solve(0, 0) << endl;
33     return 0;
34 }

判断题

1. 该程序使用了动态规划的思想来避免重复计算。 ( )
2. 如果输入数组 a 中包含负数，该程序依然能正确运行。 ( )
3. 该程序的时间复杂度为 O(n * S)。 ( )

选择题

4. 该程序解决的问题是 ( )。

   • A. 在数组 a 中寻找和为 S 的最短连续子数组
   • B. 判断是否存在一个子序列，其和为 S
   • C. 计算数组 a 中有多少个不同的子序列，其和为 S
   • D. 在数组 a 中使用最少的元素凑出和 S

5. 若输入为：

   4 5
   1 2 3 4
   

   则输出为 ( )。

   • A. 1
   • B. 2
   • C. 3
   • D. 4

(2)

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04
05 using namespace std;
06
07 vector<int> adj[100];
08 int memo[100];
09
10 int dfs(int u) {
11     if (memo[u] != -1) {
12         return memo[u];
13     }
14
15     int max_len = 0;
16     for (int v : adj[u]) {
17         max_len = max(max_len, dfs(v));
18     }
19
20     return memo[u] = 1 + max_len;
21 }
22
23 int main() {
24     int n, m; 
25     cin >> n >> m;
26     for (int i = 0; i < n; ++i) memo[i] = -1;
27
28     for (int i = 0; i < m; ++i) {
29         int u, v;
30         cin >> u >> v; 
31         adj[u].push_back(v);
32     }
33
34     int longest_path = 0;
35     for (int i = 0; i < n; ++i) {
36         longest_path = max(longest_path, dfs(i));
37     }
38
39     cout << longest_path << endl;
40     return 0;
41 }

判断题

6. memo[u] 存储的是从任意节点到节点 u 的最长路径长度。 ( )
7. 如果输入的图包含环路，该程序可能会陷入无限递归。 ( )
8. 该程序的算法核心是带有记忆化搜索的深度优先遍历。 ( )

选择题

9. 该程序计算的是 ( )。

   • A. 图中节点的数量
   • B. 图中所有路径的平均长度
   • C. 有向无环图中所有节点作为起点的最长路径中的最大值
   • D. 图的连通分量个数

10. 若输入为：

    5 5
    0 1
    0 2
    1 3
    2 3
    3 4
    

    则输出为 ( )。

    • A. 2
    • B. 3
    • C. 4
    • D. 5

(3)

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04
05 const int INF = 1e9;
06
07 using namespace std;
08
09 int main() {
10     int n, amount;
11     cin >> n >> amount;
12     vector<int> coins(n);
13     for (int i = 0; i < n; ++i) {
14         cin >> coins[i];
15     }
16
17     vector<int> dp(amount + 1, INF);
18     dp[0] = 0;
19
20     for (int i = 1; i <= amount; ++i) {
21         for (int j = 0; j < n; ++j) {
22             if (i >= coins[j]) {
23                 dp[i] = min(dp[i], dp[i - coins[j]] + 1);
24             }
25         }
26     }
27
28     if (dp[amount] == INF) {
29         cout << -1 << endl;
30     } else {
31         cout << dp[amount] << endl;
32     }
33
34     return 0;
35 }

判断题

11. dp[i] 的含义是：组成金额 i 的方案总数。 ( )
12. 将第 20 行和第 21 行的两个 for 循环交换顺序，即外层循环遍历硬币，内层循环遍历金额，程序的最终输出结果不会改变。 ( )
13. 如果将第 23 行的 + 1 去掉，程序将计算组成金额 i 的方案中，价值最高的硬币的面值。 ( )

选择题

14. 该程序解决的问题是 ( )。

    • A. 0-1 背包问题
    • B. 完全背包问题
    • C. 找零钱问题（最少硬币数）
    • D. 找零钱问题（方案总数）

15. 若输入为：

    3 6
    1 3 4
    

    则输出为 ( )。

    • A. 1
    • B. 2
    • C. 3
    • D. -1

三、完善程序

(1) 合法括号序列

题目描述: 给定一个只包含 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。

01 #include <iostream>
02 #include <string>
03 #include <stack>
04
05 using namespace std;
06
07 bool isValid(string s) {
08     stack<char> st;
09     for (char c : s) {
10         if (c == '(' || c == '{' || c == '[') {
11             ①;
12         } else {
13             if (②) {
14                 return false;
15             }
16             char top = ③;
17             if ((c == ')' && top != '(') ||
18                 (c == '}' && top != '{') ||
19                 (c == ']' && top != '[')) {
20                 return false;
21             }
22             ④;
23         }
24     }
25     return ⑤;
26 }
27
28 int main() {
29     string line;
30     cin >> line;
31     cout << (isValid(line) ? "true" : "false") << endl;
32     return 0;
33 }

16. ①处应填 ( )，处理左括号。

    • A. st.pop()
    • B. st.push(c)
    • C. return false
    • D. continue

17. ②处应填 ( )，处理遇到右括号但栈为空的情况。

    • A. !st.empty()
    • B. st.size() > 0
    • C. st.empty()
    • D. st.top() == c

18. ③处应填 ( )，获取栈顶元素用于匹配。

    • A. st.front()
    • B. st.back()
    • C. st.top()
    • D. st.peek()

19. ④处应填 ( )，匹配成功后弹出左括号。

    • A. st.push(c)
    • B. st.clear()
    • C. st.erase()
    • D. st.pop()

20. ⑤处应填 ( )，判断遍历结束后是否所有左括号都被匹配。

    • A. true
    • B. st.size() == 0
    • C. st.empty()
    • D. false

(2) 合并区间

题目描述: 给出一个区间的集合，请合并所有重叠的区间。

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04
05 using namespace std;
06
07 int main() {
08     int n;
09     cin >> n;
10     vector<pair<int, int>> intervals(n);
11     for (int i = 0; i < n; ++i) {
12         cin >> intervals[i].first >> intervals[i].second;
13     }
14
15     if (n == 0) return 0;
16
17     sort(intervals.begin(), intervals.end());
18
19     vector<pair<int, int>> merged;
20     merged.push_back(①);
21
22     for (int i = 1; i < n; ++i) {
23         if (intervals[i].first <= ②) {
24             ③ = max(merged.back().second, intervals[i].second);
25         } else {
26             ④;
27         }
28     }
29
30     
31     for (const auto& p : merged) {
32         cout << p.first << " " << p.second << endl;
33     }
34
35     return 0;
36 }

21. ①处应填 ( )，初始化合并后区间的第一个元素。

    • A. {0, 0}
    • B. intervals[n-1]
    • C. intervals[0]
    • D. intervals[1]

22. ②处是判断当前区间与已合并的最后一个区间是否重叠的条件，应填 ( )。

    • A. merged.back().first
    • B. merged.back().second
    • C. intervals[i].second
    • D. intervals[i-1].second

23. ③处是合并区间的操作，应填 ( )。

    • A. merged.back().first
    • B. intervals[i].first
    • C. merged.front().second
    • D. merged.back().second

24. ④处是当区间不重叠时的操作，应填 ( )。

    • A. merged.push_back(intervals[i])
    • B. continue
    • C. merged.pop_back()
    • D. break