犀牛国际教育旗下指定官方网站~

课程咨询热线 400-656-1680

2023-2024赛季USACO竞赛考试真题及解析新鲜出炉!

发布时间:2023-12-25 09:56:18 编辑:Lisa来源:未知

2023-2024赛季USACO竞赛考试真题及解析新鲜出炉!对于在本赛季参加USACO竞赛的各位同学,12月的月赛考题和解析犀牛国际已为大家解析出来。另外,关于USACO竞赛的课程辅导,有需要的同学可以了解。

USACO竞赛真题展示
-

就在昨晚,2023年的USACO竞赛首场月季考试结束,小编也是拿到了考试的第一手真题,关于本次USACO竞赛考试铜升银,真题如下:

01

图片

01
犀牛解析:
图片

这个题是个有意思的暴力问题

考虑一个子问题:

一个数初始是1,每一次操作是让它乘2,要求这个数小于等于n,求最多能操作多少次

这个问题的答案比较显然是log2n次

那考虑当前的问题,考虑第一头牛,如果牛比甘蔗矮,那么它吃完甘蔗后高度乘22;如果牛比甘蔗高,此轮吃甘蔗结束。

所以这一题直接暴力模拟做到甘蔗被吃完复杂度就是对的。

时间复杂度:O(nlog2n)

知识点:暴力,时间复杂度分析

02

图片

02
犀牛解析
图片

首先我们可以根据输入计算出1的扩散时间最长是多少(时间越长需要的初始点就越少)

注意边界和中间的计算方式不同,中间扩散的结果是1,3,5,...,2*n-1,而边界是1,2,3,...,n$因为边界可以放在最角落开始)

计算出最长扩散时间max_time后我们就可以对每一段连续为1计算初始最少需要放几个1 : len = 2*max_time+1 (len代表连续1个数)

最终将答案相加即可

复杂度:O(n)

知识点:贪心,边界条件判断

03

图片

03
犀牛解析
图片

考虑根据最终的排序结果来确定有多少条件,容易发现其实只有$n-1$个有效的不等式,即第1个小于第2个,第2个小于第3个,...

根据不等式origin_score[i]+increase[i]*t =origin_score[j]+increase[j]*t可以解出t对应的范围

最终对于所有不等式结果求出交集,如果不为空就输出最小值,否则输出-1

时间复杂度:O(n)

知识点:简单数学

 

图片
USACO竞赛代码解析
 
图片
 

犀牛USACO竞赛真题解析

在线咨询详情

 

 

图片
如何学好USACO?数学基础要扎实

 

虽然数学和编程有本质上的区别,但之间却存在着千丝万缕的联系:

数学可以帮助我们按步骤完成计算,而编程帮助我们实现每个计算步骤

编程的基础是建立在数学之上。例如,树、图、堆等数据结构以及贪心算法、动态规划等算法都需要应用数学思维和方法。

USACO竞赛涉及问题可以归类为应用数学或运筹学

 

学好编程需要打好数学基础,包括
 
 
 
 
 
  • 能力:在for循环中经常用到,类似小学数学的知识。

  • 数字的加减乘除:每种编程语言都内置支持,不需要手动计算。

  • 数和模运算:偶尔会用到。

  • 集合运算:交集、并集、差集,编程中用到的不多。

  • 布尔运算:AND、OR等逻辑运算。

  • 各种进制:二进制、十进制、十六进制等。

 
 
 
 
图片

 

 
 
 
 
 
 
 
 
 

犀牛USACO竞赛课程辅导

 
 
 
 
 
 
 
 
 

犀牛国际USACO竞赛拥有专业的导师团队,为学生提供更专业的课程辅导。USACO竞赛课程包含了铜冲银银金冲以及冲铂金的课程内容,4-6人小班授课,也可一对一精品授课,支持中英和全英两种授课语言

 
 
 
犀牛USACO竞赛课程
 
 
 
 
USACO竞赛铜升银培训班
 
 
01
图片
 
USACO竞赛银升金培训班
 
 
02
图片
 
USACO竞赛金升铂金培训班
 
 
03
图片

 

犀牛USACO竞赛课程辅导

在线咨询详情

 

图片

犀牛国际培训课程开设了精品小班、一对一等多种班型,家长和同学们可任意选择,线下+线上同步授课,在上海、北京、南京、苏州、无锡、杭州、广州、深圳、青岛、合肥、武汉、济南、成都等地均设有线下校区。提升各科国际竞赛、国际课程、国际学校择校与留学服务,具体了解可点击在线咨询!

 

犀牛USACO竞赛课程辅导

在线咨询详情

相关标签:
TOP