普及组CSP-J第三套模拟试题模拟题附答案.pdfVIP

未知驱动探索，专注成就专业

CSP-J第三套模拟试题模拟题附答案

题目一

小明有一条长度为n的绳子。他可以剪掉其中的一段绳子，然后把绳子连接起

来。请问小明最多可以得到多长的绳子？

输入格式

输入包含一个整数n。

输出格式

输出一个整数，表示小明最多可以得到的绳子的长度。

样例输入1

12

样例输出1

36

样例输入2

10

1

未知驱动探索，专注成就专业

样例输出2

25

数据范围

对于40%的数据，1≤n≤10^3。

对于80%的数据，1≤n≤10^5。

对于100%的数据，1≤n≤10^7。

题目解析

本题的核心思路是尽可能剪成长度相等的绳子段。假设绳子的长度是n，我们

首先尽量剪成长度为3的段，然后剩下的绳子长度是n%3。根据剩下的绳子长度，

我们有以下情况：

•如果n%3=0，说明剩下绳子无法再剪成长度为3的段，那么最大

长度即为长度为3的段的个数（n/3）。

•如果n%3=1，说明剩下绳子长度为1，这时我们将最后一段长度

为4的绳子断开得到长度为2的两段。

•如果n%3=2，说明剩下绳子长度为2，这时最好的办法是将最后

一段长度为2的绳子断开得到长度为1的两段。

因此，通过以上的分析我们可以得出，当剩下的绳子长度不为0时，最佳策略

是尽量多剪长度为3的段。

2

未知驱动探索，专注成就专业

代码实现

n=int(input())

ifn%3==0:

print((n//3)**3)

elifn%3==1:

print((n//3-1)**3*4)

else:

print((n//3)**3*2)

题目二

给定一个长度为n的整数数组a，数组中的元素可能为正数、负数或零。请计

算出数组a的最大子数组和。

输入格式

第一行包含一个整数n，表示数组的长度。

第二行包含n个整数，表示数组a的元素。

输出格式

输出一个整数，表示数组a的最大子数组和。

样例输入

5

1-2310-472-5

3

未知驱动探索，专注成就专业

样例输出

18

样例输入解释

最大子数组为[3,10,-4,7,2]，和为18。

数据范围

，9≤a_i≤10^9。

对于100%的数据，2≤n≤106-10

题目解析

本题可以使用动态规划的思想来解决。我们定义dp[i]表示以第i个元素结尾的

最大子数组和，那么我们有以下递推关系：

dp[i]=max(a[i],dp[i-1]+a[i])

最后的结果就是所有dp[i]中的最大值。

代码实现

n=int(input())

a=list(map(int,input().split()))

dp=[a[0]]*n

foriinrange(1,n):

dp[i]=max(a[i],dp[i-1]+a[i])

print(max(dp))

4

未知驱动探索，专注成就专业

总结

本文介绍了CSP-J第三套模拟试题