信竞学习笔记:[NOIP2023] 双序列拓展
这是本人的课堂笔记。
思路
转化题意,题目实际是在说对于所有 1 \leq i \leq 10^{100},都有 f_i > g_i 或都有 f_i < g_i。考虑每次询问 O(nm) 的纯粹 DP。设 X_1 > Y_1(X_1 < Y_1 时可以交换两个序列),很容易推得 DP 状态转移方程如下:
先考虑特殊性质做法。上面的 DP 过程实际上等价于在一个网格图上从 (1, 1) 开始往 (n, m) 走,可以往下方、右方、右下方移动,且只能经过 X_i > Y_j 的点 (i, j),求是否能够走到 (n, m) 点。
考虑如何优化成线性时间复杂度做法。我们注意到一个很重要的性质:设 x_1 < x_2 且满足转移条件 X_{x_1} > X_{x_2},由于 x_2 行的数值可以从 x_1 行转移过来,所以 x_2 行的合法方案数一定是大于等于 x_1 行的合法方案数的。这就形成了一种后面包含前面的包含关系。
在过程中记录 Y 的前缀最小值。如果发现一个 X 值比 Y 的前缀最小值还要小,就说明它与前面的行构不成上述的包含关系。此时就算这个 X 值能够和后面的 Y 值构成合法关系,也不能走通(中间没有 X_i > Y_j 的点,路断了)。
并且我们发现,在这种特殊性质的情况下,一定有 dp_{n, i} 和 dp_{i, m} 都为 true。所以如果我们能走到第 n-1 行或第 m-1 列就可以走通。
接下来考虑推广到一般情况。找到 X 的全局最大值 x 和 Y 的全局最小值 y。(x, y) 将整个网格图分为四个部分。我们只关注左上方部分和右下方部分。分别按照上面的做法计算两个部分是否能够到达 (x, y)(做右下方部分的时候可以把序列颠倒过来)。如果都能到达,说明存在合法路径,这条合法路径以 (x, y) 为中继点连接左上方和右下方。时间复杂度将至 O(n+m)。最后输出即可。

