【郁闷篇】冲刺CSP-J/S第2轮倒计时3天:策略有时比能力更重要

2023-10-24 16:47:51 浏览数 (2)

周六模拟赛

上周六有一场模拟赛,比赛完了,我电话跟小码匠沟通:比赛打的怎么样?

小码匠说:前三道题都比较简单,不到一小时就完事了,打得都是正解。最后一道题是DP,搞了两个小时,递推式推的有问题,估计要挂。

当时打完电话时我就感觉估计要凉,这熊孩子,又陷进去了。

出分

后来出分时,两道AC,一道挂了,只有30分,那道DP的题也挂了。

先说30分

题目描述

一家弹珠厂向一所幼儿园捐赠了一些弹珠,弹珠一共有 M 种颜色,每颗弹珠都有一种颜色。老师需要把所有的弹珠分给 N 个孩子。每个孩子得到的所有弹珠都必须是相同的颜色,而且可以有一些孩子一颗弹珠也没得到。

我们把嫉妒值定义为分给一个孩子最多的弹珠数量。请你帮助老师分弹珠,使得嫉妒值最小

例如,如果有 4 个红色的弹珠(RRRR)和 7 个蓝色的弹珠(BBBBBBB),要分给 5 个孩子,那么我们可以这样划分:RR,RR,BB,BB,BBB。这样分的嫉妒值为 3,是最小的。

输入格式

输入共 M 1 行。

第一行包含两个正整数 N,M,分别表示孩子数和弹珠的颜色总数。

接下来 M 行的第 i 行包含一个正整数 x(x∈[1,]),表示有 x 个颜色为 i 的弹珠。

输出格式

输出一行一个整数,表示最小的嫉妒值。

输入输出样例

输入 #1复制

代码语言:javascript复制
5 2
7
4

输出 #1复制

代码语言:javascript复制
3

输入 #2复制

代码语言:javascript复制
7 5
7
1
7
4
4

输出 #2复制

代码语言:javascript复制
4
说明/提示
【数据范围】

对于 100% 的数据,保证 ,,MN。

【说明】

本题分值按 COCI 原题设置,满分 120。

挖坑

小码匠读完这道题,第一感觉这道题得用二分。但她又计算复杂度,当时check函数应该考虑的有问题,结果觉得数据量二分会爆,她就开始思考其他方案,后来就有了这个华丽丽的30分思路。

懊恼不已

后来翻看题解,发现自己思路和题解一致,错估了时间复杂度,结果就凉凉了,小孩很懊恼的。

再说那道DP

一做题就较牛劲,这个对于参加信息学的孩子非常致命。

不要死磕一道题,不会或者思路一直有问题,就要及时止损,别想正解了。

赶紧打暴力,一分一档,通常打个暴力出来至少有10分以上。

回到正题

再有3天就要复赛,要多总结复赛策略,应对考试中可能出现的问题。

比如这场比赛,我在跟小码匠复盘时说:

这场比赛是入门的模拟赛,一般最后2道题会相对难,而得30分的题目是第二道题,通常是普及-级别难度的题。

通常考察的算法会比较单一,你的第一印象是二分,大概率就是二分。

如果是最后一题,有可能是二分加其他算法组合,但第二道这种可能性很小,相信自己的第一感觉就对了。

把简单的事做复杂了,自然很容易吃亏。

再说DP,死磕是不明智的,要及时调整策略。

好的策略=80%成功

对于复赛,要时刻保持冷静的头脑,策略往往在复赛中效果更好。

0 人点赞