竞赛讨论区 > 【题解】牛客小白月赛26
头像
精神病科黄主任
编辑于 2020-06-21 10:13
+ 关注

【题解】牛客小白月赛26

F题数据弱了,存在精度问题,部分ac代码是可以被卡掉的。详情请见帖子的四五楼,感谢大佬指正。 F数据已更新,欢迎大佬ac。 正确的std已更新在帖子内容最下方。

出题人认为难度大概是这样的(相对于这10题而言):

签到:B、G
简单:E、I、J
中等:A、C、D
较难:F、H

A、牛牛爱学习
答案显然具有单调性,所以考虑二分答案。
对于每次二分check,我们把每本书的知识值从大到小排序后,按顺序把每本书安排到每一天即可,


B、牛牛爱数学
签到。
把右边式子移到左边,化简后是个完全平方式。
图片说明
所以如果a能够整除bc答案就是图片说明
否则就输出-1
看成一元二次方程求解也可以,不过注意过程中会炸LL


C、牛牛种花
考虑对询问离线,将询问和种植的花的位置以x为第一关键词,y为第二关键词升序。
这样保证后面的x不小于前面的x,这样的花只需要统计前面有多少个y小于查询位置的y即可。树状数组维护一下即可。
数据范围较大,注意离散化。


D、失忆药水
根据题意,我们可以把每个人抽象为一个点,如果a知道b的秘密,那么a和b之间连一条有向边。
刚开始每个人都知道其他n-1个人的秘密,那么就是一个完全图,边都是无向边。
所以问题转换为n个点去连边,最多能连多少条边,并且不形成奇数环
我们知道二分图中,不存在奇数环。
把n个点平均分成两部分,每个点只与另一边的点连边,相同部分的点不连边,那么最多能连ans=n / 2 * (n - n / 2)条边。
(为什么均分边最多?两个数总和不变,要想乘积越大,自然是均分)
答案就是n * (n - 1) / 2 - ans 注意开LL


E、牛牛走迷宫
正常的bfs题,按下、左、右、上的顺序走即可


F、牛牛的序列
首先有个很简单的逻辑坑,题中没说a和b的相对大小
奇数+奇数=偶数 偶数+偶数=偶数 奇数+偶数=奇数
所以对答案的影响就是看有区间内有多少个数的因子和为奇数,奇数的个数才对答案有贡献,偶数不会改变答案的奇偶性。
假设b>a 问题转化为求[1,b]、[1,a-1]中有多少个数因子和为奇数
我们考虑算术基本定理。假设这个数为x,容易得到
图片说明
那么根据乘法原理 我们容易得到x的因子和sum为
图片说明
要想sum为奇数,那么需要每一项等比数列和都是奇数。
注意一下2是一个特殊的素数,只有2是偶数形式的素数。
那么对于2而言,2次幂除了1之外都是偶数,所以2的那一项等比数列和一定是奇数。
那么其他项的等比数列和想要为奇数, 素数因子出现的次数必须为偶数,因为奇数的幂次方还是奇数,但因为有加1的缘故,所以需要偶数个(偶数个奇数相加是偶数,因为有1的缘故,整体和就是奇数)

假设x不存在素因子2,显然他是一个奇数平方数。如果要对x进行加倍并且让因子和sum仍然为奇数,那么只能乘二次幂,也就是说乘的倍数必须是二次幂。因为2的那一项等比数列一定为奇数,倘若多了其他素因子,那么最少会让其中一项等比数列和为偶数,偶数 * 奇数 = 偶数,改变了奇偶性。
所以就是求区间的奇数平方数及其二次幂倍数的个数。
那么容易得到,奇平方数乘上二的偶次幂 是一个平方数,也就是sqrt(n).
那么得到了乘上偶次幂的个数后,奇次幂比他大的相邻的偶次幂小一倍,所以乘奇次幂的个数就是sqrt(n/2)。
区间[1,n]的因子和为奇数的个数就是


G、牛牛爱几何
签到,把四个半圆的面积画一下,容易发现阴影部分的面积都重复计算了一次,那么答案就是两个半径为(n / 2)的的圆的面积减去阴影部分的面积。


H、保卫家园
刚开始这题的std写假了。。这里顺便感谢一下验题大佬
问题等价从n个区间中选择若干个区间,要求满足区间重复覆盖的个数不超过k个,最多能选多少个区间
贪心的去选择。维护一个容量为k的集合,集合保存区间的终点。
枚举以i为起点的区间,首先将在集合中的终点<当前点i的都弹出集合。
(因为他们都不会与以i为起点的区间有交区间, 以i为起点的区间大可以代替他们在集合中的位置)
然后枚举所有以i为起点的线段,如果集合容量<k,直接把区间终点加入集合,
否则的话也是先加入进去,不过这时候已经超过了集合的容量了,那么肯定是要弹出一个区间的终点,显然是弹出终点大的,因为占用的区间长,大的这个区间可能可以存好几个小区间,既然弹出去了,那么这个人肯定是不能入伍的,ans++。
那么需要一个可以对数据进行排序,并且能对集合中数据排序后的最大值、最小值进行操作的数据结构。
stl中的set是个很好的选择。可能有终点一模一样,所以需要用多重集合,即multiset。


I、恶魔果实
直接dfs每个数字能变成多少个数就好,或者10^3跑个floyd也行
然后对于要变的数字计算一下每个数字可以变的方案数,根据乘法原理,直接相乘即可


J、牛牛喜欢字符串
简单贪心。
可以得到n / k个字符串,每一行是一个字符串,这样可以得到一个 n / k行 k列的矩阵,对每一列看哪个字母出现的次数最多即可。假设mx为出现最多的字母,答案就是图片说明


std:
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055825
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055848
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055860
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055871
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055876
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44056445
G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055879
H:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055881
I:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055885
J:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44055887

全部评论

(9) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