芊爸升学圈 留学 新鲜!刚结束的USACO竞赛2021年1月铜组第3题解析

新鲜!刚结束的USACO竞赛2021年1月铜组第3题解析

USACO 2021年1月竞级赛上周已经结束了,不知道各位参赛的选手们是不是都有顺利竞级呢?不论结果如何,新的一年,我们再接再厉,冲冲冲!!!

下面是最新的1月考题~

题目链接

http://www.usaco.org/index.php?page=viewproblem2&cpid=1085

题目解析

N最大为20,直接枚举的复杂度为O(N*N!),测试点1-5可以采用直接枚举,当N比较大时显然会超时。

采用排列组合和乘法原理可以以较小的复杂度解此题。以样例为例:奶牛的高度可以从高到低排序:4 3 2 1,高度为4的奶牛可以安排到2个高度为4的牛棚,因而有2种可能性。高度为3的奶牛可以安排到2个高度为4的牛棚和1个高度为3的牛棚,因而有3种可能性,但由于可以安排高度为4的奶牛的牛棚一定可以安放高度为3的奶牛,这3种可能性中必定有1个用于安放高度为4的奶牛,则最终可能性为3-1=2。同理,高度为2的奶牛可以安排到4个牛棚中,但其中一个用于安放高度为4的奶牛,一个用于安放高度为3的奶牛,则最终可能性为4-1-1=2。高度为1的奶牛也可以安排到4个牛棚中,但一个用于安放高度4,一个用于安放高度3,一个用于安放高度2,则最终可能性为4-1-1-1=1。最后根据乘法原理,安排4头奶牛的方法数为:2*(3-1)*(4-2)*(4-3)=8。该方法的时间复杂度为O(N^2)。

解法代码

如果改进,时间复杂度还可以优化到O(N*logN),只是本题的N很小,区别不大。代码如下,可以思考下原因。

END

USACO竞赛成本低,收益大,见效快是一个非常值得参与的竞赛哦~

我们拥有强大的教师阵容,教师团队具备多年的USACO和NOIP信息学奥赛教学体系研发经验

冲击2021年蓝桥杯&CSP/NOIP&USACO

20220615174806552

  师资介绍  

宋老师

电子科技大学硕士

竞赛成绩:

荣获ACM-ICPC国际大学生程序设计竞赛亚洲赛区银奖

荣获ACM四川省大学生程序设计竞赛金奖

荣获第十一届蓝桥杯国家二等奖、省一等奖

荣获第十一届蓝桥杯省二等奖

荣获国际大学生程序设计竞赛亚洲邀请赛银奖

荣获四川省邀请赛金奖

教学经验:

长期为学校ACM竞赛队队员进行辅导培训

大学期间,帮助老师教学选修课《程序设计竞赛基础》

曾作为大学承办蓝桥杯的学生负责人

教学风格:

耐心细致,对知识盲区的每个方面力求讲清楚,讲全面

幽默诙谐,注重与同学的互动,提升课堂活跃度

善于用图像具体化抽象的思维,更有利于同学们理解与思维上的提升

▍来源:网络,所有图文仅供学习交流使用,如有侵权烦请告知,我们会立即删除。

本文来自网络,不代表芊爸升学圈立场,转载请注明出处:https://www.wish188.com/2021/02/01/10335.html

作者: 芊爸

芊爸陪你升学。
上一篇
下一篇

发表回复

您的电子邮箱地址不会被公开。

联系我们

联系我们

在线咨询: QQ交谈

邮箱: hhyyy9@qq.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

返回顶部