牛客周赛76题解

比赛地址:牛客周赛 Round 76
出题人:Silencer76

A 小红出题

注意到 很小,直接 枚举就可以了。
应该有很多同学,非常自信地去写 版本。
然后取模时忘记判断星期六,喜提 Wrong Answer 。
参考代码

B 串串香

对于一个长度大于 的字符串 ,如果它是原串 的子串,
那么 的子串,也是 的子串。
分着分着,你会发现这个 在长度为 时,总是最优的。
于是题目变成统计字符数量,然后输一个 数量最多的字符 就好了。
参考代码

C 小红的gcd

是有性质的,
并且,操作可以执行任意次。
那么我们先让 和其他 操作一遍,然后重复本操作。
执行 次操作之后,所有元素都变成了原数组的
最后对数组求和即可。
参考代码

D 奇偶调整

题目假了,非常抱歉。
hack数据如下:
2 2 1
11 9
正确答案应该为 13 ,而不是 14 。

E 幂次进近

三分+快速幂。
可能很多同学搞错 的上界,看到 的范围是
然后觉得 的上界应该是 ,实则不然。
举例,当 时:



显然这里 优于
所以 的上界至少要是
有的同学不服气,说上面的根号式子不能向上取整吗?
当然不能,因为
向上取整之后变成 直接跟你爆了。
参考代码

F 同位序列

难点在于求
大致有以下几种求法。

  1. :直接枚举大于 的数字 ,直到
  2. :二进制模拟,代码大概 行。
  3. :把二进制位提取出来,然后调用排列函数(比如C++的next_permutation)。
  4. :位运算,代码如下。
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 的变式,通过映射关系去做动态规划。
参考代码

感谢阅读!

全部评论
D题 2 3 1 9 11 这个测试数据,样例代码结果是14,但最小和应该是12,即第一次9-1,然后8->4->2->1,结果是1+11=12
13 回复 分享
发布于 01-12 21:16 上海
所以E题计算幂的时候怎么判断爆了
点赞 回复 分享
发布于 01-12 21:10 北京
为啥没有c++呀
点赞 回复 分享
发布于 01-12 21:18 江西
d题m,k<=1e9,1e9次操作居然能直接过,还以为要优化成直接算出每个数处理完的状态
点赞 回复 分享
发布于 01-12 21:28 北京
请问为什么把k=1的情况注释掉就会出错
点赞 回复 分享
发布于 01-12 21:41 山东
E没有数学的做法吗?
点赞 回复 分享
发布于 01-12 22:08 河北
O(1) nextPermutation太秀了
点赞 回复 分享
发布于 01-12 23:18 河北
为什么c题是2*(n-1)次?
点赞 回复 分享
发布于 01-13 18:54 河南

相关推荐

01-10 19:41
山东大学 C++
投递华为等公司10个岗位
点赞 评论 收藏
分享
评论
7
3
分享

创作者周榜

更多
牛客网
牛客企业服务