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

A邹忌讽齐王纳谏:哈希、统计、查找

姓名不超过3个字母,可以看成一个27进制数,该数字不超过100万,统计每个人价值,查找第一个最大值即可。

B数列游戏:前缀和、思维、规律

区间异或和为0,必然出现两个前缀异或和为0,避免出现0,我们可以让他跟后面的数字合并在一起(后面数字前缀和不变),从而消除它。

对于多个前缀异或和相同,我们只需要消除其中一个即可,且保证能消除,故最后就是统计前缀异或和中不同数字的数量,当然不能出现0。

如果全部数字异或和为0,则无解。

C流水线:贪心

答案为最大值乘以数量,拆分并不会变少,只能减小最大值。要让最大值减少,首选最大结点来拆分。

能拆就拆,并判断新的答案会不会更好;如果不能拆,最大值不会变化了,数量增多无益,不再拆!

这样,很自然的就枚举了所有可能的最大值,所以是正确的。

排序做法:由于保证儿子比父亲小,所以从大到小排序后,轮到拆分的结点,其父亲必然已被拆分。

D小学生计数题:筛法、逆元

看到都是公差的倍数,就应该想到筛法翻倍。接着就是用这个序列,找出长度在[x, y]范围的子段,累乘即该段的贡献。

不难发现,同一个公差,每一个等差数列,可以单独处理,断开后就不会一起用了。

问题就转换成n个数,连续[x, y]个的乘积之和是多少。

我们可以枚举开头,乘积用前缀积处理,乘积之和用前缀积的前缀和处理。

对于[1, x..y],可以b[x] + … + b[y],也就是s[y] – s[x-1]。

对于[2, x+1..y+1],就是b[x+1]/b[1] + … + b[y+1]/b[1],除法转换成乘逆元,提取出来即(s[y+1]-s[x]) * t[1]。

报歉!评论已关闭.