我们令$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])$

DP

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

然后我们在询问的时候,就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦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

显然,我们可以发现一个序列是“好的”当且仅当这个序列中的最大值等于这个序列中的其他数之和相加,所以我们只需要保证序列单调递减,同时维护一下这个序列里面元素之和我们就可以$O(1)$判断一个序列是不是“好的”序列($a_1 = Sum - a_1$)

由于题目要求求出去掉哪些元素之后,这个序列会变为一个“好的”序列,所以我们只需要把原序列排序之后再按照刚刚说过的办法$O(1)$判断,只需要吧把原序列之中的$Sum$减去我们需要去掉的元素即可

还有一点需要注意,我们需要特判去掉第一个的情况,这样删去后最大值就是原先的次大数,即$a_2$

上代码QwQ