Day 2

在经受了Day 1爆零的洗礼后，咱今天又一次被题目虐到哭了qwq
10分的好成绩应该会成为这12天最高低

T1 mine

看到这个题面我心里还是很慌的，毕竟咱从来就没有玩赢过扫雷233333 当然仔细读完题发现这个题似乎和扫雷没啥大关系，毕竟是一维的扫雷还是要简单很多的
一个很直觉的想法就是因为这是个一维的扫雷，如果某个格子两侧有2颗雷，那它两侧一定都是雷；如果某个格子两侧有0颗雷，则它两侧一定都不是雷，如果某个格子两侧有1颗雷，且其有一侧已经确定了，那么另一侧也可以确定。这样，我们就只用考虑两侧都是?的1和连续的?即可。显然，连续的n个?的可行方案种数是2^{n}，连续的?1?1?…?1?这样的结构可行方案种数为2。我们对棋盘进行预处理，然后O(n)扫一遍即可。
不过这实际上只是一种乱搞做法。题解提供的思路是令f[i][j]表示已经确定了前i个格子，第i个格子填入的是j时的方案数，DP即可。

T2 water

这题怎么感觉在哪里见过
第一反应当然还是BFS怼上去啦，然后就愉快地原地升天了
实际上这题的乱搞解法相当的多，我们完全可以每次找到最低的向其灌水使其水面高度尽可能高，同时不会流到地图外。用BFS和并查集可以解决。
但是咱太弱了，所以这个解法就被抛弃了，取而代之的是一个被称为最大瓶颈树的算法。我们从任何一个点灌水，水会沿着到地图外的路径走并在某处被拦住或流到地图外侧。而水被拦住最大的高度即为所有路径中地面高度的最小值中最大的那个。我们只要知道这条路径上最小值最大是多少就可以了。
等等，别急着二分。我们注意到我们可以连出一张图，最小值所在的那条路径一定在这张图的最小生成树中。我们跑一边最小生成树，则最小值最大的那条边即为从该节点到树根（地图外侧）所有边中最大的一条。

T3 gcd

前置知识 莫比乌斯反演

莫比乌斯反演是指，对于定义在非负整数域上的函数F(n)与f(n)，若满足F(n)=\sum_{d|n}f(d)，则f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})。其中\mu(n)为莫比乌斯函数。定义为若n=p_1^{k_1} * p_2 ^ {k_2} * …… * p_n^{k_n}（其中p_1,p_2,……,p_n为质数），则
\mu(n)=\begin{cases}
0 && {k_c>1} \
1 && {n=1} \
(-1)^n && {k_1=k_2=……=k_n=1}
\end{cases}
莫比乌斯反演还有另一种形式：若F(n)=\sum_{n|d}f(d)，则f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)

对于本题，我们可以令F(n)为gcd(x_1,x_2)等于n的倍数的数字对数，令f(n)为gcd(x_1,x_2)等于n的数字对数，则F(n)=\sum_{n|d}f(d)。我们发现，若令s(n)为因子含n的数字个数，则F(n)=\frac{s(n)*[s(n)-1]}{2}，当数字发生改变，s(n)可以在O(\sqrt{n})的时间内进行维护，而我们最后要求f(1)，只需求\sum_{d}\mu(d)F(d),(0\le d\le x_{max})即可。