【题解】牛客CSP-J入门组赛前集训营1

A 模法师

30分做法

枚举所有合法的更新答案。

100分做法

对于第一种询问，如果不是质数，那么答案就是的最小质因子；否则答案是。
对于第二种询问，可以证明。在这种情况下。
证明如下：
如果，那么，当时取到最优；
如果：

• 当是偶数时，若，那么；若，那么由于， 。
• 当是奇数时，由于， 。

那么无论如何，都是最优解。
若只会其中一种询问，可获得20分。

B 乘法师

20分做法

枚举所有合法的区间，暴力求区间积判断。为了防止答案超出long long范围，可以：
先检查区间内是否有，如果有就返回，否则一直乘直到答案，即可退出。

50分做法

可以改进20分做法，固定左端点，从左到右枚举右端点并维护区间积。若下一个数为，那么区间积为。否则若区间积已就不更新区间积，否则就将区间积乘上下一个数。

100分做法

当时，所有子区间都合法，答案是。
当时，若区间中至少有一个，那么这个区间所有数的积为，必定不合法；
之后就可以把序列通过划分成若干个区间，之后对于每个区间求解。这样这个问题就转化为序列中所有数都是正整数的问题。
可以发现若左端点固定，随着右端点向右移动，区间内所有数的积一定不会减少。那么可以使用two pointers，来对于每个左端点，求出最靠左的右端点，满足区间内所有数的积。
由于区间内所有数的乘积可能很大，不能通过维护前缀积解决。但是可以发现如果在two pointers时动态维护区间内所有数的积，区间内所有数的积不会超过。那么只需用long long存下即可。

C 数数师

20分做法

枚举所有可能的序列计算答案。

50分做法

可以计算答案的方案数减去答案的方案数。
使用动态规划解决，设为长为，最大后缀和为的方案数。那么转移可以通过枚举下一个数是什么解决。即从到枚举下一个数，若要求的是最大子段和的方案数，那么如果，那么可以转移到。

100分做法

容易发现这个转移可以使用前缀和优化将复杂度优化成。

D 数树师

20分做法

暴力枚举和，对于和可以在树上暴力计算。

50分做法

需要对于树上每一对点求出和，可以采用递推。把这棵树看作以为根，定义为点的深度，定义点的父亲，定义为树上和之间的边的边权。
若要求与，不妨设，那么，。之后就可以在的时间内求出每一对点的和，然后便可以求出答案。

100分做法

根据乘法分配律，可以枚举的一位和的一位，将它们相乘计算贡献。即枚举第位和第位，计算有多少对满足的第位和的第位为，那么答案需要加上的对数乘上。
如果枚举了，那么可以通过将的第位为的对数、和的第位为且的第位为的对数相减得到。对于前者，只留下第位为的边，然后计算连通的点对数即可；对于后者，只留下第位为且第位为的边，然后计算连通的点对数即可。