浏阳市2023年科技节信息学竞赛小学提高组

一、基础题（40*2=80 分）

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题; 除特殊说明外， 判断题2 分， 选择题 3 分， 共计 40 分

1. （13 分）

1.#include <cstdio>

2.#include <cstring>

3.using namespace std;

4.char st[100];

5.int main() {

6. scanf("%s", st);

7. int n = strlen(st);

8. for (int i = 1; i <= n; ++i) {

9. if (n % i == 0) {

10. char c = st[i - 1];

11. if (c >= 'a')

12. st[i - 1] = c - 'a' + 'A';

13. }

14. }

15. printf("%s", st);

16. return 0;

17.}

2. （13 分）

1.#include <iostream>

2.using namespace std;

3.int n, i, temp, sum, a[100];

4.int main() {

5. cin >> n;

6. for (i = 1; i <= n; i++)

7. cin >> a[i];

8. for (i = 1; i <= n - 1; i++)

9. if (a[i] > a[i + 1]) {

10. temp = a[i];

11. a[i] = a[i + 1];

12. a[i + 1] = temp;

13. }

14. for (i = n; i >= 2; i--)

15. if (a[i] < a[i - 1]) {

16. temp = a[i];

17. a[i] = a[i - 1];

18. a[i - 1] = temp;

19. }

20. sum = 0;

21. for (i = 2; i <= n - 1; i++)

22. sum += a[i];

23. cout << sum / (n - 2) << endl;

24. return 0;

25.}

26.

3、（14分）
1.#include <iostream>
2.using namespace std;
3.const int maxN = 20;
4.int g[maxN][maxN];
5.int f(int n, int m) {
6. if(n <= 1 || m < 2)
7. return 1;
8. if(g[n][m] != -1)
9. return g[n][m];
10. int ans = 0;
11. for(int i = 0; i < m; i += 2)
12. ans += f(n-1, i);
13. g[n][m] = ans;
14. return ans;
15.}
16.int main() {
17. int n, m;
18. cin >> n >> m;
19. for(int i = 0; i < maxN; i++)
20. for(int j = 0; j < maxN; j++)
21. g[i][j] = -1;
22. cout << f(n, m);
23. return 0;
24.}

三、完善程序（单选题，每小题 3 分 ，共计30 分）

2.（装备穿戴问题）有 n 件装备，穿戴第 i 件装备需要玩家的力量值至少为 𝑎𝑖，穿戴该装备后会让玩家的力量值增加 𝑏𝑖。现在请问玩家的初始力量值最小是多少，才能以某种顺序穿戴上所有的装备？
输入：第一行是一个整数 n（1 ≤ 𝑛 ≤ 103）；第二行有 n 个整数，第 i 个 整数表示 𝑎𝑖（0 ≤ 𝑎𝑖 ≤ 109）；第三行有 n 个整数，第 i 个整数表示 𝑏𝑖 （0 ≤ 𝑏𝑖 ≤ 106）。
提示：使用二分+贪心的方法解决这个问题，先对装备按顺序进行排序，然后二分答案，并贪心地进行选择。

试补全程序
01 #include <cstdio>
02 #include <algorithm>
03
04 using namespace std;
05 const int maxn = 1005;
06
07 int n;
08 int a[maxn], b[maxn], c[maxn];
09
10 bool Comp(const int &x, const int &y) {
11 // 你可以简单地认为括号内的内容等价于 (int x, int y)
12 return ①;
13 }
14
15 bool check(int x) {
16 for (int i = 1; i <= n; ++i) {
17 int u = c[i];
18 if (②) {
19 x += b[u];
20 } else {
21 return false;
22 }
23 }
24 return true;
25 }
26
27 int main() {
28 scanf("%d", &n);
29 for (int i = 1; i <= n; ++i) scanf("%d", a + i);
30 for (int i = 1; i <= n; ++i) scanf("%d", b + i);
31 for (int i = 1; i <= n; ++i) c[i] = i;
32 sort(c + 1, c + 1 + n, Comp);
33 int ans = 1145141919;
34 for (int l=1, r=ans, mid=(l+r)/2; ③; mid=(l+r)/2)
35 if (check(mid)) {
36 ans = mid;
37 ④;
38 } else {
39 ⑤;
40 }
41 printf("%d\n", ans);
42 return 0;
43 }