【题解】牛客小白月赛13 精

A-小A的签到题

显然复制代码并不能AC，实际上要求的是 $f_{n}^{2}-f_{n-1}f_{n+1}$ ，其中 $f_{n}$ 是斐波那契数列的第n项，简单观察或推导可以得出结论： $\forall n \geq 3$ , 若为奇数则为-1，否则就为1。

复杂度： $O(1)$

B-小A的回文串
求n个串的最大回文子串的长度的最大值。枚举每一个变化后的字符串，对每个串跑一遍马拉车即可。

复杂度： $O(n^2)$

C-小A买彩票
考虑买n张彩票的总的方案数是 $4^{n}$ ,然后统计不亏本的方案数，记录 $f[i][j]$ 是买到第i张彩票总获利为j的总方案数。 $f[i][j]=∑f[i-1][j-k],k = 1,2,3,4$ ,最后统计一下不亏本的方案数即可。由于数据规模很小，考虑分别组合枚举有多少个1，2，3，4也可以通过。

复杂度： $O(n^2)$

D-小A的位运算
预处理了一下前缀和后缀，然后枚举那个不选的数就可以了。

复杂度： $O(n)$

E-小A的路径
矩阵表示第一天的时候u到v有多少条路径，然后直接做矩阵k次幂就能得到k天从u到v的路径数，最后统计一下就可以了。

复杂度： $O(n^3logk)$

F-小A的最短路
这张图可以认为是边权全为1的树上增加了一条边权为0的边。

首先先不考虑多出来的一条边，那么dep[u]表示点u的深度，任意两点u，v的最短的距离就是 $dep[u]+dep[v]-2dep[lca(u,v)]$ ,加上这条边后另外一种可能最短的路径就是经过这条边权为0的边，可以建图之后跑一次最短路，每次查询的答案都是 $min(dis[u]+dis[v],dep[u]+dep[v]-2dep[lca(u,v)])$ 。

复杂度： $O((n+q)logn)$

G-小A和小B
这题由于疏忽，一开始的时候题意上误导了大家，在这里向大家道歉。
双向BFS，只要搜索的时候判断当前走过的位置是否被对方走过就可以了。

复杂度： $O(nm)$

H-小A的柱状图
单调栈的模板题，考虑每个位置向两边拓展的最左边的边界和最右边的边界 $L[i],R[i]$ ,分别从左到有和从右到左用一个单调栈维护。处理一下底边的前缀和，扫一遍就可以求出最大值。

复杂度： $O(n)$

I-小A取石子
判断一下小A是否能够取石子，当且仅当小A原本就是必败态并且不能取出任何石子的情形下，小A会输否则小A都会赢。

复杂度： $O(n)$

J-小A的数学题
有很多种做法，一种比较常规的做法是：

$∑_{i=1}^{n}∑_{j=1}^{m}gcd(i,j)^{2}$
= $∑_{d=1}^{min(n,m)}d^{2}(∑_{i=1}^{n}∑_{j=1}^{m}gcd(i,j)=d)$
$记f(d)=(∑_{i=1}^{n}∑_{j=1}^{m}gcd(i,j)=d)$
$有F(t)=∑_{d|t}f(d)=[\frac{n}{d}][\frac{m}{d}]$
$有f(d)=∑_{d|t}\mu(\frac{t}{d})F(t)=∑_{d|t}\mu(\frac{t}{d})[\frac{n}{d}][\frac{m}{d}]$
处理因子直接计算复杂度 $O(nlogn)$ 就可以通过本题