本篇题解讲述的为非完美做法，但是可以骗到96分

说实话我在网上找了好久结果都是这个$O(n^2)$的非正解树型$DP$

听说有个$O(N)​$的正解在某篇论文里？

算了反正我也看不懂

所以我接下来就介绍一下这个$O(n^2)$的树型$DP$吧QwQ

顺手丢一下我学习的这篇blog​吧

简单递归

首先我们如果要消灭一段区间$[l, r]$，我们可以有三种选择：

• 如果$[l, r]​$区间内没人，那么直接花费$A​$的代价将这段摧毁
• 如果$r > l​$（即这段区间长度$>2​$），可以选择把它切割成$\left[ l, \lfloor \frac{l + r}2\rfloor\right]​$ $\left[\lceil \frac{l + r}2\rceil, r\right]​$两段
• 如果$[l, r]$区间内有人，直接花费$b (r - l + 1)x$的代价将其摧毁。

题外话

我本来自己想到的的做法是跟别的大多数题解一样的

但是$LJC00118$大仙跟我讲了他的做法，据说常数更小一些，于是我就过来发（水）题（社）解（区）了（分）。

题外话

我们模拟赛考了这题。

模拟赛大概还剩一个半小时的时候，我想出了这题，并且说

“要是我这没A掉，我就不交卷了”

于是我就没有A掉。

其实赛后半个小时左右就调出来了（我才不会告诉你我比赛的时候那个建模是有锅的呢）

其实我很想吐槽这题

我比赛的时候疯狂$\text{WA on test 16}​$

然后死活找不出来哪儿错了

我觉得我数组开小了

于是我开到$MLE$都没有过掉

最后一看

被一个n = 2的点卡掉了……

才出4题，罚时爆炸，上黄失败，掉分哭唧唧

我们令$fa[i]$为$i$直接连向的点

那么显然，$fa[i] \in \{a_{i, 1}, a_{i, 2}\}​$

假设$a_{i, 1}$为$fa[i]$，那么$a_{2, i} \in \{ a_{fa[i], 1}, a_{fa[i], 2} \}$

否则肯定有$a_{2, i} \not\in \{ a_{fa[i], 1}, a_{fa[i], 2} \}$

所以，如果有$a_{2, i} \in \{ a_{fa[i], 1}, a_{fa[i], 2} \}$，那么$fa[i] = a_{i, 1}$，否则$fa[i] = a_{i, 2}$

一道有点套路化的网格图上$DP$QwQ

我们用$f_{min}[i][j][0]$表示线头在$(i, j)$这个点的时候，线的方向朝__下__，我们能取到的最小的拐弯次数、用$f_{min}[i][j][1]$表示线头在$(i, j)$这个点的时候，显得方向朝__右__，能够取到的最小的拐弯次数

同理，我们用$f_{max}[i][j][0]$与$f_{max}[i][j][1]$表示线头在$(i, j)$位置是线朝下和朝右能够取到的最大的拐弯次数。

接下来，对于有障碍的点，我们直接不处理

显然，答案分别为$\max(f_{max}[n][m][0], f_{max}[n][m][1])$与$\min(f_{min}[n][m][0], f_{min}[n][m][1])$

对于这题，看到字符串匹配，第一反应想到字符串hash，同时看到$len \leq 8 $ ，考虑对于先给出的$n$个字符串，$O(len^2)$枚举它的子串，将其加入$map$中，但是要注意如果一个然后对于每个字符串，我们都统计一下它最后一次出现在哪里（于是就可以顺便判一下重）

然后我们在询问的时候，就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ

我感觉思路隔壁题解给的不够清楚啊……

感觉我无法直接理解隔壁dalao的“正经的图上神搜”啊……

那本蒟蒻就补充一下吧QwQ

第一篇题解

我们都知道$lcm(a, b) = \frac{a * b}{\gcd(a, b)}$

∴ $\frac{lcm(a, b)}{a} = \frac{\frac{a * b}{\gcd(a, b)}}{a} = \frac{b}{\gcd(a, b)}$

题目的意思就被我们转化成了求$\frac{b}{\gcd(a, b)}$的种类数

又∵b是一个确定的数

∴$\frac{b}{\gcd(a, b)}$的种类数就等于$\gcd(a, b)$的种类数

由于$a$的范围在$[1, 10^{18}]$范围内，所以$\gcd(a, b)$的种类数就等于b的因数个数。

因数个数就可以$O(\sqrt n)$求辣QwQ