2020年广东工业大学第十届文远知行杯新生程序设计竞赛题解

Problem A 肥猪的钢琴床

假设0^a 表示连续a个0，1^a表示连续a个1

通过观察容易发现答案是0^a 1^b 0^c形式的（当然abc可能为0），此时一个简单的想法就是枚举两个分界点，但事实上在确定了左端点之后右端点是很容易通过预处理找到的，我们可以假设枚举完左端点之后先将左端点左边全部转为0，右端点全部转为1，此时我们想要知道的是0和1出现次数差值最大的右端点，那么我们是需要事先预处理后缀0和1出现次数差的最大值就可以了。

Problem B 拯救小a

本场的签到题~考察新生字符串处理的能力

Problem C 母牛的***赌

显然能开出第n-1枪的是胜者，易证得开出第k枪的玩家一定能开出第k+5枪，算出n<=5的答案即可。

Problem D 中学数学题

本题问题易转换为：n中p因子个数

则p的因子贡献为1；因子贡献为2，以此类推，于是答案可以容易得出：

n/p+n/(p^2)+n/(p^3)

Problem E 枚举求和

k为gcd的因子于是问题为：有多少个i和j都是k的倍数。

于是，答案出来了，直接输出(n/k)*(m/k).

Problem F 合并石子

你只关心在所有合并方案当中，某一堆石子会被合并多少次。

fi表示还剩i堆石子，当前第j堆，在后续所有合并方案中被合并的次数。

转移O（1）

Problem G 排解忧伤

显然，无论以任何顺序入场，怒气值之和都不会改变。

你只要以你喜欢的顺序入场计算就好了。

Problem H 台灯

Problem I 历史

本场的签到题~因为是新生赛所以希望可以通过这一道题目让新生们了解一下acm的历史以及基本规则。

Problem J 母牛烃

显然双键的能量在1至n-1之间。

考虑从高到低依次满足能量，并且每次满足能量时，选取的势力值都是未选择势力值的最值。

可以证明如果每次都遵循这个原则，最后一定能构造出一个合法方案。

定义在一个碳原子上添加双键称为扩展。

对于能量n-1，必定为1与n相连产生。

对于能量n-2，可由1与n-1相连或2与n相连产生。

假设在满足能量时选择前者，则会产生的链；若选择在上扩展，则会导致势力值被忽略，违背了上诉原则。同理若选择了后者，则在上扩展时，同样会违背上诉规则。

因此，归纳可知每次扩展之间必定存在一个公共碳原子，且只要满足存在公共碳原子，则可得到合法方案。

基于此，只需要在主链上扩展时始终满足存在公共碳原子即可得到一组合法方案。

如下图：

Problem K 很基础的模拟题

签到模拟题

Problem L 母牛上柱

签到数学题。两个方向都计算一遍取最小即可。