OIer博客

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]。