2023 年绍兴市中小学生编程比赛复赛解题报告

发布时间 2023-09-09 07:14:34作者: 御坂夏铃

考试(exam)

按题意判断即可。

散步(walk)

对于 \(90\%\) 的数据,直接模拟。

容易发现 \(x\) 坐标和 \(y\) 坐标都是隔两个改变一次,改变的值跟当前阶段有关,分情况计算一下即可。

恺撒密码(password)

显然字符之间所需加密次数模 \(26\) 余数必须相同,数字之间所需加密次数模 \(10\) 余数必须相同。

数字和字符一起调整,不合法的情况就是两者之差不是 \(\gcd(26,10)=2\) 的倍数,即一奇一偶。合法情况的最少加密次数直接暴力模拟即可得到。

打怪闯关(monster)

能不用金币就不用,当某个时刻必须要用金币时,贪心地选择之前最大的 \(a_i\) 消掉。这个过程用大根堆实现。

吃土豆(potato)

按题意模拟即可。

重排计数(count)

一开始看会觉得很难,但其实是个水题。

首先 \(p\)\(q\) 内部的顺序都是无所谓的,我们可以将 \(q\) 从小到大排序后按顺序填。

这样我们就知道排列中有哪些数能填了,并且当前能填的数之后也一定能填,所以方案数直接乘上能填的个数即可。

序列乘积(product)

考虑 DP,记录当前含有哪些 \(m\) 的质因子以及个数,用 \(m\) 的因数表示。加入一个数时超出数量或者不是 \(m\) 质因子的部分直接去掉,用 \(\gcd\) 即可快速实现。

选择酒店(hotel)

正难则反,以酒店为起点 BFS,每个路口都记录前两个到达它的酒店即可。