#A. 图灵初赛练习6(普及组)

    客观题

图灵初赛练习6(普及组)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

阅读程序(12分)

1	#include<iostream>
2	using namespace std;
3	int n;
4	int a[100];
5	
6	int main() {
7	    scanf("%d", &n);
8	    for (int i = 1; i <= n; ++i)
9	        scanf("%d", &a[i]);
10	    int ans = 1;
11	    for (int i = 1; i <= n; ++i) {
12	        if (i > 1 && a[i] < a[i - 1])
13	            ans = i;
14	        while (ans < n && a[i] >= a[ans + 1])
15	            ++ans;
16	        printf("%d\n", ans);
17	    }
18	    return 0;
19	} 

判断题

  1. 1616 行输出 ansans 时,ansans 的值一定大于 ii 。(){{ select(1) }}
  • 正确
  • 错误
  1. 程序输出的 ansans 小于等于 nn 。(){{ select(2) }}
  • 正确
  • 错误
  1. 若将第 1212 行的"<"改为"!=",程序输出的结果不会改变。() {{ select(3) }}
  • 正确
  • 错误
  1. 当程序执行到第 1616 行时,若 ansi>2ans-i>2,则a[i+1]a[i]a[i+1] \le a[i]。() {{ select(4) }}
  • 正确
  • 错误

选择题

  1. 若输入的a数组是一个严格单调递增的数列,此程序的时间复杂度是{{ select(5) }}。
  • O(logn)O(logn)
  • O(n2)O(n^2)
  • O(nlogn)O(nlogn)
  • O(n)O(n)
  1. 最坏情况下,此程序的时间复杂度是{{ select(6) }}。
  • O(n2)O(n^2)
  • O(logn)O(logn)
  • O(n)O(n)
  • O(nlogn)O(nlogn)

完善程序(15分)

nn 条绳子,每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割,但不可以连接。现在要从这些绳子中切割出至少 mm 条长度相同的绳段,求绳段的最大长度是多少。

输入:第一行是一个不超过 100100 的正整数 nn,第二行是 nn 个不超过 10610^6 的正整数,表示每条绳子的长度,第三行是一个不超过 10810^8 的正整数 mm

输出:绳段的最大长度,若无法切割,输出 Failed

1	#include<iostream>
2	using namespace std;
3	int n, m, i, lbound, ubound, mid, count;
4	int len[100]; // 绳子长度
5	int main()
6	{
7	    cin >> n;
8	    count = 0;
9	    for (i = 0; i < n; i++)
10	    {
11	        cin >> len[i];
12	        ①;
13	    }
14	    cin >> m;
15	    if (②)
16	    {
17	        cout << "Failed" << endl;
18	        return 0;
19	    }
20	    lbound = 1;
21	    ubound = 10000000;
22	    while (③)
23	    {
24	        mid = (lbound + ubound) / 2;
25	        count = 0;
26	        for (i = 0; i < n; i++)
27	            ④;
28	        if (count < m) 
29	            ubound = mid;
30	        else
31	            lbound = mid + 1;
32	    }
33	    cout << ⑤ << endl;
34	    return 0;
35	}
  1. ① 处应填( ){{ select(7) }}
  • count = min(count,len[i])
  • count = max(count,len[i])
  • count = count + len[i]
  • count = count + 1
  1. ② 处应填( ){{ select(8) }}
  • count > m
  • count < m
  • count > n
  • count < n
  1. ③ 处应填( ){{ select(9) }}
  • lbound < ubound
  • lbound <= ubound
  • lbound > ubound
  • lbound >= ubound
  1. ④ 处应填( ){{ select(10) }}
  • count = count + len[i]
  • count = (count + len[i] + 1) / 2
  • count = count + len[i] / mid
  • count = count + len[i] / mid + 1
  1. ⑤ 处应填( ){{ select(11) }}
  • lbound
  • ubound
  • ubound - 1
  • lbound - 1

2024年8月2日 初赛练习(6)【普及组】

未参加
状态
已结束
规则
OI
题目
1
开始于
2024-8-2 17:00
结束于
2024-8-5 0:00
持续时间
0.7 小时
主持人
参赛人数
42