【题解】牛客小白月赛12
Nowcoder小白月赛12题解
更新:2019.3.11在本文末尾补充了标程链接~
命题:fzszkl
命题:fzszkl
前言
***和华华是出题人的好朋友,然后他们最近(2019年2月份)互相帮助对方脱单了,只剩下了孤单寂寞的出题人一个人,出了这套题祝他们幸福。
(怎么可能哈哈哈哈哈,出题人当然也是有女朋友的。)
第一题
考虑贪心,将所有区间按照左端点排序,从左往右遍历。用一个变量维护我们当前最远可以够到的右端点,然后枚举左端点不超过右端点+1的所有区间,选择右端点最靠右的一个即可。时间复杂度
。
(怎么可能哈哈哈哈哈,出题人当然也是有女朋友的。)
第一题
考虑贪心,将所有区间按照左端点排序,从左往右遍历。用一个变量维护我们当前最远可以够到的右端点,然后枚举左端点不超过右端点+1的所有区间,选择右端点最靠右的一个即可。时间复杂度
第二题
快速幂和快速乘的模板题,时间复杂度
。
快速幂和快速乘的模板题,时间复杂度
第三题
长得很吓人的送分题,注意到
是一个完全积性函数,所以线筛即可。对于素数,直接快速幂。因为素数的个数是
级别的,快速幂的复杂度是
的,所以总时间复杂度是O(N)。
第四题
N=1时答案显然为1,然后针对每一个N(N>1)推式子:
![](https://uploadfiles.nowcoder.com/files/20190309/389613386_1552140366258_equation?tex=%5Csum_%7Bi%3D1%7D%5EN%5Cfrac%7Bi%7D%7B%5Cgcd(i%2CN)%7D%5C%5C%0A%3D%5Csum_%7Bd%7CN%7D%5Cfrac%7B1%7D%7Bd%7D%5Csum_%7Bi%3D1%7D%5EN%5B%5Cgcd(i%2CN)%3D%3Dd%5D%5Ctimes%20i%5C%5C%0A%3D%5Csum_%7Bd%7CN%7D%5Cfrac%7B1%7D%7Bd%7D%5Csum_%7Bi%3D1%7D%5E%5Cfrac%7BN%7D%7Bd%7D%5B%5Cgcd(i%2C%5Cfrac%7BN%7D%7Bd%7D)%3D%3D1%5D%5Ctimes%20i%5Ctimes%20d%5C%5C%0A%3D%5Csum_%7Bd%7CN%7D%5Csum_%7Bi%3D1%7D%5E%5Cfrac%7BN%7D%7Bd%7D%5B%5Cgcd(i%2C%5Cfrac%7BN%7D%7Bd%7D)%3D%3D1%5D%5Ctimes%20i%5C%5C%0A%3D%5Csum_%7Bd%7CN%7D%5Csum_%7Bi%3D1%7D%5Ed%5B%5Cgcd(i%2Cd)%3D%3D1%5D%5Ctimes%20i%5C%5C%0A%3D%5Csum_%7Bd%7CN%7D%5Cphi(d)%5Ctimes%20d%5Cdiv%202)
线筛出欧拉函数以后,直接计算每个d对N的贡献,时间复杂度
。
(还有一种出题人原创的同复杂度但贼难写的莫比乌斯反演弱智做法,就不献丑了。)
第五题
显然可以二分答案,然后枚举每根木棍判断可以裁剪成几段,根据段数的总和判断是否合法。时间复杂度
。
第六题
考虑用树状数组暴力维护,单次修改的复杂度为
。
X越大的时候,复杂度越低,可以直接用树状数组来维护。
X越小的时候,复杂度过高,但是这样的X比较有限,可以开一个桶来维护被修改的总量。
假设界限为S,那么修改复杂度为
,询问复杂度为
,显然
的时候,复杂度最优,为
。
本题还可以使用定期重构解决,将阈值设为
,复杂度一样,实际效率更高。
感谢csyer验题时提出以下做法:
建一个树状数组,第i位记录i的倍数被增加的数的和(只记一次,比如2的倍数就记在2的位置,不需要修改4、6等),设为
。将每次询问看成两端前缀和相减,那么我们要求的就是区间[1,X]的答案,显然就是
。求值时数论分块,使用树状数组进行区间求和即可。修改复杂度
,询问复杂度
,因为数论分块和树状数组的复杂度上界比较松,所以效率比较高。
长得很吓人的送分题,注意到
第四题
N=1时答案显然为1,然后针对每一个N(N>1)推式子:
线筛出欧拉函数以后,直接计算每个d对N的贡献,时间复杂度
(还有一种出题人原创的同复杂度但贼难写的莫比乌斯反演弱智做法,就不献丑了。)
第五题
显然可以二分答案,然后枚举每根木棍判断可以裁剪成几段,根据段数的总和判断是否合法。时间复杂度
第六题
考虑用树状数组暴力维护,单次修改的复杂度为
X越大的时候,复杂度越低,可以直接用树状数组来维护。
X越小的时候,复杂度过高,但是这样的X比较有限,可以开一个桶来维护被修改的总量。
假设界限为S,那么修改复杂度为
本题还可以使用定期重构解决,将阈值设为
感谢csyer验题时提出以下做法:
建一个树状数组,第i位记录i的倍数被增加的数的和(只记一次,比如2的倍数就记在2的位置,不需要修改4、6等),设为
第七题
首先离线操作,建出整棵树的最终状态。对这棵树进行DFS,i号点被搜到的时间记为
考虑到一个操作会影响到一个点有以下两个条件:1、***作的是被影响的点的祖先(或它自己);2、加点的时间早于操作的时间。
所以我们执行修改和询问时直接对整棵子树执行,执行加点操作的时候直接将这个点当前的点权**清零**即可。这样可以消除所有早于它出现的操作的影响。因为只有单点询问,所以本题线段树可用差分树状数组代替。时间复杂度
第八题
感谢csyer提供本题以及题解(因为我不会做):
令
由于
这样递归下去,最终可以得到
所以本题就是求
第九题
因为少了一道图论题,但是出题人图论不好,所以只能随便编了一道tarjan入门题给大家献丑了。
如果删掉某条边后,图仍旧连通,那么这就是一条不必要的边。
反过来说,如果删掉一条边以后,图不连通了,那么这就是一条必要的边。
显然对于一条边,只能是必要或不必要的,所以我们只用求出有几条边是必要的,然后用边的总数去减即可。
必要的边显然就是割边,那我们只用写个tarjan算法求出有几条割边即可。时间复杂度O(N+M)。
第十题
考虑贪心的去匹配,我们希望当前匹配到的位置越靠前越好。所以对于母串每一位都记一下下一次出现某个字符的位置。匹配的时候从第零位(虚根)开始,如果能一直匹配下去就是Yes,否则就是No。这样单次查询的复杂度是
尾声
按照fzsz的习俗,最后祝大家身体健康~
标程链接(不懂怎么搞链接啊,只好放网址了sorry):
A
B
C
D
E
F
G
H
I
J