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