其实我很想吐槽这题

我比赛的时候疯狂$\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

Day （不想算）

将RP耗尽在了初赛QwQ

Day 0

教练说这天Openday，随便打游戏，于是上午随手把最大流、费用流、树剖三个听说可能会考的板子给敲了一遍于是就去跟同学颓了一天的LOL

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

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

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

上代码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(N * 8^4)$的优秀复杂度

显然会T飞QwQ

我们考虑再这个基础上进行优化

前言

某天我看到了memset0巨佬怒切17道网络流神仙题的时候，我顿时准备去做做看网络流24题以满足我内心的抖M之魂

于是，我这个蒟蒻看到某道费用流神题的时候，一脸懵逼地看着“费用流”的标签，决心去学一学这玩意