Nowcoder小白月赛12题解

Nowcoder小白月赛12题解

更新：2019.3.11在本文末尾补充了标程链接~
命题：fzszkl

前言

月月和华华是出题人的好朋友，然后他们最近（2019年2月份）互相帮助对方脱单了，出了这套题祝他们幸福。
第一题
考虑贪心，将所有区间按照左端点排序，从左往右遍历。用一个变量维护我们当前最远可以够到的右端点，然后枚举左端点不超过右端点+1的所有区间，选择右端点最靠右的一个即可。时间复杂度 $O(N\log N)$ 。

第二题
快速幂和快速乘的模板题，时间复杂度 $O(T\log^2A)$ 。

第三题
长得很吓人的送分题，注意到

是一个完全积性函数，所以线筛即可。对于素数，直接快速幂。因为素数的个数是 $O(\frac{N}{\log N})$ 级别的，快速幂的复杂度是 $O(\log N)$ 的，所以总时间复杂度是O(N)。
第四题
N=1时答案显然为1，然后针对每一个N(N>1)推式子：
$\sum_{i=1}^N\frac{i}{\gcd(i,N)}\\ =\sum_{d|N}\frac{1}{d}\sum_{i=1}^N[\gcd(i,N)==d]\times i\\ =\sum_{d|N}\frac{1}{d}\sum_{i=1}^\frac{N}{d}[\gcd(i,\frac{N}{d})==1]\times i\times d\\ =\sum_{d|N}\sum_{i=1}^\frac{N}{d}[\gcd(i,\frac{N}{d})==1]\times i\\ =\sum_{d|N}\sum_{i=1}^d[\gcd(i,d)==1]\times i\\ =\sum_{d|N}\phi(d)\times d\div 2$
线筛出欧拉函数以后，直接计算每个d对N的贡献，时间复杂度 $O(N\ln N)$ 。
（还有一种出题人原创的同复杂度但贼难写的莫比乌斯反演弱智做法，就不献丑了。）
第五题
显然可以二分答案，然后枚举每根木棍判断可以裁剪成几段，根据段数的总和判断是否合法。时间复杂度 $O(N\log A)$ 。
第六题
考虑用树状数组暴力维护，单次修改的复杂度为 $O(\frac{N}{X}\times\log N)$ 。
X越大的时候，复杂度越低，可以直接用树状数组来维护。
X越小的时候，复杂度过高，但是这样的X比较有限，可以开一个桶来维护被修改的总量。
假设界限为S，那么修改复杂度为 $O(\frac{N}{S}\times\log N)$ ，询问复杂度为 $O(S+\log N)$ ，显然 $S=\sqrt{N\log N}$ 的时候，复杂度最优，为 $O(N\sqrt{N\log N})$ 。
本题还可以使用定期重构解决，将阈值设为 $S=\sqrt{N\log N}$ ，复杂度一样，实际效率更高。
感谢csyer验题时提出以下做法：
建一个树状数组，第i位记录i的倍数被增加的数的和（只记一次，比如2的倍数就记在2的位置，不需要修改4、6等），设为 $F_i$ 。将每次询问看成两端前缀和相减，那么我们要求的就是区间[1,X]的答案，显然就是 $\sum_{i=1}^X\lfloor\frac{X}{i}\rfloor\times F_i$ 。求值时数论分块，使用树状数组进行区间求和即可。修改复杂度 $O(\log N)$ ，询问复杂度 $O(\sqrt n\times\log N)$ ，因为数论分块和树状数组的复杂度上界比较松，所以效率比较高。

第七题
首先离线操作，建出整棵树的最终状态。对这棵树进行DFS，i号点被搜到的时间记为 $DFN_i$ 。DFN有一个重要的性质，就是同一棵子树内的节点的DFN总是连续的，所以我们可以用一个线段树按照DFN的顺序来维护所有点的点权。
考虑到一个操作会影响到一个点有以下两个条件：1、***作的是被影响的点的祖先（或它自己）；2、加点的时间早于操作的时间。
所以我们执行修改和询问时直接对整棵子树执行，执行加点操作的时候直接将这个点当前的点权**清零**即可。这样可以消除所有早于它出现的操作的影响。因为只有单点询问，所以本题线段树可用差分树状数组代替。时间复杂度 $O(M\log M)$ 。
第八题
感谢csyer提供本题以及题解（因为我不会做）：

令 $1\le A\le B$ ，我们知道 $\gcd(A,B)=\gcd(A,B-A)$ 。
由于 $F_i=F_{i-1}+F_{i-2}$ ，则 $\gcd(F_N,F_{N+1})=\gcd(F_N,F_{N-1}+F_{N})=\gcd(F_N,F_{N-1})=\gcd(F_{N-1},F_N)$
这样递归下去，最终可以得到 $\gcd(F_N,F_{N+1})=\gcd(F_1,F_2)$ 。
所以本题就是求 $\gcd(A,B)$ ，时间复杂度 $O(\log(\max(A,B)))$ 。
第九题
因为少了一道图论题，但是出题人图论不好，所以只能随便编了一道tarjan入门题给大家献丑了。
如果删掉某条边后，图仍旧连通，那么这就是一条不必要的边。
反过来说，如果删掉一条边以后，图不连通了，那么这就是一条必要的边。
显然对于一条边，只能是必要或不必要的，所以我们只用求出有几条边是必要的，然后用边的总数去减即可。
必要的边显然就是割边，那我们只用写个tarjan算法求出有几条割边即可。时间复杂度O(N+M)。
第十题
考虑贪心的去匹配，我们希望当前匹配到的位置越靠前越好。所以对于母串每一位都记一下下一次出现某个字符的位置。匹配的时候从第零位（虚根）开始，如果能一直匹配下去就是Yes，否则就是No。这样单次查询的复杂度是