【题解】牛客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分做法
根据乘法分配律,可以枚举的一位和的一位,将它们相乘计算贡献。即枚举第位和第位,计算有多少对满足的第位和的第位为,那么答案需要加上的对数乘上。
如果枚举了,那么可以通过将的第位为的对数、和的第位为且的第位为的对数相减得到。对于前者,只留下第位为的边,然后计算连通的点对数即可;对于后者,只留下第位为且第位为的边,然后计算连通的点对数即可。