基础算法评估

十一期间的CodeStar综合评估于10月8日00:00圆满结束，其中基础算法评估主要目的有三：1.给选手提供一场练习赛，训练选手的代码能力和赛事经验；2.选手可以通过评估了解自己的代码及基础算法水平，横向和其他选手对比，清楚自己的定位；3.匹配学而思编程集训队寒假班次。

本次参加基础算法评估的选手供1166人；420分及以上学员可录取进Z3集训队班次，符合条件的人数共55人；310分及以上学员可录取进Z2集训队班次，符合条件的人数共180人；

10月14日将会按分数从高到低电话通知录取学员，请有意报名学而思集训队的家长保持电话畅通。

错过此次评估的选手可以有以下两个途径进入学而思编程集训队：

1.凭10月29日CSP-J复赛分数匹配对应班次；

2.参加学而思秋季周赛普及奠基组，根据5次周赛成绩匹配对应班次，点击查看周赛详情。

 

01

基础算法评估成绩分析   

参考学员总人数：1166人

参考学员平均分：178.79分(满分600分)

进阶Z3集训队分数线：420

进阶Z2集训队分数线：310

进阶Z3集训队学员人数：55人

进阶Z2集训队学员人数：180人

进阶Z3集训队学员平均分：468.91分(满分600分)

进阶Z2集训队学员平均分：352.14分(满分600分)

进阶集训队学员每题平均分：

基础算法评估高分分数段人数统计：

基础算法评估高分分数段人数统计表
分数段	人数	分数段	人数	分数段	人数
600	2	490	1	390	10
590	0	480	6	380	8
580	2	470	3	370	16
570	0	460	7	360	10
560	1	450	3	350	22
550	0	440	7	340	9
540	0	430	5	330	37
530	0	420	10	320	14
520	3	410	12	310	27
510	1	400	15	300	12
500	4

---

02

基础算法评估试题解析   

T1~T10、选择填空题

【题目答案】

选择填空题答案
题号	1	2	3
答案	B	C	A
题号	4	5	6
答案	D	D	C
题号	7	8	9
答案	A	D	81
题号	10
答案	35

【视频讲解】

，时长21:54

T11、节日礼物

【题目大意】小A在圣诞节前采购巧克力送给朋友们，他想采购尽量多的巧克力，因为每当⼀个朋友收到巧克力，他的快乐值会增加1。小A现在有总金额M元，现在商店有n种巧克力，每种巧克力都有若干件库存。帮他计算最多可以获得多少快乐值（朋友数量无上限）。

【参考难度】入门

【题目解析】典型的贪心问题，目标是采购尽可能多的巧克力，那么就要求买的价格尽可能便宜，因此，我们只需要将价格按照从低到高的顺序排列，然后按顺序购买即可。

注意：在排序时，不能打乱价格和数量的对应关系。

【参考标程1】选择排序

【参考标程2】结构体排序

---

T12、股票价格

【题目大意】皮皮妈妈正在研究一支股票的历史价格波动。对于一段连续时间，她会计算其中的“价格谷”的数量，来衡量这段时间的股价表现。

皮皮妈妈认为，当某一天的股价，同时低于前一天与后一天的股价时，那么这一天的股价就是一个“价格谷”。

现在，对于她所关心的每一段连续时间，你能用程序帮她计算股票在这段时间内有多少个“价格谷”吗？特殊地，一段连续时间的首末两个股价，无论价格多少，均不被视作是这段时间内的“价格谷”。

【参考难度】普及-

【题目解析】首先需要先明白“价格谷”的定义：比前一个小，比后一个大。

70分做法：我们可以按照题目所述，依次遍历 l 到 r 的每一个价格，若满足“价格谷”的定义，则cnt++。时间复杂度为O(m*n)。

100分做法：在70分的基础上，我们会发现，其实只要是价格不变，那么价格谷的位置就是不变的。所以每次查询的时候，我们没有必要重新统计一下，可以使用前缀和记录一下，当前位置之前一共有几个价格谷即可，查询时只需用前缀和做差。时间复杂度为O(n+m)。

【参考标程1】70分代码

【参考标程2】100分代码

---

T13、排队办理

【题目大意】假设一家银行有M个服务窗口。窗户前面有一条黄线，将等候区分为两部分。客户排队等候的规则是：

①在黄线以内的区域，每个窗口前都可以排一对人，每队最多可以排K个⼈，当 个窗口前的队伍都排满时，第M*K+1个顾客以及以后的顾客只能在黄线以外的区域等候。黄线外的所有客户统一排成一个长队。

