01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04
05 int a[100005];
06
07 int main() {
08     int n, S;
09     cin >> n >> S;
10     for (int i = 0; i < n; ++i)
11         cin >> a[i];
12
13     int i = 0, j = 0, sum = 0;
14     int ans = n + 1;
15     while (j < n) {
16         sum += a[j];
17         while (sum - a[i] >= S) {
18             sum -= a[i];
19             i++;
20         }
21         if (sum >= S) {
22             ans = min(ans, j - i + 1);
23         }
24         j++;
25     }
26     if (ans == n + 1) cout << 0 << endl;
27     else cout << ans << endl;
28     return 0;
29 }

条件：假设 $S$ 和数组 $a$ 中的元素均为正整数，$n \le 100000$。

---

第 1 题

当不存在满足条件的子数组时，程序输出为 0。
{{ select(1) }}

• 正确
• 错误

---

第 2 题

将 while (sum - a[i] >= S) 改为 while (sum - a[i] > S)，程序对于所有输入都能求出正确的最短子数组长度。
{{ select(2) }}

• 正确
• 错误

---

第 3 题

程序的时间复杂度为 $O(n^2)$。
{{ select(3) }}

• 正确
• 错误

---

第 4 题

当输入为：

5 7
2 3 1 2 4

输出为（ ）
{{ select(4) }}

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

---

第 5 题

如果数组 $a$ 中允许出现负数，该双指针算法是否仍然正确？（ ）
{{ select(5) }}

• A. 正确
• B. 不正确
• C. 不确定
• D. 只对部分负数正确

---

第 6 题

该程序使用的是（ ）
{{ select(6) }}

• A. 动态规划
• B. 贪心
• C. 双指针
• D. 二分

---

01 #include <iostream>
02 #include <algorithm>
03 using namespace std;
04
05 int a[100005];
06 int n, k;
07
08 bool check(int len) {
09     if (len == 0) return true;
10     int cnt = 0;
11     for (int i = 0; i < n; ++i)
12         cnt += a[i] / len;
13     return cnt >= k;
14 }
15
16 int main() {
17     cin >> n >> k;
18     int maxa = 0;
19     for (int i = 0; i <n; ++i) {
20         cin >> a[i];
21         maxa = max(maxa, a[i]);
22     }
23     int l = 1, r = maxa, ans = 0;
24     while (l <= r) {
25         int mid = (l + r) / 2;
26         if (check(mid)) {
27             ans = mid;
28             l = mid + 1;
29         } else {
30             r = mid - 1;
31         }
32     }
33     cout << ans << endl;
34     return 0;
35 }

条件：假设所有木棍长度为正整数，$n \le 100000$，$k \ge 0$。

---

第 7 题

当 $k = 0$ 时，程序输出 maxa。
{{ select(7) }}

• 正确
• 错误

---

第 8 题

将 int mid = (l + r) / 2; 改为 int mid = (l + r + 1) / 2; 可能导致死循环。
{{ select(8) }}

• 正确
• 错误

---

第 9 题

该程序的时间复杂度为 $O(n \log(\text{maxa}))$。
{{ select(9) }}

• 正确
• 错误

---

第 10 题

当输入为：

4 5
10 24 15 8

输出为（ ）
{{ select(10) }}

• A. 8
• B. 9
• C. 10
• D. 7

---

第 11 题

如果输入的 $k$ 大于所有木棍能切出的段数总和，程序输出（ ）
{{ select(11) }}

• A. 0
• B. 1
• C. maxa
• D. 死循环

---

第 12 题

该程序二分的是（ ）
{{ select(12) }}

• A. 数组下标
• B. 木棍长度
• C. 段数
• D. 答案的可能值

---

01 #include <iostream>
02 #include <string>
03 #include <algorithm>
04 using namespace std;
05
06 int dp[1005][1005];
07
08 int main() {
09     string s, t;
10     cin >> s >> t;
11     int n = s.length(), m = t.length();
12     for (int i = 0; i <= n; ++i) dp[i][0] = i;
13     for (int j = 0; j <= m; ++j) dp[0][j] = j;
14     for (int i = 1; i <= n; ++i) {
15         for (int j = 1; j <= m; ++j) {
16             if (s[i - 1] == t[j - 1])
17                 dp[i][j] = dp[i - 1][j - 1];
18             else
19                 dp[i][j] = min(dp[i - 1][j],
20                     min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
21         }
22     }
23     cout << dp[n][m] << endl;
24     return 0;
25 }

条件：字符串长度不超过 1000，仅包含小写字母。

---

第 13 题

当两个字符串完全相同时，程序输出为 0。
{{ select(13) }}

• 正确
• 错误

---

第 14 题

若将替换操作的代价改为 2，插入和删除的代价仍为 1，则上述程序需要修改才能正确计算编辑距离。
{{ select(14) }}

• 正确
• 错误

---

第 15 题

该程序的时间复杂度为 $O(n \times m)$，空间复杂度为 $O(n \times m)$。
{{ select(15) }}

• 正确
• 错误

---

第 16 题

当输入为 abc abd 时，输出为（ ）
{{ select(16) }}

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

---

第 17 题

当输入为 kitten sitting 时，输出为（ ）
{{ select(17) }}

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

---

第 18 题

若将第 16 行的 if (s[i - 1] == t[j - 1]) 改为 if (s[i] == t[j])，程序可能出现的问题是（ ）
{{ select(18) }}

• A. 数组越界
• B. 结果错误
• C. 死循环
• D. 无影响