当前位置:首页 > 比赛题解 > 正文
GDOI2022普及组Day2题解
397+

A点指兵兵:推公式或者找规律

最终位置:1 + (n-1) % i,无解位置:1、2、i(0)
对于$1 + (n-1) \mod i \equiv 1$,即$ (n-1) \mod i \equiv 0$,i是n-1的约数即可。
对于$1 + (n-1) \mod i \equiv 2$,即$ (n-1) \mod i \equiv 1$,i是n-2的约数即可,因为n-1减去余数是i的倍数。
对于$1 + (n-1) \mod i \equiv 0$,即$ (n-1) \mod i \equiv -1$,i是n的约数即可,因为n-1减去余数是i的倍数。

B网页浏览:贪心

每个网页至少打开一次、关闭一次,关闭也可以转换为打开新的网页;只有叶子结点无法转换,需要2次操作,其他只需要1次操作。

C教室的电子钟:模拟

将日期和时间看成一个高精度数,秒位加1,进位则分位加1……如果加到比最大值还大,那么从头开始。输出时间验证是否正确,正确才进行下一步的计算。

如何判断两个日期间的耗电量?逐位比较即可。我们可以预处理出每个数字的状态,用二进制表示,异或可得他们的变化情况,其中的1的数量即耗电量。

暴力70分,检查无误后记忆化。

满分做法:加入记忆化。显然,每一天的时分秒耗电量是固定的,我们可以预处理出来,下次只要时分秒跑到相同的时候,就可以一天一天跑。

D机器人:最短路

首先要看成是子序列问题,失灵和遇到障碍物,相当于这个字符不用,问题就转换成用字符串的子序列让机器人走出去。

我们可以贪心,用尽量少的字符走出去,bfs出每个位置需要的最少字符是多少;边权可以用序列自动机预处理。

报歉!评论已关闭.