②每当客户进入黄线以内时，他会选择到当前排队人数最少的窗口处排队等待办理业务。当多个窗口前排队人数最少时，客户会选择窗口编号更小的窗口处排队等待办理业务。

③第i名客户的办理业务时长为Ti。

④最开始的M名客户将于早上08:00被受理业务，记做0时刻。

⑤假设任意窗口办理完成后，下一个客户立刻开始办理，中间的时间忽略。

现在，给定所有客户办理业务所需的时间，请问所有客户办理结束的最晚时间是什么时候。（按分钟计时即可，例如最终结束时间为09:30， 则输出90即可）。

例如，假设银行共有2个服务窗口，每个窗口内可以有2名客户排在黄线以内。

现在共有5名客户等待办理业务，他们的业务时长分别为1,2，6,4,3分钟。

0时刻时，客户1在窗口1接受服务，客户2在窗口2接受服务，客户3在窗口1 前等待，客户4在窗口2前等待，客户5在黄线以外等待。

在1时刻，客户1办完业务，客户5进入黄线以内，并于窗口1前等待。

客户2将于2时刻办完业务，客户4将于6时刻办完业务，客户3将于7时刻办完业务，客户5将于10时刻办完业务。

因此，所有客户办理结束的最晚时间是10。

【参考难度】普及+/提高-

【题目解析】

20分做法：考虑当M=1时，只有一个窗口，那么每个人就按顺序依次排队，最后的办理结束的时间一定是所有时间的总和。

60分做法：考虑M*K≥N，即所有人都可以排到黄线内，不需要等人办完离开。此时，只需要将每个人按照顺序放到数组中即可。最后找到数组中的最大值即可。

100分做法：对于每个窗口来说，如果人满了，下一个进来的人就需要等最先到这的人出去，这就是典型的先入先出。因此，我们可以使用队列来模拟每一个窗口。因为队列无法遍历，所以我们利用一个数组来记录下每个队列的结束时间。

【参考标程1】20分代码

【参考标程2】60分代码

【参考标程3】100分代码

---

T14、交换礼物

【题目大意】小猴邀请朋友一起参加了自己的生日晚会，晚会上小猴收到朋友们的祝福和礼物，由于小猴非常开心，决定给参加晚会的朋友每人赠送一个礼物，所有礼物的价值都是一样的，但是礼物的样式是各不相同的。

参加晚会的朋友一共有n人，编号依次为1~n，小猴给朋友赠送的礼物一共有n个，编号依次为1~n。初始时，编号为i的礼物给编号为i的朋友，即编号为1的礼物给编号为1的朋友，编号为2的礼物给编号为2的朋友，…，编号为n的礼物给编号为n的朋友。

小猴为了活跃晚会的气氛，决定把朋友们之间拿到的礼物进行交换。小猴研究了一种炫酷的交换方法，在交换之前，小猴先需要确定一种交换规则，即给定一个礼物置换序列a1,a2,…,an，具体来说，在进行一次礼物交换时，会把编号为i的朋友拿到的礼物给编号为ai的朋友，即把编号为1的朋友拿到的礼物给编号为a1的朋友，把编号2为的朋友拿到的礼物给编号为a2的朋友，…，把编号为n的朋友拿到的礼物给编号为an的朋友。

小猴想要知道按照上述交换规则，经过k次礼物交换之后，小猴所有的朋友手中分别拿到的礼物编号依次是多少，按照朋友们的编号从小到大依次输出各自最终拿到的礼物编号。

保证序列a1,a2,…,an是一个1~n的排列，即1到n中的每个数字出现且只出现一次。

【参考难度】普及+/提高-

【题目解析】

60分做法：枚举每个礼物的交换过程，确定每个礼物最后交换到哪一个朋友，时间复杂度O(n*k)。

80分做法：可以注意到n远小于k，那么每一个礼物在交换的过程中必定重复多次⾛同一条路径，所以可以单独求出每个礼物的循环节，然后利用求模技巧可以在O(n)的时间内确定一个礼物的最终归属，还需要枚举每个礼物，因此该算法的时间复杂度为O(n2)。

满分做法：基于80分的做法上，可以注意到每次一个礼物在交换的过程中，实际上有其他礼物也一同进⾏交换，且⾛的路径是相同的，可以把这些礼物所⾛的路径记录并标记这些礼物已经确定最终归属，在后⾯遇到已经标记的礼物就不用在确定其归属。所有礼物最多枚举一次，总的时间复杂度为O(n)。

【参考标程1】60分代码

【参考标程2】80分代码

【参考标程3】100分代码

---

添加 家长论坛微信