牛客周赛76题解
比赛地址:牛客周赛 Round 76
出题人:Silencer76
A 小红出题
注意到 很小,直接
枚举就可以了。
应该有很多同学,非常自信地去写 版本。
然后取模时忘记判断星期六,喜提 Wrong Answer 。
参考代码
B 串串香
对于一个长度大于 的字符串
,如果它是原串
的子串,
那么 的子串,也是
的子串。
分着分着,你会发现这个 在长度为
时,总是最优的。
于是题目变成统计字符数量,然后输一个 数量最多的字符 就好了。
参考代码
C 小红的gcd
是有性质的,
。
并且,操作可以执行任意次。
那么我们先让 和其他
操作一遍,然后重复本操作。
执行 次操作之后,所有元素都变成了原数组的
。
最后对数组求和即可。
参考代码
D 奇偶调整
题目假了,非常抱歉。
hack数据如下:
2 2 1
11 9
正确答案应该为 13 ,而不是 14 。
E 幂次进近
三分+快速幂。
可能很多同学搞错 的上界,看到
的范围是
,
然后觉得 的上界应该是
,实则不然。
举例,当 ,
时:
。
。
。
显然这里 优于
。
所以 的上界至少要是
。
有的同学不服气,说上面的根号式子不能向上取整吗?
当然不能,因为 。
向上取整之后变成 ,
直接跟你爆了。
参考代码
F 同位序列
难点在于求 。
大致有以下几种求法。
:直接枚举大于
的数字
,直到
。
:二进制模拟,代码大概
行。
:把二进制位提取出来,然后调用排列函数(比如C++的next_permutation)。
:位运算,代码如下。
long long g(long long x)
{
long long o = x & -x;
long long t = x + o;
long long c = t & -t;
long long m = (c / o >> 1) - 1;
long long ans = t | m;
return ans;
}
public static long g(long x){
long o = x & -x;
long t = x + o;
long c = t & -t;
long m = (c / o >> 1) - 1;
long ans = t | m;
return ans;
}
def g(x:int)->int:
o=x&-x
t=x+o
c=t&-t
m=((c//o)>>1)-1
ans=t|m
return ans
剩下的部分就是 set 乱搞,没什么难度。
思考题其实算是 LIS 的变式,通过映射关系去做动态规划。
参考代码
感谢阅读!