发布时间:2023-12-25 09:56:18 编辑:Lisa来源:未知
2023-2024赛季USACO竞赛考试真题及解析新鲜出炉!对于在本赛季参加USACO竞赛的各位同学,12月的月赛考题和解析犀牛国际已为大家解析出来。另外,关于USACO竞赛的课程辅导,有需要的同学可以了解。
就在昨晚,2023年的USACO竞赛首场月季考试结束,小编也是拿到了考试的第一手真题,关于本次USACO竞赛考试铜升银,真题如下:
这个题是个有意思的暴力问题
考虑一个子问题:
一个数初始是1,每一次操作是让它乘2,要求这个数小于等于n,求最多能操作多少次
这个问题的答案比较显然是log2n次
那考虑当前的问题,考虑第一头牛,如果牛比甘蔗矮,那么它吃完甘蔗后高度乘22;如果牛比甘蔗高,此轮吃甘蔗结束。
所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。
时间复杂度:O(nlog2n)
知识点:暴力,时间复杂度分析
首先我们可以根据输入计算出1的扩散时间最长是多少(时间越长需要的初始点就越少)
注意边界和中间的计算方式不同,中间扩散的结果是1,3,5,...,2*n-1,而边界是1,2,3,...,n$因为边界可以放在最角落开始)
计算出最长扩散时间max_time后我们就可以对每一段连续为1计算初始最少需要放几个1 : len = 2*max_time+1 (len代表连续1个数)
最终将答案相加即可
复杂度:O(n)
知识点:贪心,边界条件判断
考虑根据最终的排序结果来确定有多少条件,容易发现其实只有$n-1$个有效的不等式,即第1个小于第2个,第2个小于第3个,...
根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围
最终对于所有不等式结果求出交集,如果不为空就输出最小值,否则输出-1
时间复杂度:O(n)
知识点:简单数学
犀牛USACO竞赛真题解析
在线咨询详情
虽然数学和编程有本质上的区别,但之间却存在着千丝万缕的联系:
数学可以帮助我们按步骤完成计算,而编程帮助我们实现每个计算步骤。
编程的基础是建立在数学之上。例如,树、图、堆等数据结构以及贪心算法、动态规划等算法都需要应用数学思维和方法。
USACO竞赛涉及问题可以归类为应用数学或运筹学。
能力:在for循环中经常用到,类似小学数学的知识。
数字的加减乘除:每种编程语言都内置支持,不需要手动计算。
数和模运算:偶尔会用到。
集合运算:交集、并集、差集,编程中用到的不多。
布尔运算:AND、OR等逻辑运算。
各种进制:二进制、十进制、十六进制等。
犀牛USACO竞赛课程辅导
犀牛国际USACO竞赛拥有专业的导师团队,为学生提供更专业的课程辅导。USACO竞赛课程包含了铜冲银,银金冲以及冲铂金的课程内容,4-6人小班授课,也可一对一精品授课,支持中英和全英两种授课语言。
犀牛USACO竞赛课程辅导
在线咨询详情
犀牛国际培训课程开设了精品小班、一对一等多种班型,家长和同学们可任意选择,线下+线上同步授课,在上海、北京、南京、苏州、无锡、杭州、广州、深圳、青岛、合肥、武汉、济南、成都等地均设有线下校区。提升各科国际竞赛、国际课程、国际学校择校与留学服务,具体了解可点击在线咨询!
犀牛USACO竞赛课程辅导
在线咨询详情
AP03-08
小托福04-03
美国留学04-05
微信咨询