题外话

我们模拟赛考了这题。

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

“要是我这没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])$

DP

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

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

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

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

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

上代码QwQ