题解
https://www.bilibili.com/video/BV1Km411m7zZ
赛时公告
- 为增加挑战性，如果通过了 H 题，可以考虑尝试 n \leq 10^5 时本题的做法。如果想要尝试，请浏览 https://www.luogu.com.cn/problem/T446622。但是这一道新的题目不会计入比赛分数计算。
洛谷入门赛 #22 赛前公告
这里是第 22 场洛谷入门赛，也是洛谷网校【入门计划/基础算法计划】2024 年 4 月有奖语言月赛提升赛。
本次比赛中，等级分在 1200 或者以下的用户可以得到评级。超过 1200 分的选手不能获得评级。
洛谷入门赛 #22 将于 2024 年 4 月 19 日 19:00 ~ 21:00 举行，时长 2 小时。
错过比赛可以在入门赛结束后继续参加语言月赛同步赛：https://www.luogu.com.cn/contest/167896
本次比赛共有 8 道试题，分数依次设置为：
500-700-900-1100-1300-1500-1700-2100
选手某题的得分与其通过该题的时间有关。题目难度大致由易到难，但不保证题目难度严格递增。
简而言之，如果选手某次提交某题（原始得分为 S）完成评测的时刻距离比赛开始时的时间间隔为 T（小时），那么选手本次评测的得分为：
\dfrac{1.3}{T+1.3} \cdot S
该函数的图像为（纵轴为得分比率；横轴为比赛进行时间，小时）：
因为舍入误差、测试点分数和评测延迟等原因，得分会有一个比较小的相对误差，但我们保证先完成评测的得分严格不低于后完成评测的得分（原始分相同的情况下）。
选手一道题目的得分是该选手本题所有提交的最高得分。
由于技术原因，所有题目测试数据均分为多个 Subtask。其中 Subtask 0 为样例，不计分；其余 Subtask 为正式测试数据，正常计分。
比赛概况
比赛面向刚完成了算法竞赛入门，基本掌握了语法的选手。题目非常简单，难度一般不高于黄色。你可以在「入门与面试」题库中找到往届语言月赛题目，以对难度进行参考。
比赛的考察范围是：
- 除部分标注出的题目外，考察知识点包含顺序结构、分支结构、循环结构、数组、字符串、简单排序。
- 考察选手理解试题的能力与应对常见易错点的能力。
比赛的目的是：
训练入门选手的代码实现能力、题目理解能力、处理问题能力，并巩固选手的语法知识，对学习过程中的易错点加重强调。
赛时答疑与比赛评价
《洛谷公开比赛参赛规则》节选
- 一个人只能使用一个帐号参加比赛，禁止一个人同时操纵多个帐号参加比赛。
- 对于个人比赛，比赛期间，禁止多人共用同一帐号比赛；禁止用户与他人交流比赛相关内容。
- 比赛期间，选手可以使用自己在比赛开始前编写好的代码；禁止使用他人编写的代码，无论这些代码是否在比赛前编写完成。
注意，严禁开小号/和他人分享答案以达成任何目的，或者直接套用非本人编写的代码。本次比赛将使用洛谷反作弊系统，因为任何原因被反作弊系统发现（包括多人套用同一个互联网公开的代码）、被举报或在抽查代码时发现选手有影响比赛成绩公平性的行为，视情节严重给予取消成绩（得分设为 -1，若计入等级分参赛则按此成绩参与等级分计算）、警告性棕名以及封号等处罚。
广告
欢迎报名洛谷网校课程。优秀学员可以得到 tag 奖励，而且可以有效解决不会写题的问题哦！
冬季学期，入门计划、基础计划和基础-提高衔接计划课程正在报名。各个班级均为一月开班，详细安排请点击下面的对应的链接。
- 入门前期：从零基础开始学习，内容包括编程软件的安装和使用、顺序结构程序设计、变量与常量、分支结构程序设计、循环结构程序设计，同时包含测试与评估。【点击此处查看 >>>】
- 入门后期：适合已经学习完前期或者其他同类课程的学生。后期课程的内容包括数组、字符串、函数、结构体、文件输入输出等进阶 C++ 语言内容，同时包含测试与评估。初步了解算法竞赛思维，为之后学习算法打下坚实的基础。【点击此处查看 >>>】
- 基础前期：已经掌握语言基础。本课程学习内容包括模拟、枚举、排序、贪心、递推、二进制、线性表等。辅以针对性的练习，帮助学生搭建算法知识体系。【点击此处查看 >>>】
- 基础后期：已经学习完前期算法内容。本课程学习内容包括搜索、二分、基础动态规划、集合、栈、队列、图等。辅以针对性的练习，进一步完善算法知识体系。【点击此处查看 >>>】
- 基础-提高衔接计划：针对学完入门级知识和基础算法的学生，通过集中授课、题单作业布置、定期模拟比赛讲评，巩固算法基础和举一反三能力，覆盖 NOI 入门级要求，目标达到 CSP-J 高分能力，为提高级打基础。【点击此处查看 >>>】
如果学习了相关知识点，但不会做题，希望通过练习指导、作业布置、直播答疑、监督与模拟赛评估的方式巩固基础和积累比赛经验的，可以考虑选择训练营课程作为辅助，可以和所有其他课程兼容。
训练营课程随时可以报名，随到随学。
- 信奥入门训练营 前期：学完 C++ 语言顺序结构、分支结构、循环结构，需要巩固这一部分内容的学生。https://class.luogu.com.cn/course/xly2024rm1
- 信奥入门训练营 后期：学完 C++ 语言顺序结构、分支结构、循环结构、数组、字符串、函数、结构体，需要巩固 C++ 基本语法的学生。https://class.luogu.com.cn/course/xly2024rm2
- 基础算法训练营 前期：学完模拟、枚举、排序、基础贪心、高精度、递推、二进制的相关知识，需要巩固这一部分内容的学生。https://class.luogu.com.cn/course/xly2024jc1
- 基础算法训练营 后期：已初步学完 CSP-J 基本算法和数据结构，包括递推、二分、搜索、队列和栈、基础 DP、基础图论等，需要巩固 CSP-J 内容的学生。https://class.luogu.com.cn/course/xly2024jc2
欢迎关注洛谷公众号，及时获取更多洛谷相关动态！
欢迎进入洛谷用户群，及时获取更多洛谷相关动态！