2021.10.02模拟赛

虎踞龙盘今胜昔，天翻地覆慨而慷。

2021.10.02 模拟赛

A. 旅游路线

旅游路线

最大子矩阵板子题

B. 金色丝线将瞬间一分为二

金色丝线将瞬间一分为二

$x,y$ 独立，考虑分开处理

对于 $x$ 而言，当前插入一个点加的答案 $\Delta = \sum\limits_{j<i}|x_j-x_i|=\sum\limits_{j<i,x_j\le x_i}x_i-x_j+\sum\limits_{j<i,x_j>x_i}x_j-x_i$

树状数组维护这个东西即可

code

C. 神在夏至祭降下了神谕

神在夏至祭降下了神谕

先把 $0$ 记成 $-1$ 会好看一点

朴素DP : $dp_i = \sum \limits_{j<i,|S(j,i)| \le k} dp_{j}$

发现如果我们能迅速求出来 $|S(i,j)|\le k$ 的和即可，考虑开个桶，表示距离当前点 $x$ 的 $S(i,x)$ 的 $dp_k$ 之和

每次加入一个点会把桶整体平移，移动零点的指针即可，统计用树状数组

code

D. number

number

考虑仅有最后五位是有用的，用 $dp_{i,S}$ 表示当前是第 $i$ 位，后五位状态为 $S$

先预处理出来所有不合法的情况，需要记录下 $S$ 如果不合法，那不合法的位置到哪里，因为可能会被截断

然后正常数位DP，每次暴力扫不合法的情况判断即可

比较优秀的解法应该是AC自动机？

code